题目

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;
            }
        }
    }
}