[LeetCode]037-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.
Solution:遡及法に似た考え方で、最後まで繰り返し、trueを返し、そうでなければfalseを返します.遡及法は判断関数,すなわちcheckに注意し,現在挿入する値が横,縦,サブグリッド内で合法であると判断する.
コードは次のとおりです.

 void solveSudoku(vector<vector<char>>& board) 
    {
        solve(board);
    }

    bool solve(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 = 1;k<=9;k++)
                    {
                        board[i][j] = k + '0';
                        if(isValid(board,i,j) && solve(board))
                            return true;
                        board[i][j] = '.';
                    }
                    return false;
                }
            }
        }
        return true;
    }

    bool isValid(vector<vector<char>>& board,int row,int col)
    {
        int i,j;
        i = j = 0;
        for(i =0;i<9;i++)
        {
            if(i != row && board[row][col] == board[i][col])
                return false;
        }

        for(j = 0;j<9;j++)
        {
            if(j != col && board[row][col] == board[row][j])
                return false;
        }

        int grid_row = row/3 * 3;
        int grid_col  = col/3 * 3;
        for(i =0;i<3;i++)
            for(j =0;j<3;j++)
            {
                if(row != i+grid_row && col != j + grid_col && board[i+grid_row][j+grid_col] == board[row][col])
                    return false;
            }

        return true;
    }

比較的簡単で重要な考え方が明確なアルゴリズムを参照してください.http://blog.csdn.net/aivin24/article/details/33346657