#include <iostream>
#include <stack>
#include <vector>
// function main use arry to initialize a sudoku game.
// You can use 0 to take instead of any number in the array.
// recompile the cpp use command: g++ -o sudoku sudoku.cpp
// Then run it use commond: ./sudoku.
using std::stack;
using std::vector;
using namespace std;
const int SUDOKU_COLS = 3;
const int SUDOKU_ROWS = 3;
const int SUDOKU_DIMS = SUDOKU_COLS * SUDOKU_ROWS;
class CSudoku
{
public:
CSudoku(){}
CSudoku(int array[][9]);
void next_step(vector<CSudoku>&);
bool have_finished() const;
friend ostream& operator << (ostream &os, const CSudoku &s);
friend istream& operator >> (istream &is, CSudoku &s);
private:
int cell[SUDOKU_DIMS][SUDOKU_DIMS];
void fill_number(bool pos[], const int width, bool value);
static void dispose_number(bool *pos, int i)
{
if (i != 0)
{
pos[i - 1] = false;
}
}
};
CSudoku::CSudoku(int array[][9])
{
for (int r = 0; r < SUDOKU_DIMS; r++)
for (int c = 0; c < SUDOKU_DIMS; c++)
cell[r][c] = array[r][c];
}
void CSudoku::fill_number(bool pos[], const int width, bool value)
{
for (int i = 0; i < width; i++)
pos[i] = true;
}
ostream &operator << (ostream &os, const CSudoku &s)
{
for (int i = 0; i < SUDOKU_DIMS; i++)
{
for (int j = 0; j < SUDOKU_DIMS; j++)
{
os << s.cell[i][j] << " ";
}
os << endl;
}
return os;
}
istream &operator >> (istream &is, CSudoku &ps)
{
int v;
for (int r = 0; r < SUDOKU_DIMS; r++)
{
for (int c = 0; c < SUDOKU_DIMS; c++)
{
is >> v;
ps.cell[r][c] = (v < 1 || v > 9) ? 0 : v;
}
}
return is;
}
bool print_result(const CSudoku &s)
{
cout << "CSudoku answer:/n" << s << endl;
return true;
}
bool CSudoku::have_finished() const
{
for (int row = 0; row < SUDOKU_DIMS; row++)
{
for (int column = 0; column < SUDOKU_DIMS; column++)
{
if (cell[row][column] == 0)
return false;
}
}
return true;
}
void CSudoku::next_step(vector<CSudoku>& vs)
{
CSudoku sdk;
bool pos[SUDOKU_DIMS];
for (int row = 0; row < SUDOKU_DIMS; row++)
{
for (int column = 0; column < SUDOKU_DIMS; column++)
{
if (cell[row][column] == 0)
{
fill_number(pos, SUDOKU_DIMS, true);
for (int i = 0; i < SUDOKU_DIMS; i++)
{
dispose_number(pos, cell[i][column]);
dispose_number(pos, cell[row][i]);
}
int lr = row - (row % SUDOKU_ROWS);
int lc = column - (column % SUDOKU_COLS);
for (int i = 0; i < SUDOKU_ROWS; i++)
{
for (int j = 0; j < SUDOKU_COLS; j++)
{
dispose_number(pos, cell[lr + i][lc + j]);
}
}
for (int i = 0; i < SUDOKU_DIMS; i++)
{
if (pos[i])
{
sdk = *this;
sdk.cell[row][column] = i + 1;
vs.push_back(sdk);
}
}
return;
}
}
}
}
template <class T1, class T2>
int depth_first_search(const T1 &init_state, const T2 &after_find_solution)
{
int n = 0;
stack<T1> states;
states.push(init_state);
vector<T1> next_states;
bool stop = false;
while (!stop && !states.empty())
{
T1 s = states.top();
states.pop();
next_states.clear();
s.next_step(next_states);
for (typename vector<T1>::iterator i = next_states.begin(); i != next_states.end(); ++i)
{
if (i->have_finished())
{
++n;
if (after_find_solution(*i))
{
stop = true;
break;
}
}
else
{
states.push(*i);
}
}
}
return n;
}
int main(int argc, char **argv)
{
int array[9][9] = {
{3,1,7,4,6,9,8,2,5},
{4,5,6,2,8,7,3,1,9},
{9,2,8,3,1,5,7,4,6},
{2,8,5,6,4,3,9,7,1},
{6,4,1,7,9,8,5,3,2},
{7,3,9,5,2,1,4,6,8},
{1,7,2,8,5,4,6,9,3},
{8,6,3,9,7,2,1,5,4},
{5,9,4,1,3,6,2,8,7},
};
CSudoku sudo(array);
if (argc != 1)
cin >> sudo;
cout << "Question:/n" << sudo << endl;
int n = depth_first_search(sudo, &print_result);
if (n == 0)
{
cout << "Solution not found!" << endl;
}
else
{
cout << n << " solution(s) found!/n" << endl;
}
return 0;
}
