POJ 2676-Sudoku
Sudoku
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 14104 Accepted: 6963 Special Judge
Description
Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3×3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other cells are empty. The goal is to fill the empty cells with decimal digits from 1 to 9, one digit per cell, in such way that in each row, in each column and in each marked 3×3 subsquare, all the digits from 1 to 9 to appear. Write a program to solve a given Sudoku-task.
Input
The input data will start with the number of the test cases. For each test case, 9 lines follow, corresponding to the rows of the table. On each line a string of exactly 9 decimal digits is given, corresponding to the cells in this line. If a cell is empty it is represented by 0.
Output
For each test case your program should print the solution in the same format as the input data. The empty cells have to be filled according to the rules. If solutions is not unique, then the program may print any one of them.
Sample Input
1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
Sample Output
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127
Source
Southeastern Europe 2005
这一题是练习深度搜索和剪枝的好题目。题意很简答，数独游戏，在每一行、每一列和每一个小正方形填入1-9这9个数字，数字不能重复，求一种可以的方案。
因为只需要求一种可行解，根据
POJ Problem 3278: Catch That Cow后面的总结，很快有了深度搜索的思路：
从上到下，从左到右依次扫描每一个格子，如果这个格子上的数字不是0，说明原来就有数字了，不用填，测试下一个格子；如果这个格子为0，则求出可填入该格子的候选数字，再依次测试每一个候选数字是否可行，一直这样深度搜索下去，直到将所有格子测试完毕。这个思路相信很多人都能很快想到，完整的代码如下：
[cpp]
#include<iostream>
#include<vector>
using namespace std;
const int N=9;
int board[N][N];//棋盘
int candidates[N];//对于某一个坐标ij，可以填入的候选数字
//给定坐标(row,column),求它所在的小方格的左上角坐标
void get_subquare_start(int row,int column,int& x0,int& y0)
{
if(row<3&&column<3)
{
x0=0;
y0=0;
}
else if(row<3&&column<6)
{
x0=0;
y0=3;
}
else if(row<3&&column<9)
{
x0=0;
y0=6;
}
else if(row<6&&column<3)
{
x0=3;
y0=0;
}
else if(row<6&&column<6)
{
x0=3;
y0=3;
}
else if(row<6&&column<9)
{
x0=3;
y0=6;
}
else if(row<9&&column<3)
{
x0=6;
y0=0;
}
else if(row<9&&column<6)
{
x0=6;
y0=3;
}
else if(row<9&&column<9)
{
x0=6;
y0=6;
}
}
//给定坐标(row,column),将可以填入该坐标的候选数字放入vi
//思路就是先把candidates[N]填满1-9，然后将给定坐标的
//横轴、纵轴、小方格出现过的数字去掉，剩下的数字就是
//候选数字
void get_candidates(int row,int column,vector<int>& vi)
{
for(int i=0;i<N;i++)
candidates[i]=i+1;
for(int i=0;i<N;i++)//横轴
{
if(board[row][i]!=0)
candidates[board[row][i]-1]=0;
}
for(int i=0;i<N;i++)//纵轴
{
if(board[i][column]!=0)
candidates[board[i][column]-1]=0;
}
int x0,y0;
get_subquare_start(row,column,x0,y0);
for(int i=x0;i<x0+3;i++)//小方格
{
for(int j=y0;j<y0+3;j++)
{
if(board[i][j]!=0)
candidates[board[i][j]-1]=0;
}
}
for(int i=0;i<N;i++)//重复工作，可优化
if(candidates[i]!=0)
vi.push_back(candidates[i]);
}
//深度搜索
bool dfs(int pos)
{
if(pos==N*N)
{
return true;
}
int row=pos/N;
int column=pos%N;
if(board[row][column]!=0)//如果有数字
return dfs(pos+1);//则搜下一个格子
else
{
vector<int> local_candidates;//要使用局部的candidates，因为如果是全局的，那么回溯的时候candidates已经修改了
get_candidates(row,column,local_candidates);//获取可填入该格子的候选数字
int cand_num=local_candidates.size();
for(int i=0;i<cand_num;i++)
{
board[row][column]=local_candidates[i];//填入
if(dfs(pos+1))//继续搜下一个格子
return true;
}
board[row][column]=0;//回溯
return false;//回溯
}
}
int main()
{
freopen("input.txt","r",stdin);
int t;
char c;
cin>>t;
while(t–)
{
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
cin>>c;
board[i][j]=c-‘0’;
}
}
if(dfs(0))
{
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
cout<<board[i][j];
cout<<endl;
}
}
}
return 0;
}
[/cpp]
满心欢喜的提交后发现TLE超时了，此时泪流满面，后来又琢磨了一下，师兄给的分类是
简单搜索技巧和剪枝，我上面的代码压根就没有剪枝，TLE也就不足为奇了。
那么怎样剪枝？想一想我们手算解数独的过程，正常情况下，如果A这个格子有5个候选数字可以填入，而B这个格子只有2个候选数字可以填入，我们肯定会先填好B这个格子，再填A，因为B的情况少一些，而填完B之后，A的情况可能又会减少，这样比先填A再填B会快得多。根据这样的思路，我们
在每次深度搜索的时候，把每个空格的候选数字求出来，并求候选数字个数最少的那个格子C，填格子C，继续深度搜索，直到所有空格填满为止。
可能有的同学会问，每次深度搜索的时候都要求一遍
所有空格的候选数字，这样会不会耗时太多了，这个我也担心过，但是总体来说，剪枝比第一个版本的代码高效多了。下面是剪枝版本的完整代码：
[cpp]
#include<iostream>
#include<vector>
using namespace std;
const int N=9;
int board[N][N];//棋盘
int candidates[N];//对于某一个坐标ij，可以填入的候选数字
//给定坐标(row,column),求它所在的小方格的左上角坐标
void get_subquare_start(int row,int column,int& x0,int& y0)
{
if(row<3&&column<3)
{
x0=0;
y0=0;
}
else if(row<3&&column<6)
{
x0=0;
y0=3;
}
else if(row<3&&column<9)
{
x0=0;
y0=6;
}
else if(row<6&&column<3)
{
x0=3;
y0=0;
}
else if(row<6&&column<6)
{
x0=3;
y0=3;
}
else if(row<6&&column<9)
{
x0=3;
y0=6;
}
else if(row<9&&column<3)
{
x0=6;
y0=0;
}
else if(row<9&&column<6)
{
x0=6;
y0=3;
}
else if(row<9&&column<9)
{
x0=6;
y0=6;
}
}
//给定坐标(row,column),将可以填入该坐标的候选数字放入vi
//思路就是先把candidates[N]填满1-9，然后将给定坐标的
//横轴、纵轴、小方格出现过的数字去掉，剩下的数字就是
//候选数字
void get_candidates(int row,int column,vector<int>& vi)
{
for(int i=0;i<N;i++)
candidates[i]=i+1;
for(int i=0;i<N;i++)//横轴
{
if(board[row][i]!=0)
candidates[board[row][i]-1]=0;
}
for(int i=0;i<N;i++)//纵轴
{
if(board[i][column]!=0)
candidates[board[i][column]-1]=0;
}
int x0,y0;
get_subquare_start(row,column,x0,y0);
for(int i=x0;i<x0+3;i++)//小方格
{
for(int j=y0;j<y0+3;j++)
{
if(board[i][j]!=0)
candidates[board[i][j]-1]=0;
}
}
for(int i=0;i<N;i++)//重复工作，可优化
if(candidates[i]!=0)
vi.push_back(candidates[i]);
}
//深度搜索
bool dfs(vector<int>& blank_pos)
{
int blank_num=blank_pos.size();
if(blank_num==0)//如果空格都填完了，返回true
{
return true;
}
int row,column,pos;
int min_candidates=N+1;
vector<int> global_candidates;
for(int i=0;i<blank_num;i++)
{
row=blank_pos[i]/N;
column=blank_pos[i]%N;
vector<int> local_candidates;
get_candidates(row,column,local_candidates);//对于每一个空格求可填入的候选数字
if(local_candidates.size()<min_candidates)//求到最小值
{
pos=blank_pos[i];//记录位置
min_candidates=local_candidates.size();
global_candidates.clear();
global_candidates=local_candidates;//vector可以直接赋值
}
}
row=pos/N;
column=pos%N;
vector<int> next_blank_pos;
for(int j=0;j<blank_num;j++)
if(blank_pos[j]!=pos)
next_blank_pos.push_back(blank_pos[j]);//剩余的空格
for(int i=0;i<min_candidates;i++)
{
board[row][column]=global_candidates[i];//填入
if(dfs(next_blank_pos))//继续搜下一个格子
return true;
}
board[row][column]=0;//回溯
return false;//回溯
}
//剪枝版本，AC，用时282MS，内存240K
int main()
{
//freopen("input.txt","r",stdin);
int t;
char c;
cin>>t;
vector<int> blank_pos;
while(t–)
{
blank_pos.clear();//因为可能有多个case，所以每次都要clear！！！
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
cin>>c;
board[i][j]=c-‘0’;
if(board[i][j]==0)
blank_pos.push_back(i*N+j);
}
}
if(dfs(blank_pos))
{
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
cout<<board[i][j];
cout<<endl;
}
}
}
return 0;
}
[/cpp]
这个版本的代码需要注意一个小细节，我在每次输入的时候都将空格的位置记录在了blank_pos的vector中，因为题目说有多个case，所以每次输入的时候都要记得blank_pos.clear()，要不然会影响下一个case。这个版本的代码AC，用时282MS，内存240K。
AC之后，又看了一下discuss，发现很多同学谈到如果倒搜，会比顺搜快得多，倒搜就是从最后一个格子开始搜索。闲来无事，我就把第一个版本的代码改成了倒搜索，只需要修改两三个地方，代码如下：
[cpp]
#include<iostream>
#include<vector>
using namespace std;
const int N=9;
int board[N][N];//棋盘
int candidates[N];//对于某一个坐标ij，可以填入的候选数字
//给定坐标(row,column),求它所在的小方格的左上角坐标
void get_subquare_start(int row,int column,int& x0,int& y0)
{
if(row<3&&column<3)
{
x0=0;
y0=0;
}
else if(row<3&&column<6)
{
x0=0;
y0=3;
}
else if(row<3&&column<9)
{
x0=0;
y0=6;
}
else if(row<6&&column<3)
{
x0=3;
y0=0;
}
else if(row<6&&column<6)
{
x0=3;
y0=3;
}
else if(row<6&&column<9)
{
x0=3;
y0=6;
}
else if(row<9&&column<3)
{
x0=6;
y0=0;
}
else if(row<9&&column<6)
{
x0=6;
y0=3;
}
else if(row<9&&column<9)
{
x0=6;
y0=6;
}
}
//给定坐标(row,column),将可以填入该坐标的候选数字放入vi
//思路就是先把candidates[N]填满1-9，然后将给定坐标的
//横轴、纵轴、小方格出现过的数字去掉，剩下的数字就是
//候选数字
void get_candidates(int row,int column,vector<int>& vi)
{
for(int i=0;i<N;i++)
candidates[i]=i+1;
for(int i=0;i<N;i++)//横轴
{
if(board[row][i]!=0)
candidates[board[row][i]-1]=0;
}
for(int i=0;i<N;i++)//纵轴
{
if(board[i][column]!=0)
candidates[board[i][column]-1]=0;
}
int x0,y0;
get_subquare_start(row,column,x0,y0);
for(int i=x0;i<x0+3;i++)//小方格
{
for(int j=y0;j<y0+3;j++)
{
if(board[i][j]!=0)
candidates[board[i][j]-1]=0;
}
}
for(int i=0;i<N;i++)//重复工作，可优化
if(candidates[i]!=0)
vi.push_back(candidates[i]);
}
//深度搜索
bool dfs(int pos)
{
if(pos==-1)//倒搜到-1结束
{
return true;
}
int row=pos/N;
int column=pos%N;
if(board[row][column]!=0)//如果有数字
return dfs(pos-1);//则搜下一个格子
else
{
vector<int> local_candidates;//要使用局部的candidates，因为如果是全局的，那么回溯的时候candidates已经修改了
get_candidates(row,column,local_candidates);//获取可填入该格子的候选数字
int cand_num=local_candidates.size();
for(int i=0;i<cand_num;i++)
{
board[row][column]=local_candidates[i];//填入
if(dfs(pos-1))//继续搜下一个格子
return true;
}
board[row][column]=0;//回溯
return false;//回溯
}
}
//倒搜版本，AC，用时125MS，内存224K
int main()
{
//freopen("input.txt","r",stdin);
int t;
char c;
cin>>t;
while(t–)
{
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
cin>>c;
board[i][j]=c-‘0’;
}
}
if(dfs(N*N-1))//倒搜
{
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
cout<<board[i][j];
cout<<endl;
}
}
}
return 0;
}
[/cpp]
令我吃惊的是，倒搜这个版本的代码AC了，而且用时125MS，内存224K，居然比剪枝还要快，内存占用也更少。到现在我还没有搞清楚更快的原因。]]>