#include <iostream>
#include <list>
using namespace std;
int map[9][9]={
4,0,0,0,0,2,0,0,9,
9,5,8,0,0,3,7,0,0,
2,0,7,5,0,0,4,0,0,
0,0,0,0,0,0,0,1,0,
1,9,2,0,3,0,0,4,5,
0,4,0,0,0,0,0,0,0,
0,0,9,0,0,6,2,0,4,
0,2,4,3,0,0,8,9,6,
6,0,0,2,0,0,0,0,0
};
int count;
struct Point
{
int i;
int j;
};
bool row[9][9];
bool col[9][9];
bool block[9][9];
list<Point> spaces;
void Print(int a[][9])
{
for(int i = 0;i < 9;i++)
{
for(int j = 0;j < 9;j++)
{
cout<<a[i][j]<<' ';
}
cout<<endl;
}
}
/**
* 提取空格，保存到spaces链表
* 标记行、列、块的候选数
*/
void PickUp()
{
int t;
Point p;
for(int i = 0;i < 9;i++)
{
for(int j = 0;j < 9;j++)
{
t = map[i][j];
if(t == 0)
{
p.i = i;
p.j = j;
spaces.push_back(p);
}
else
{
row[i][t-1] = true;
col[j][t-1] = true;
block[i/3*3 + j/3][t-1] = true;
}
}
}
}
/**
* 返回下一个候选数
*/
int next(Point& p,int d)
{
bool* r = row[p.i];
bool* c = col[p.j];
bool* b = block[p.i/3*3 + p.j/3];
for(int i = d;i < 9;i++)
if((r[i] || c[i] || b[i]) == false)
return i + 1;
return -1;
}
/**
* 设置某一格所在行、列、块的标记
*/
void set(Point& p,bool choosed)
{
int t = map[p.i][p.j];
if(t == 0)
{
cout<<"设置某一格所在行、列、块的标记错误,("<<p.i<<","<<p.j<<")=0"<<endl;
exit(-1);
}
row[p.i][t-1] = choosed;
col[p.j][t-1] = choosed;
block[p.i/3*3 + p.j/3][t-1] = choosed;
}
void Solve(list<Point>::iterator& it)
{
if(it == spaces.end())
{
Print(map);
cout<<endl;
count++;
return;
}
//获得该处下一个候选数
int d = next(*it,0);
list<Point>::iterator next_it(it);
++next_it;
for(;d > 0;d = next(*it,d))
{
//填入
map[it->i][it->j] = d;
//设置标记数组，表明不再成为该行、列、块中的候选数
set(*it,true);
//转到下一个点
Solve(next_it);
//设置标记数组，表明再次成为该行、列、块中的候选数
set(*it,false);
//恢复
map[it->i][it->j] = 0;
}
}
int main()
{
PickUp();
