78 lines
2.7 KiB
C++
78 lines
2.7 KiB
C++
#include "s0037_sudoku_solver.hpp"
|
|
|
|
// 返回结果为当前传递进去的数独是否存在解
|
|
bool S0037::recusiveSolveSudoku(vector<vector<char>> &board,
|
|
vector<unordered_map<char, bool>> &rows,
|
|
vector<unordered_map<char, bool>> &cols,
|
|
vector<unordered_map<char, bool>> &grids,
|
|
int row, int col) {
|
|
int size = board.size();
|
|
// 边界校验
|
|
if (col == size) {
|
|
// 进入下一行
|
|
col = 0;
|
|
row++;
|
|
// 填充完成，返回 True
|
|
if (row == size) {
|
|
return true;
|
|
}
|
|
}
|
|
// 如果不为空则跳过，填充下一个
|
|
if (board[row][col] != '.') {
|
|
return recusiveSolveSudoku(board, rows, cols, grids, row, col + 1);
|
|
} else { // 否则开始填充
|
|
// 尝试填充 1 ~ 9
|
|
for (char num{'1'}; num <= '9'; ++num) {
|
|
int gridIndex = static_cast<int>(floor(row / 3)) +
|
|
3 * static_cast<int>(floor(col / 3));
|
|
// 如果这个数字还没有出现过
|
|
if (!(rows[row].count(num) == 1 || cols[col].count(num) == 1 ||
|
|
grids[gridIndex].count(num) == 1)) {
|
|
// 先把这个数字填进去
|
|
rows[row][num] = true;
|
|
cols[col][num] = true;
|
|
grids[gridIndex][num] = true;
|
|
board[row][col] = num;
|
|
// 然后试试看填进去后下一个能不能解
|
|
// 如果下一个能解的话，现在这个肯定能解
|
|
if (recusiveSolveSudoku(board, rows, cols, grids, row, col + 1)) {
|
|
return true;
|
|
}
|
|
// 如果不能解，那么说明这个数字填错了，把它重新设为空，然后尝试下一个数字
|
|
board[row][col] = '.';
|
|
rows[row].erase(num);
|
|
cols[col].erase(num);
|
|
grids[gridIndex].erase(num);
|
|
}
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
void S0037::solveSudoku(vector<vector<char>> &board) {
|
|
// 每个行/列/单元格中某个数字是否出现过
|
|
vector<unordered_map<char, bool>> rows;
|
|
vector<unordered_map<char, bool>> cols;
|
|
vector<unordered_map<char, bool>> grids;
|
|
// 初始化
|
|
int size = board.size();
|
|
for (int i{0}; i < size; ++i) {
|
|
rows.push_back(unordered_map<char, bool>{});
|
|
cols.push_back(unordered_map<char, bool>{});
|
|
grids.push_back(unordered_map<char, bool>{});
|
|
}
|
|
for (int row{0}; row < size; ++row) {
|
|
for (int col{0}; col < size; ++col) {
|
|
if (board[row][col] != '.') {
|
|
rows[row][board[row][col]] = true;
|
|
cols[col][board[row][col]] = true;
|
|
int gridIndex = static_cast<int>(floor(row / 3)) +
|
|
3 * static_cast<int>(floor(col / 3));
|
|
grids[gridIndex][board[row][col]] = true;
|
|
}
|
|
}
|
|
}
|
|
// 从 (0, 0) 开始递归求解
|
|
recusiveSolveSudoku(board, rows, cols, grids, 0, 0);
|
|
}
|