回溯法最经典问题-数独

  |  

摘要: 数独的状态空间树与回溯法

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


在文章 回溯法的思想、设计与分析 中,我们系统了解了回溯法的思想。

我们知道要用回溯法解决问题,首先需要明确问题的解空间,构成解空间的向量可以表示为 $(x_{0}, x_{1}, \cdots, x_{n-1})$。解空间一般描述为树形结构,称为状态空间树。文章 回溯法三种常见的状态空间树:子集树、排列树、满m叉树 中,我们学习了三种常见的状态空间树。

显式约束规定了待求解问题的所有可能的候选解,这些候选解组成了问题实例的解空间。也就是说,显式约束决定了状态空间树。

隐式约束用于判定一个候选解是否为可行解。根据隐式约束,我们可以设计一个判定函数 $p(x_{0},x_{1},\cdots,x_{n-1})$,若该函数为真,则称候选解 $(x_{0},x_{1},\cdots,x_{n-1})$ 是问题的可行解。

本文我们以数独问题,来看一下回溯法解决实际问题的过程:明确显式约束、及其对应的解空间和状态空间树,明确判断可行解的隐式约束,寻找合适的剪枝策略。


36. 有效的数独 (判断是否可行)

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。

  • 数字 1-9 在每一行只能出现一次。
  • 数字 1-9 在每一列只能出现一次。
  • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)

注意:

1
2
3
一个有效的数独(部分已被填充)不一定是可解的。
只需要根据以上规则,验证已经填入的数字是否有效即可。
空白格用 '.' 表示。

提示:

1
2
3
board.length == 9
board[i].length == 9
board[i][j] 是一位数字(1-9)或者 '.'

示例 1:

输入:board =
[[“5”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”]
,[“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”]
,[“.”,”9”,”8”,”.”,”.”,”.”,”.”,”6”,”.”]
,[“8”,”.”,”.”,”.”,”6”,”.”,”.”,”.”,”3”]
,[“4”,”.”,”.”,”8”,”.”,”3”,”.”,”.”,”1”]
,[“7”,”.”,”.”,”.”,”2”,”.”,”.”,”.”,”6”]
,[“.”,”6”,”.”,”.”,”.”,”.”,”2”,”8”,”.”]
,[“.”,”.”,”.”,”4”,”1”,”9”,”.”,”.”,”5”]
,[“.”,”.”,”.”,”.”,”8”,”.”,”.”,”7”,”9”]]
输出:true

示例 2:
输入:board =
[[“8”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”]
,[“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”]
,[“.”,”9”,”8”,”.”,”.”,”.”,”.”,”6”,”.”]
,[“8”,”.”,”.”,”.”,”6”,”.”,”.”,”.”,”3”]
,[“4”,”.”,”.”,”8”,”.”,”3”,”.”,”.”,”1”]
,[“7”,”.”,”.”,”.”,”2”,”.”,”.”,”.”,”6”]
,[“.”,”6”,”.”,”.”,”.”,”.”,”2”,”8”,”.”]
,[“.”,”.”,”.”,”4”,”1”,”9”,”.”,”.”,”5”]
,[“.”,”.”,”.”,”.”,”8”,”.”,”.”,”7”,”9”]]
输出:false
解释:除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

算法:枚举

这是在回溯法求解数独过程中的一步判断,这里判断数独局面是否合法的若干条件,可以视为是回溯法求解数独过程中的隐式条件。

判断过程即枚举起盘的所有位置,若该位置有数字,则判断该数字在同行、同列、同块种是否出现过。

维护三个状态数组:row_state[i][j] 表示第 i 行是否出现数字 j;col_state 表示第 i 列是否出现数字 j,block_state 表示第 i 个块是否出现数字 j。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import numpy as np

def block_id(i, j):
r = i // 3
c = j // 3
return 3 * r + c

class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
row_state = np.array([False] * 9 * 9, np.bool_).reshape(9, 9)
col_state = np.array([False] * 9 * 9, np.bool_).reshape(9, 9)
block_state = np.array([False] * 9 * 9, np.bool_).reshape(9, 9)
for i in range(9):
for j in range(9):
if board[i][j] != ".":
num = int(board[i][j])
if row_state[i][num - 1]:
return False
row_state[i][num - 1] = True
if col_state[j][num - 1]:
return False
col_state[j][num - 1] = True
if block_state[block_id(i, j)][num - 1]:
return False
block_state[block_id(i, j)][num - 1] = True
return True

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
vector<vector<bool> > row_state(9, vector<bool>(9, false));
vector<vector<bool> > col_state(9, vector<bool>(9, false));
vector<vector<bool> > block_state(9, vector<bool>(9, false));
for(int i = 0; i < 9; ++i)
for(int j = 0; j < 9; ++j)
{
if(board[i][j] != '.')
{
if(!row_state[i][board[i][j] - '0' - 1])
row_state[i][board[i][j] - '0' - 1] = true;
else
return false;
if(!col_state[j][board[i][j] - '0' - 1])
col_state[j][board[i][j] - '0' - 1] = true;
else
return false;
if(!block_state[block_id(i, j)][board[i][j] - '0' - 1])
block_state[block_id(i, j)][board[i][j] - '0' - 1] = true;
else
return false;
}
}
return true;
}

private:
int block_id(int i, int j)
{
int r = i / 3;
int c = j / 3;
return 3 * r + c;
}
};

37. 解数独 (返回任一种可行解)

编写一个程序,通过填充空格来解决数独问题。

数独的解法需 遵循如下规则:

  • 数字 1-9 在每一行只能出现一次。
  • 数字 1-9 在每一列只能出现一次。
  • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)

数独部分空格内已填入了数字,空白格用 ‘.’ 表示。

提示:

1
2
3
4
board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据 保证 输入数独仅有一个解

示例 1:

输入:board = [[“5”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”],[“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”],[“.”,”9”,”8”,”.”,”.”,”.”,”.”,”6”,”.”],[“8”,”.”,”.”,”.”,”6”,”.”,”.”,”.”,”3”],[“4”,”.”,”.”,”8”,”.”,”3”,”.”,”.”,”1”],[“7”,”.”,”.”,”.”,”2”,”.”,”.”,”.”,”6”],[“.”,”6”,”.”,”.”,”.”,”.”,”2”,”8”,”.”],[“.”,”.”,”.”,”4”,”1”,”9”,”.”,”.”,”5”],[“.”,”.”,”.”,”.”,”8”,”.”,”.”,”7”,”9”]]
输出:[[“5”,”3”,”4”,”6”,”7”,”8”,”9”,”1”,”2”],[“6”,”7”,”2”,”1”,”9”,”5”,”3”,”4”,”8”],[“1”,”9”,”8”,”3”,”4”,”2”,”5”,”6”,”7”],[“8”,”5”,”9”,”7”,”6”,”1”,”4”,”2”,”3”],[“4”,”2”,”6”,”8”,”5”,”3”,”7”,”9”,”1”],[“7”,”1”,”3”,”9”,”2”,”4”,”8”,”5”,”6”],[“9”,”6”,”1”,”5”,”3”,”7”,”2”,”8”,”4”],[“2”,”8”,”7”,”4”,”1”,”9”,”6”,”3”,”5”],[“3”,”4”,”5”,”2”,”8”,”6”,”1”,”7”,”9”]]
解释:输入的数独如上图所示,唯一有效的解决方案如下所示:

算法:回溯

  • 显式约束:每个位置有 9 种选择,一共有 81 个位置,状态空间树构成一个 81 层的满 9 叉树。
  • 隐式约束:数字不能再同一行、同一列、同一块出现过。

代码 (python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import numpy as np

def block_id(i, j):
r = i // 3
c = j // 3
return 3 * r + c

class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
self.row_state = np.array([False] * 9 * 9, np.bool_).reshape(9, 9)
self.col_state = np.array([False] * 9 * 9, np.bool_).reshape(9, 9)
self.block_state = np.array([False] * 9 * 9, np.bool_).reshape(9, 9)
for i in range(9):
for j in range(9):
if board[i][j] != ".":
num = int(board[i][j])
self.row_state[i][num - 1] = True
self.col_state[j][num - 1] = True
self.block_state[block_id(i, j)][num - 1] = True
return self.dfs(board, 0, 0)

def check(self, board, i, j, num):
# 隐式约束
if self.row_state[i][num - 1]:
return False
if self.col_state[j][num - 1]:
return False
if self.block_state[block_id(i, j)][num - 1]:
return False
return True

def dfs(self, board, i, j):
if i == 9:
return True
nxt_i = (i * 9 + j + 1) // 9
nxt_j = (i * 9 + j + 1) % 9
if board[i][j] != ".":
return self.dfs(board, nxt_i, nxt_j)
for num in range(1, 10):
if not self.check(board, i, j, num):
continue
board[i][j] = str(num)
self.row_state[i][num - 1] = True
self.col_state[j][num - 1] = True
self.block_state[block_id(i, j)][num - 1] = True
if self.dfs(board, nxt_i, nxt_j):
return True
board[i][j] = "."
self.row_state[i][num - 1] = False
self.col_state[j][num - 1] = False
self.block_state[block_id(i, j)][num - 1] = False
return False

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
row_state = vector<vector<bool>>(9, vector<bool>(9, false));
col_state = vector<vector<bool>>(9, vector<bool>(9, false));
block_state = vector<vector<bool>>(9, vector<bool>(9, false));
for(int i = 0; i < 9; ++i)
for(int j = 0; j < 9; ++j)
if(board[i][j] != '.')
{
int num = board[i][j] - '0';
row_state[i][num - 1] = true;
col_state[j][num - 1] = true;
block_state[block_id(i, j)][num - 1] = true;
}
dfs(board, 0, 0);
}

private:
vector<vector<bool>> row_state;
vector<vector<bool>> col_state;
vector<vector<bool>> block_state;
int block_id(int i, int j)
{
int r = i / 3;
int c = j / 3;
return 3 * r + c;
}

bool check(int i, int j, int num)
{
// 隐式约束
if(row_state[i][num - 1])
return false;
if(col_state[j][num - 1])
return false;
if(block_state[block_id(i, j)][num - 1])
return false;
return true;
}

bool dfs(vector<vector<char>>& board, int i, int j)
{
if(i == 9)
return true;
int nxt_i = (i * 9 + j + 1 ) / 9;
int nxt_j = (i * 9 + j + 1 ) % 9;
if(board[i][j] != '.')
return dfs(board, nxt_i, nxt_j);
for(int num = 1; num <= 9; ++num)
{
if(!check(i, j, num))
continue;
board[i][j] = '0' + num;
row_state[i][num - 1] = true;
col_state[j][num - 1] = true;
block_state[block_id(i, j)][num - 1] = true;
if(dfs(board, nxt_i, nxt_j))
return true;
board[i][j] = '.';
row_state[i][num - 1] = false;
col_state[j][num - 1] = false;
block_state[block_id(i, j)][num - 1] = false;
}
return false;
}
};

剪枝、搜索顺序

在构成状态空间的 81 层满 9 叉树中,不满足隐式约束的分支不会搜索到,因此隐式约束是一种可行性剪枝。

我们希望剪枝尽可能发生在浅层,这样就可以减少很多对无效状态的搜索。在选择下一个填写的位置时,之前是直接按从小到大顺序来。现在选择可填数字最少的坐标作为下一个要填数的位置。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
row_state = vector<vector<bool>>(9, vector<bool>(9, false));
col_state = vector<vector<bool>>(9, vector<bool>(9, false));
block_state = vector<vector<bool>>(9, vector<bool>(9, false));
for(int i = 0; i < 9; ++i)
for(int j = 0; j < 9; ++j)
if(board[i][j] != '.')
{
int num = board[i][j] - '0';
row_state[i][num - 1] = true;
col_state[j][num - 1] = true;
block_state[block_id(i, j)][num - 1] = true;
}
int nxt_i = -1, nxt_j = -1;
get_nxt(board, nxt_i, nxt_j);
dfs(board, nxt_i, nxt_j);
}

private:
vector<vector<bool>> row_state;
vector<vector<bool>> col_state;
vector<vector<bool>> block_state;
vector<vector<vector<bool>>> used;

void get_nxt(const vector<vector<char>>& board, int& nxt_i, int& nxt_j)
{
int min_choose = 10;
for(int i = 0; i < 9; ++i)
for(int j = 0; j < 9; ++j)
{
if(board[i][j] != '.')
continue;
int used = 0;
for(int num = 1; num <= 9; ++num)
{
if(!check(i, j, num))
used |= (1 << (num - 1));
}
int choose = 9 - ones(used);
if(choose < min_choose)
{
min_choose = choose;
nxt_i = i;
nxt_j = j;
}
}
}

int ones(int x)
{
int ans = 0;
while(x > 0)
{
if(x & 1)
++ans;
x >>= 1;
}
return ans;
}

int block_id(int i, int j)
{
int r = i / 3;
int c = j / 3;
return 3 * r + c;
}

bool check(int i, int j, int num)
{
// 隐式约束
if(row_state[i][num - 1])
return false;
if(col_state[j][num - 1])
return false;
if(block_state[block_id(i, j)][num - 1])
return false;
return true;
}

bool dfs(vector<vector<char>>& board, int i, int j)
{
if(i == -1)
return true;
for(int num = 1; num <= 9; ++num)
{
if(!check(i, j, num))
continue;
board[i][j] = '0' + num;
row_state[i][num - 1] = true;
col_state[j][num - 1] = true;
block_state[block_id(i, j)][num - 1] = true;
int nxt_i = -1, nxt_j = -1;
get_nxt(board, nxt_i, nxt_j);
if(dfs(board, nxt_i, nxt_j))
return true;
board[i][j] = '.';
row_state[i][num - 1] = false;
col_state[j][num - 1] = false;
block_state[block_id(i, j)][num - 1] = false;
}
return false;
}
};

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import numpy as np

def block_id(i, j):
r = i // 3
c = j // 3
return 3 * r + c


def ones(x):
ans = 0
while x > 0:
if (x & 1) == 1:
ans += 1
x >>= 1
return ans


class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
self.row_state = np.array([False] * 9 * 9, np.bool_).reshape(9, 9)
self.col_state = np.array([False] * 9 * 9, np.bool_).reshape(9, 9)
self.block_state = np.array([False] * 9 * 9, np.bool_).reshape(9, 9)
for i in range(9):
for j in range(9):
if board[i][j] != ".":
num = int(board[i][j])
self.row_state[i][num - 1] = True
self.col_state[j][num - 1] = True
self.block_state[block_id(i, j)][num - 1] = True
nxt_i, nxt_j = self.get_nxt(board)
return self.dfs(board, nxt_i, nxt_j)

def get_nxt(self, board):
min_choose = 10
nxt_i = nxt_j = -1
for i in range(9):
for j in range(9):
if board[i][j] != ".":
continue
used = 0
for num in range(1, 10):
if not self.check(board, i, j, num):
used |= (1 << (num - 1))
choose = 9 - ones(used)
if choose < min_choose:
min_choose = choose
nxt_i = i
nxt_j = j
return nxt_i, nxt_j

def check(self, board, i, j, num):
# 隐式约束
if self.row_state[i][num - 1]:
return False
if self.col_state[j][num - 1]:
return False
if self.block_state[block_id(i, j)][num - 1]:
return False
return True

def dfs(self, board, i, j):
if i == -1:
return True
for num in range(1, 10):
if not self.check(board, i, j, num):
continue
board[i][j] = str(num)
self.row_state[i][num - 1] = True
self.col_state[j][num - 1] = True
self.block_state[block_id(i, j)][num - 1] = True
nxt_i, nxt_j = self.get_nxt(board)
if self.dfs(board, nxt_i, nxt_j):
return True
board[i][j] = "."
self.row_state[i][num - 1] = False
self.col_state[j][num - 1] = False
self.block_state[block_id(i, j)][num - 1] = False
return False

Share