【回溯法】Sudoku Solver

题目：leetcode

Sudoku Solver

 

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.

分析：

要想用回溯法，必须能够有办法回溯（即回溯的时候，要知道上一个没有数字的空格在哪里）。本代码里设置一个函数 bool solveSudoku_core(vector<vector<char> > &board,int row,int col)，巧妙解决这个问题。注意solveSudoku_core最后一行返回的是true！这是递归截止的条件。

class Solution {
public:
    void solveSudoku(vector<vector<char> > &board) {
        if(board.empty() || board[0].empty())
        return;
        
        solveSudoku_core(board,0,0);
    }
    
    bool solveSudoku_core(vector<vector<char> > &board,int row,int col)
    {
        for(int j=col;j<9;j++)
        {
            if(board[row][j]!='.')
            continue;
            for(char k='1';k<='9';k++)
            {
                board[row][j]=k;
                if(isValid(board,row,j) && solveSudoku_core(board,row,j+1))
                    return true;
                board[row][j]='.';
            }
            if( board[row][j]=='.')
            return false;
        }
        
        for(int i=row+1;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                 if(board[i][j]!='.')
                    continue;
                 for(char k='1';k<='9';k++)
                {
                board[i][j]=k;
                if(isValid(board,i,j) && solveSudoku_core(board,i,j+1))
                    return true;
                board[i][j]='.';
                }
                if( board[i][j]=='.')
                    return false;
            }
        }
        return true;
        
    }
    
    bool isValid(vector<vector<char> > &board,int row,int col)
    {
        char c=board[row][col];
        for(int i=0;i<9;i++)
        {
            if(i==row)//注意
            continue;
            if(board[i][col]==c)
            return false;
        }
        for(int j=0;j<9;j++)
        {
            if(j==col)//注意
            continue;
            if(board[row][j]==c)
            return false;
        }
        int f[3]={0,3,6};//注意
        int rowstart=f[row/3],colstart=f[col/3];
        for(int i=rowstart;i<rowstart+3;i++)
        {
            for(int j=colstart;j<colstart+3;j++)
            {
                if(i==row && j==col)//注意
                continue;
                if(board[i][j]==c)
                    return false;
            }
        }
        return true;
    }
};