题目

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…

分析

与36 Valid Sudoku本质相同的题目，上一题要求判定所给九宫格能否满足数独要求，本题要求给定唯一解。

所采取基本方法 — 遍历 ， 遍历整个9*9宫格每一元素，对所有的 ′.′ 分别判定1~9是否满足要求，对于判定，我们采用上一题的思路，但是此时只需判定当前位置所在行、列、及3*3块是否满足要求即可。

AC代码

class Solution {

private:

    const int N = 9;

public:

    void solveSudoku(vector<vector<char>>& board) {

        if (board.empty())

            return;

        isValidSudoku(board);

    }

    bool isValidSudoku(vector<vector<char> > &board)

    {

        //所给非空九宫格

        for (int r = 0; r < N; r++)

        {

            for (int c = 0; c < N; c++)

            {

                //如果当前为待填充数字

                if ('.' == board[r][c])

                {

                    for (int i = 1; i <= 9; i++)

                    {

                        board[r][c] = i + '0';

                            //判断当前填充数字是否合理

                        if (judge(board, r, c))

                        {

                            if (isValidSudoku(board))

                                return true;

                        }//if

                        board[r][c] = '.';

                    }//for

                    return false;

                }//if

            }//for

        }//for

    }//isValid

    //判断当前row，col中所填数字是否合理，只需要判断当前行，当前列，以及当前所在的3*3块

    bool judge(vector<vector<char> > &board, int row, int col)

    {

        //(1)判断当前行

        for (int j = 0; j < N; j++)

        {

            if (col != j && board[row][j] == board[row][col])

                return false;

        }

        //(2)判断当前列

        for (int i = 0; i < N; i++)

        {

            if (row != i && board[i][col] == board[row][col])

                return false;

        }//for

        //(3)判断当前3*3块

        for (int i = row / 3 * 3; i < (row / 3 + 1) * 3; ++i)

        {

            for (int j = col / 3 * 3; j < (col / 3 + 1) * 3; ++j)

            {

                if (row != i && j != col && board[row][col] == board[i][j])

                    return false;

            }//for

        }//for

        return true;

    }

};

GitHub测试程序源码