MENU

LeetCode37. Sudoku Solver(递归 / 回溯)

2019 年 04 月 15 日 • 阅读: 938 • LeetCode阅读设置

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 '.'.

img
A sudoku puzzle...

img
...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);
    }
};

参考


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