A Soduku Puzzle Solver

soduku.cc

#include <vector>
#include <set>
#include <algorithm>
#include <ctime>
#include <iostream>

const int UNASSIGNED = 0;
const int N = 9;

class Grid {
 private:
  std::vector<unsigned> grid;
  std::set<unsigned> locations;
  unsigned sizeSquared;

 public:
  Grid() {
    sizeSquared = N * N;
    grid.resize(sizeSquared);
  }

  void Copy(unsigned matrix[N][N]) {
    for (int row = 0; row < N; ++row) {
      for (int col = 0; col < N; ++col) {
        grid[row + col * N] = matrix[row][col];
      }
    }
  }

  void Print() const {
    for (int row = 0; row < N; row++) {
      for (int col = 0; col < N; col++) std::cout << grid[row + col * N] << " ";
      std::cout << std::endl;
    }
    std::cout << std::endl;
  }

  bool Solve() {
    int row, col;
    if (!HasUnassignedLocations(row, col)) return true;
    // consider digits 1 to 9

    for (int num = 1; num <= 9; num++) {
      if (IsFeasible(row, col, num)) {
        grid[row + col * N] = num;
        if (Solve()) {
          return true;
        }
        // Try again
        grid[row + col * N] = UNASSIGNED;
      }
    }
    return false;
  }

 private:
  bool HasUnassignedLocations(int &row, int &col) {
    for (row = 0; row < N; row++)
      for (col = 0; col < N; col++)
        if (grid[row + col * N] == UNASSIGNED) return true;

    return false;
  }

  bool IsFeasible(int row, int col, int num) {
    // Check if number not already placed in current row, col, 3x3
    // box
    return !InRow(row, num) && !InColumn(col, num) &&
           !In3x3Box(row - row % 3, col - col % 3, num);
  }

  bool InRow(int row, int num) {
    for (int col = 0; col < N; col++)
      if (grid[row + col * N] == num) return true;
    return false;
  }
  bool InColumn(int col, int num) {
    for (int row = 0; row < N; row++)
      if (grid[row + col * N] == num) return true;
    return false;
  }

  bool In3x3Box(int boxStartRow, int boxStartCol, int num) {
    for (int row = 0; row < 3; row++)
      for (int col = 0; col < 3; col++) {
        int rown = row + boxStartRow;
        int coln = col + boxStartCol;

        if (grid[rown + coln * N] == num) return true;
      }
    return false;
  }
};

int main() {
  Grid gr;

  unsigned grid[N][N] = {{0, 7, 4, 3, 0, 2, 0, 0, 0},
                         {0, 0, 0, 0, 0, 5, 0, 4, 0},
                         {0, 0, 0, 6, 0, 7, 9, 0, 0},
                         {0, 5, 6, 0, 0, 0, 7, 9, 0},
                         {3, 0, 0, 0, 0, 0, 0, 0, 5},
                         {0, 2, 7, 0, 0, 0, 6, 8, 0},
                         {0, 0, 5, 7, 0, 1, 0, 0, 0},
                         {0, 1, 0, 2, 0, 0, 0, 0, 0},
                         {0, 0, 0, 4, 0, 8, 1, 6, 0}};

  gr.Copy(grid);
  std::cout << "Initial Puzzle:" << std::endl
            << std::endl;
  gr.Print();

  if (true == gr.Solve()) {
    std::cout << "Solved Puzzle:" << std::endl
              << std::endl;
    gr.Print();
  } else {
    std::cout << "No solution exists";
  }
  return 0;
}