题目描述
题目链接: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 93x3
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.
解题思路
用回溯法暴力递归搜索所有解即可。需要对每一个方块、每一行、每一列都用一个向量数字的使用情况。代码如下:
#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