0%

[Leetcode]37. Sudoku Solver(C++)

题目描述

题目链接:37. Sudoku Solver

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.

例子

见官网例子。

Constraints

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit or '.'.
  • It is guaranteed that the input board has only one solution.

解题思路

用回溯法暴力递归搜索所有解即可。需要对每一个方块、每一行、每一列都用一个向量数字的使用情况。代码如下:

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
#include <vector>

class Solution {
public:
void solveSudoku(std::vector<std::vector<char>>& board) {
std::vector<std::vector<bool>> used(27, std::vector<bool>(10, false));

for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
int block_index = int(i / 3.0) * 3 + j / 3;
int row_index = 9 + i;
int col_index = 18 + j;

if (board[i][j] != '.') {
int index = board[i][j] - '0';
used[block_index][index] = true;
used[row_index][index] = true;
used[col_index][index] = true;
}
}
}

solve(board, used, 0, 0);
}

private:
bool solve(std::vector<std::vector<char>>& board,
std::vector<std::vector<bool>>& used, int row, int col) {
// reach the end of board
if (row == 9) return true;

if (board[row][col] != '.') {
int r = row;
int c = col;
if (c == 8) {
r++;
c = 0;
} else {
c++;
}

if (solve(board, used, r, c)) {
return true;
} else {
return false;
}
}

// calcualte index of hashable
int block_index = int(row / 3.0) * 3 + col / 3;

int row_index = 9 + row;
int col_index = 9 * 2 + col;

for (int i = 1; i <= 9; ++i) {
if (!used[block_index][i] && !used[row_index][i] &&
!used[col_index][i]) {
used[block_index][i] = true;
used[row_index][i] = true;
used[col_index][i] = true;
board[row][col] = '0' + i;
int r = row;
int c = col;
if (c == 8) {
r++;
c = 0;
} else {
c++;
}

if (solve(board, used, r, c)) {
return true;
}

used[block_index][i] = false;
used[row_index][i] = false;
used[col_index][i] = false;
board[row][col] = '.';
}
}

return false;
}
};
  • 时间复杂度: O(n!)
  • 空间复杂度: O(n^2)

GitHub 代码同步地址: 37.SudokuSolver.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions