3c2574886ed4567ee67c619b019b0dec
(难度Hard)Problem 37. Sudoku Solver(解数独)

链接

Sudoku Solver - LeetCode

难度等级

Hard

题干

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

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
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...

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.

题意

题意不用多说,想必大家都能看明白,其实就是上一题的进阶版。在上一题当中我们实现了判断一个数独是否合法,在这题中,我们则需要解开这个数独。

需要注意的是,题目当中限定了这个数独只有唯一解,所以不用担心多解的问题。

题解

解法一 暴力搜索

这道题暴力是不可能暴力的,直接暴力一定会超时,因为有一个空就有九种可能,只要几个空,就可以把复杂度增加到无法承受的地步。

但是尽管如此,我们还是有必要写一下暴力的代码。因为对于初学者来说,这是一道非常经典的搜索问题。

解数独的本质和八皇后一样,是一个回溯问题,我们枚举了当前的位置之后,如果找不到解,需要把当前的位置撤销。这个是整个搜索算法的基础,后续的优化方法,都是在这个基础上的。

基本的回溯怎么写呢?

其实说白了很简单,有一个现成的套路,往里面套即可。

判断是否搜索到结果
如有,返回
做下一次搜索的准备
递归进行下一步搜索
回溯(清除这一步的准备)

这么几行就是大名鼎鼎的回溯法,让我们来看下套入这题当中的伪代码

    void dfs(vector<vector<char>> board, int n) {
          // n表示当前枚举的棋盘的位置,超过81说明整个棋盘已经填满
        if (n == 81) return ;
          // 计算n所代表的棋盘坐标
        int x = n / 9;
        int y = n % 9;
          // 如果棋盘已有棋子,直接递归下一个位置
        if (board[x][y] != '.') dfs(board, n+1);
          // 枚举当前位置可以放置的棋子
        for (int i = 0; i < 9; i++) {
            char ch = '1' + i;
            board[x][y] = ch;
              // 递归
            if (isValidSudoku(board)) {
                dfs(board, n+1);
            }
              // 回溯,即清除这一步所放的棋子
            board[x][y] = '.';
        }
    }

    void solveSudoku(vector<vector<char>>& board) {
        dfs(board, 0);
    }

但是很遗憾,这么做会超时,虽然我们在每次枚举之后都做了合法判断,减去了不少冗余的情况,但时间复杂度还是不能接受。两个原因导致了这一情况,一个是我们在放置棋子的时候没有过滤,枚举了很多非法棋子,另一个原因是我们每次的合法判断都需要遍历整个棋盘,消耗太大。

我们下一步的目标就是针对这两点做优化。

解法二 搜索剪枝

首先,我们怎么对行列剪枝呢?

其实很好办,还记得我们上一题当中判断合法数独的时候,是怎么处理行列当中出现的元素的个数的吗?我们用了hashtable,没错,在这题当中我们依然可以如此操作。

首先我们申请两个二维数组,作为hashtable,一个叫做row一个叫做col,顾名思义一个hash的行元素,一个hash的列元素。

其中row[i][j]表示第i行中j出现的次数,同理,col[i][j]表示第i列,j元素出现的次数。

有了这个hashtable之后,我们只需要在枚举的时候判断一下row和col中当前的行和列这个元素出现的次数为0,这样我们就减去了大量枚举的工作。

但是只是这样还不够,我们还必须考虑到九宫格匹配。一开始的时候我是专门写了一个函数来计算九宫格是否匹配。

```
// x,y表示放置的位置,k表示放置的元素
bool check(int x, int y, int k) {
su[x][y] = k;
// 计算得到九宫格左上角的点
int tx = x / 3 * 3;

top Created with Sketch.