LeetCode37. Sudoku Solver（递归 / 回溯）

LeetCode37. Sudoku Solver（递归 / 回溯）

• Hard
• Accepted：123,186
• Submissions：340,225

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character '.'.

A sudoku puzzle...

...and its solution numbers marked in red.

Note:

• The given board contain only digits 1-9 and the character '.'.
• You may assume that the given Sudoku puzzle will have a single unique solution.
• The given board size is always 9x9.

---

链接

https://leetcode.com/problems/sudoku-solver

题意

解决数独问题，给定一个9*9的棋盘，其中一些已经填好数字，未填的用.表示，现要求填写剩余空的方格，要求每行每列和每个3*3的小棋盘都为1到9。

题解

采取的策略是对每个空的方格都用1~9逐个填充，看是否合法，直到填完所有的空格，如果填的数字不符合要求那么就回溯使用别的数字继续填充。

关键在于如何判断行列以及3*3的小棋盘是否合法。

假设当前填充的方格所在位置为(row, col)，我们使用一个for循环，i从0到8，那么行和列的判断很简单，遍历board[row][i]和board[i][col]即可，对于3*3的小棋盘我们可以先得到当前其左上角的位置为(row / 3 * 3, col / 3 * 3)，然后遍历3*3的小棋盘就是(row / 3 * 3 + i / 3, col / 3 * 3 + i % 3)。

因为我们只需要得到一个解，所以solve函数是bool类型的，如果当前board[i][j]设置为某个字符数字后又回溯为.，那么就返回false。当n*m的棋盘都不为.时返回true。

没有对此进行额外的剪枝，时间复杂度为$O(9^m)$，m为棋盘中.的数量。

代码

• Runtime: 16 ms, faster than 62.89% of C++ online submissions for Sudoku Solver.
• Memory Usage: 8.7 MB, less than 94.38% of C++ online submissions for Sudoku Solver.

class Solution {
private:
    int n, m;
    bool solve(vector<vector<char>>& board)
    {
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (board[i][j] == '.')
                {
                    for (char c = '1'; c <= '9'; ++c)
                    {
                        if (check(board, i, j, c))
                        {
                            board[i][j] = c;
                            if (solve(board))
                                return true;
                            board[i][j] = '.'; // 回溯
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    bool check(vector<vector<char>>& board, int row, int col, char c)
    {
        for (int i = 0; i < 9; ++i)
        {
            int x = row / 3 * 3 + i / 3;
            int y = col / 3 * 3 + i % 3;
            if (board[row][i] == c || board[i][col] == c || board[x][y] == c)
                return false;
        }
        return true;
    }
public:
    void solveSudoku(vector<vector<char>>& board) {
        if (board.empty())
            return ;
        n = board.size(), m = board[0].size();
        solve(board);
    }
};

参考

• Straight Forward Java Solution Using Backtracking

---

The end.
2019年4月15日 星期一