[LeetCode]Sudoku Solver

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.

A sudoku puzzle...

...and its solution numbers marked in red.

和Valid Sudoku还是有区别的。这里默认有唯一解了，不需要全盘验证。

用到回溯的思想。在‘.’位置插入1-9数字，判断是否满足数独的条件，如果不满足，则回溯，直到‘.’添加的数字都满足。

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board,int x,int y)
    {
        for(int i=0;i<9;i++)
        {
            if((i!=x)&&(board[x][y]==board[i][y]))
            {
                return false;
            }
        }
        for(int i=0;i<9;i++)
        {
            if((i!=y)&&(board[x][y]==board[x][i]))
            {
                return false;
            }
        }
        for(int m=x/3*3;m<x/3*3+3;m++)
        {
            for(int n=y/3*3;n<y/3*3+3;n++)
            {
                if((m!=x)&&(n!=y)&&(board[m][n]==board[x][y]))
                {
                    return false;
                }
            }
        }
        return true;
    }
    
    bool isSolveSudoku(vector<vector<char>>& board) {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j]=='.')
                {
                    for(int k=0;k<9;k++)
                    {
                        board[i][j]='1'+k;
                        if((isValidSudoku(board,i,j))&&(isSolveSudoku(board)))
                        {
                            return true;
                        }
                        board[i][j]='.';
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    void solveSudoku(vector<vector<char>>& board) {
        isSolveSudoku(board);
    }
};