题目
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.
A sudoku puzzle...
...and its solution numbers marked in red.
分析
向空格填入1-9，填满整个表格。需要依次向空位填值，然后检查该值会不会影响整个表格的合法性。然而由于之前的表格是合法的，所以只需要判断引入的该值所在行列及其方框不冲突即可。
我使用两种递归的方法，及将递归改为堆栈式的如下C代码都能通过。
//判断 加入该数字后是否有效,(boardRowSize，boardColSize)
bool isValid(char** board, int i, int j)
{
for(int k=0;k<9;k++)
{
if(k!=j && board[i][k]==board[i][j])
return false;
}
for(int k=0;k<9;k++)
{
if(k!=i && board[k][j]==board[i][j])
return false;
}
for(int row = i/3*3; row<i/3*3+3; row++)
{
for(int col=j/3*3; col<j/3*3+3; col++)
{
if((row!=i || col!=j) && board[row][col]==board[i][j])
return false;
}
}
return true;
}
bool isValidSudoku(char** board, int boardRowSize, int boardColSize) {
//printf("isValidSudoku:%d %d %c\n",boardRowSize,boardColSize,board[boardRowSize][boardColSize]);
bool answer=true;
int temp[10]={0};
int i=0,j=0;
//判断横行
for(int k=0;k<10;k++)
temp[k]=0;
for(i=0;i<9;i++)
{
if(board[boardRowSize][i]!='.')
{
if(temp[board[boardRowSize][i]-'0']==0)
{
temp[board[boardRowSize][i]-'0']=1;
}
else
{
return false;//answer=false;break;
}
}
}
//判断竖行
for(int k=0;k<10;k++)
temp[k]=0;
for(i=0;i<9;i++)
{
if(board[i][boardColSize]!='.')
{
if(temp[board[i][boardColSize]-'0']==0)
{
temp[board[i][boardColSize]-'0']=1;
}
else
{
return false;//answer=false;break;
}
}
}
//1个方框
for(int k=0;k<10;k++)
temp[k]=0;
i=boardRowSize/3;
j=boardColSize/3;
int left[9] ={0+3*i,0+3*i,0+3*i,1+3*i,1+3*i,1+3*i,2+3*i,2+3*i,2+3*i};
int right[9]={0+3*j,1+3*j,2+3*j,0+3*j,1+3*j,2+3*j,0+3*j,1+3*j,2+3*j};
for(int k=0;k<9;k++)
{
if(board[left[k]][right[k]]!='.')
{
if(temp[board[left[k]][right[k]]-'0']==0)
{
temp[board[left[k]][right[k]]-'0']=1;
}
else
{
return false;//answer=false;break;
}
}
}
return answer;
}
//方法2，依次寻找空值进行递归
bool solver2(char** board,int ans,int emptynums)
{
int pi=-1,pj=-1;
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(board[i][j]=='.')
{
pi=i;
pj=j;
break;
}
}
if(pi!=-1)
break;
}
if(pi==-1&&pj==-1)
return false;
else
{
for(int k=1;k<=9;k++)
{
board[pi][pj]=k+'0';
if(isValidSudoku(board,pi,pj)==true)
{
//printf("%d %d %d %d %c\n",ans,emptynums,pi,pj,board[pi][pj]);
if(ans+1==emptynums)
return true;
else if(solver2(board,ans+1,emptynums)==true)
return true;
}
board[pi][pj]='.';
}
//return solver2(board,ans-1,emptynums);
}
return false;
}
//方法1，挨个元素递归
bool solver1(char** board, int i, int j)
{
if(j>=9)
return solver1(board,i+1,0);
if(i==9)
return true;
if(board[i][j]=='.')
{
for(int k=1;k<=9;k++)
{
board[i][j]=k+'0';
if(isValidSudoku(board,i,j)==true)
{
if(solver1(board,i,j+1)==true)
return true;
}
board[i][j]='.';
}
}
else
return solver1(board,i,j+1);
return false;
}
void solveSudoku(char** board, int boardRowSize, int boardColSize) {
int ans=0;
int emptyi[100]={0},emptyj[100]={0},emptyvalue[100]={0},emptynums=0;
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(board[i][j]=='.')
{
emptyi[emptynums]=i;
emptyj[emptynums]=j;
emptynums++;
}
}
}
//solver1(board,0,0);
//solver2(board,ans,emptynums);
//方法3 堆栈式
while(ans<emptynums)
{
//printf("%d %d %c %d %d\n",emptyi[ans],emptyj[ans],board[emptyi[ans]][emptyj[ans]],ans,emptynums);
char temp=board[emptyi[ans]][emptyj[ans]];
if(board[emptyi[ans]][emptyj[ans]]=='9')
{
board[emptyi[ans]][emptyj[ans]]='.';
ans--;
}
else
{
if(board[emptyi[ans]][emptyj[ans]]=='.')
{
board[emptyi[ans]][emptyj[ans]]='1';
}
else if(board[emptyi[ans]][emptyj[ans]]<'9')
{
board[emptyi[ans]][emptyj[ans]]=board[emptyi[ans]][emptyj[ans]]+1;
}
if(isValidSudoku(board,emptyi[ans],emptyj[ans])==true)
{
ans++;
//if(ans==emptynums)
//break;
}
}
}
}
