题目描述
编写一个程序,通过填充空格来解决数独问题。
一个数独的解法需遵循如下规则:
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ’.’ 表示。
一个数独。
答案被标成红色。
样例
如图
算法1
(dfs)
爆搜模板题吧。
时间复杂度
参考文献
C++ 代码
class Solution {
public:
bool row[9][9], col[9][9], cell[3][3][9];
void solveSudoku(vector<vector<char>>& board) {
memset(row, 0, sizeof row);
memset(col, 0, sizeof col);
memset(cell, 0, sizeof cell);
for (int i = 0; i < 9; i ++)
for (int j = 0; j < 9; j ++)
if (board[i][j] != '.'){
int t = board[i][j] - '1';
row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
}
dfs(board, 0, 0);
}
bool dfs(vector<vector<char>> &board, int x, int y){
if (y == 9) x ++, y = 0;
if (x == 9) return true;
if (board[x][y] != '.') return dfs(board, x, y + 1);
for (int i = 0; i < 9; i ++)
if (!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]){
board[x][y] = '1' + i;
row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
if (dfs(board, x, y + 1)) return true;
board[x][y] = '.';
row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
}
return false;
}
};