#include <iostream>
#include <vector>
#include <list>
using namespace std;
typedef vector<vector<int> > STATUS;
typedef list<STATUS*> FRINGE;
typedef void (FRINGE::*COMBINER)(FRINGE::const_reference);
void report(STATUS* s)
{
for (int i=0; i<9; ++i) {
for (int j=0; j<9; ++j) cout<<(*s)[i][j];
cout<<endl;
}
cout<<endl;
}
bool goal(STATUS* s)
{
for (int i=0; i<9; ++i) {
for (int j=0; j<9; ++j) if ((*s)[i][j]==0) return false;
}
return true;
}
void findCandidates(STATUS* s, int i, int j, bool* candidates)
{
for (int n=1; n<=9; ++n) *(candidates+n)=true;
for (int k=0; k<9; ++k) {
*(candidates+(*s)[i][k])=false;
*(candidates+(*s)[k][j])=false;
}
for (int r=0; r<3; ++r) {
for (int c=0; c<3; ++c) *(candidates+(*s)[3*(i/3)+r][3*(j/3)+c])=false;
}
}
void expand(FRINGE* fringe, STATUS* s, COMBINER combiner)
{
int i=0, j=0;
for (i=0; i<9; ++i) {
for (j=0; j<9; ++j) if ((*s)[i][j]==0) goto FOUND;
}
FOUND:
bool candidates[10];
findCandidates(s, i, j, candidates);
for (int n=1; n<=9; ++n) {
if (candidates[n]) {
STATUS* newSTATUS=new STATUS(*s);
(*newSTATUS)[i][j]=n;
(fringe->*combiner)(newSTATUS);
}
}
}
void search(FRINGE* fringe, COMBINER combiner, bool findAll)
{
if (fringe->size()!=0) {
STATUS* s=fringe->front();
fringe->pop_front();
if (goal(s)) {
report(s);
if (!findAll) fringe->clear();
}
else expand(fringe, s, combiner);
delete s;
search(fringe, combiner, findAll);
}
}
int main ()
{
int problem[][9]={
{0,0,5,3,0,0,0,0,0},
{8,0,0,0,0,0,0,2,0},
{0,7,0,0,1,0,5,0,0},
{4,0,0,0,0,5,3,0,0},
{0,1,0,0,7,0,0,0,6},
{0,0,3,2,0,0,0,8,0},
{0,6,0,5,0,0,0,0,9},
{0,0,4,0,0,0,0,3,0},
{0,0,0,0,0,9,7,0,0}};
STATUS* s=new STATUS(9);
for (int i=0; i<9; ++i) {
(*s)[i].resize(9);
for (int j=0; j<9; ++j) (*s)[i][j]=problem[i][j];
}
FRINGE fringe;
fringe.push_back(s);
search(&fringe, &FRINGE::push_front, false); //depth-first search
//search(&fringe, &FRINGE::push_back, false); //breadth-first search
return 0;
}