#include <iostream>
#include <list>
#define N 9
#define B 3//square root of N
using namespace std;
typedef int STATUS;
typedef list<STATUS*> FRINGE;
typedef void (FRINGE::*COMBINER)(FRINGE::const_reference);
void report(STATUS* s)
{
for (int i=0; i<N*N; ++i) {
cout<<s[i];
if (i%N==N-1) cout<<endl;
}
cout<<endl;
}
bool goal(STATUS* s)
{
for (int i=0; i<N*N; ++i) {
if (s[i]==0) return false;
}
return true;
}
bool canBePlaced(STATUS* s, int pos, int x)
{
int row=pos/N;
int col=pos%N;
int i, j, topLeft;
for (i=0; i<N; ++i) {
if (s[row*N+i]==x) return false;
if (s[col+i*N]==x) return false;
}
topLeft=N*(row/B)*B+(col/B)*B;
for (i=0; i<B; ++i) {
for (j=0; j<B; ++j) {
if (s[topLeft+i*N+j]==x) return false;
}
}
return true;
}
void expand(FRINGE* fringe, STATUS* s, COMBINER combiner)
{
int pos;
for (pos=0; pos<N*N; ++pos) {
if (s[pos]==0) break;
}
for (int x=1; x<=N; ++x) {
if (canBePlaced(s, pos, x)) {
STATUS* newStatus=new STATUS[N*N];
for (int i=0; i<N*N; ++i) newStatus[i]=s[i];
newStatus[pos]=x;
(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) {
while (!fringe->empty()) {
STATUS* tmp=fringe->front();
fringe->pop_front();
delete tmp;
}
}
}
else expand(fringe, s, combiner);
delete s;
search(fringe, combiner, findAll);
}
}
int main ()
{
int problem[]={
1,0,0,0,0,7,0,9,0,
0,3,0,0,2,0,0,0,8,
0,0,9,6,0,0,5,0,0,
0,0,5,3,0,0,9,0,0,
0,1,0,0,8,0,0,0,2,
6,0,0,0,0,4,0,0,0,
3,0,0,0,0,0,0,1,0,
0,4,0,0,0,0,0,0,7,
0,0,7,0,0,0,3,0,0};
STATUS* s=new STATUS[N*N];
for (int i=0; i<N*N; ++i) s[i]=problem[i];
FRINGE* fringeP=new FRINGE();
fringeP->push_back(s);
//search(fringeP, &FRINGE::push_front, true); //depth-first search
search(fringeP, &FRINGE::push_back, true); //breadth-first search
return 0;
}