Description#
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 digits
1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
The '.' character indicates empty cells.
Example 1:
Input: 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"]]
Output: [["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"]]
Explanation: The input board is shown above and the only valid solution is shown below:
Constraints:
board.length == 9board[i].length == 9board[i][j] is a digit or '.'.- It is guaranteed that the input board has only one solution.
Solutions#
Solution 1: Backtracking#
We use arrays row, col, and box to record whether a number has appeared in each row, each column, and each 3x3 grid respectively. If the number i has appeared in the rth row, the cth column, and the bth 3x3 grid, then row[r][i], col[c][i], and box[b][i] are all true.
We traverse each empty space in board, enumerate the numbers v that it can fill in. If v has not appeared in the current row, the current column, and the current 3x3 grid, then we can try to fill in the number v and continue to search for the next empty space. If we search to the end and all spaces are filled, it means that a feasible solution has been found.
The time complexity is $O(9^{81})$, and the space complexity is $O(9^2)$.
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
| class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
def dfs(k):
nonlocal ok
if k == len(t):
ok = True
return
i, j = t[k]
for v in range(9):
if row[i][v] == col[j][v] == block[i // 3][j // 3][v] == False:
row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True
board[i][j] = str(v + 1)
dfs(k + 1)
row[i][v] = col[j][v] = block[i // 3][j // 3][v] = False
if ok:
return
row = [[False] * 9 for _ in range(9)]
col = [[False] * 9 for _ in range(9)]
block = [[[False] * 9 for _ in range(3)] for _ in range(3)]
t = []
ok = False
for i in range(9):
for j in range(9):
if board[i][j] == '.':
t.append((i, j))
else:
v = int(board[i][j]) - 1
row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True
dfs(0)
|
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
| class Solution {
private boolean ok;
private char[][] board;
private List<Integer> t = new ArrayList<>();
private boolean[][] row = new boolean[9][9];
private boolean[][] col = new boolean[9][9];
private boolean[][][] block = new boolean[3][3][9];
public void solveSudoku(char[][] board) {
this.board = board;
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') {
t.add(i * 9 + j);
} else {
int v = board[i][j] - '1';
row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
}
}
}
dfs(0);
}
private void dfs(int k) {
if (k == t.size()) {
ok = true;
return;
}
int i = t.get(k) / 9, j = t.get(k) % 9;
for (int v = 0; v < 9; ++v) {
if (!row[i][v] && !col[j][v] && !block[i / 3][j / 3][v]) {
row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
board[i][j] = (char) (v + '1');
dfs(k + 1);
row[i][v] = col[j][v] = block[i / 3][j / 3][v] = false;
}
if (ok) {
return;
}
}
}
}
|
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
| using pii = pair<int, int>;
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
bool row[9][9] = {false};
bool col[9][9] = {false};
bool block[3][3][9] = {false};
bool ok = false;
vector<pii> t;
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') {
t.push_back({i, j});
} else {
int v = board[i][j] - '1';
row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
}
}
}
function<void(int k)> dfs = [&](int k) {
if (k == t.size()) {
ok = true;
return;
}
int i = t[k].first, j = t[k].second;
for (int v = 0; v < 9; ++v) {
if (!row[i][v] && !col[j][v] && !block[i / 3][j / 3][v]) {
row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
board[i][j] = v + '1';
dfs(k + 1);
row[i][v] = col[j][v] = block[i / 3][j / 3][v] = false;
}
if (ok) {
return;
}
}
};
dfs(0);
}
};
|
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
| func solveSudoku(board [][]byte) {
var row, col [9][9]bool
var block [3][3][9]bool
var t [][2]int
ok := false
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
if board[i][j] == '.' {
t = append(t, [2]int{i, j})
} else {
v := int(board[i][j] - '1')
row[i][v], col[j][v], block[i/3][j/3][v] = true, true, true
}
}
}
var dfs func(int)
dfs = func(k int) {
if k == len(t) {
ok = true
return
}
i, j := t[k][0], t[k][1]
for v := 0; v < 9; v++ {
if !row[i][v] && !col[j][v] && !block[i/3][j/3][v] {
row[i][v], col[j][v], block[i/3][j/3][v] = true, true, true
board[i][j] = byte(v + '1')
dfs(k + 1)
row[i][v], col[j][v], block[i/3][j/3][v] = false, false, false
}
if ok {
return
}
}
}
dfs(0)
}
|
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
| public class Solution {
public void SolveSudoku(char[][] board) {
this.board = new ushort?[9,9];
for (var i = 0; i < 9; ++i)
{
for (var j = 0; j < 9; ++j)
{
if (board[i][j] != '.')
{
this.board[i, j] = (ushort) (1 << (board[i][j] - '0' - 1));
}
}
}
if (SolveSudoku(0, 0))
{
for (var i = 0; i < 9; ++i)
{
for (var j = 0; j < 9; ++j)
{
if (board[i][j] == '.')
{
board[i][j] = '0';
while (this.board[i, j].Value != 0)
{
board[i][j] = (char)(board[i][j] + 1);
this.board[i, j] >>= 1;
}
}
}
}
}
}
private ushort?[,] board;
private bool ValidateHorizontalRule(int row)
{
ushort temp = 0;
for (var i = 0; i < 9; ++i)
{
if (board[row, i].HasValue)
{
if ((temp | board[row, i].Value) == temp)
{
return false;
}
temp |= board[row, i].Value;
}
}
return true;
}
private bool ValidateVerticalRule(int column)
{
ushort temp = 0;
for (var i = 0; i < 9; ++i)
{
if (board[i, column].HasValue)
{
if ((temp | board[i, column].Value) == temp)
{
return false;
}
temp |= board[i, column].Value;
}
}
return true;
}
private bool ValidateBlockRule(int row, int column)
{
var startRow = row / 3 * 3;
var startColumn = column / 3 * 3;
ushort temp = 0;
for (var i = startRow; i < startRow + 3; ++i)
{
for (var j = startColumn; j < startColumn + 3; ++j)
{
if (board[i, j].HasValue)
{
if ((temp | board[i, j].Value) == temp)
{
return false;
}
temp |= board[i, j].Value;
}
}
}
return true;
}
private bool SolveSudoku(int i, int j)
{
while (true)
{
if (j == 9)
{
++i;
j = 0;
}
if (i == 9)
{
return true;
}
if (board[i, j].HasValue)
{
++j;
}
else
{
break;
}
}
ushort stop = 1 << 9;
for (ushort t = 1; t != stop; t <<= 1)
{
board[i, j] = t;
if (ValidateHorizontalRule(i) && ValidateVerticalRule(j) && ValidateBlockRule(i, j))
{
if (SolveSudoku(i, j + 1))
{
return true;
}
}
}
board[i, j] = null;
return false;
}
}
|
