解数独
问题描述
编写一个程序，通过填充空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 ‘.’ 表示。
给定的数独序列只包含数字 1-9 和字符 '.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。解决方案
大体思路为从上至下，从左至右依次填表，填表的过程中要时刻保证上述三条性质，若当前位置无数可填则回溯到上一个位置重新选择，当到达右下角的位置时流程结束。
定义三个布尔型的数组:
boolean[] [] row;
boolean[] [] col;
boolean[] [] [] square;row[i] [num] 表示i行num这个数字是否使用过了，col[i] [num] 表示i列num这个数字是否使用过了，square[i] [j] [num] 为第i行j列的那个九宫格中num这个数字是否已经使用过了。
class Solution {
boolean[][] row;
boolean[][] col;
boolean[][][] square;
char[][] board;
public void solveSudoku(char[][] board) {
int N = 9;
// row[i][j] 为第i行j元素是否已经被使用了
this.board = board;
row = new boolean[N][N];
col = new boolean[N][N];
square = new boolean[N / 3][N / 3][N];
// init
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(board[i][j] != '.'){
int num = board[i][j] - '1';
row[i][num] = true;
col[j][num] = true;
square[i / 3][j / 3][num] = true;
}
}
}
dfs(0, 0);
}
// 从i j位置开始是否已经完成任务
public boolean dfs(int i, int j){
if(i == 9){
return true;
}
if(j == 9){
return dfs(i + 1, 0);
}
if(board[i][j] != '.'){
return dfs(i, j + 1);
}
for(int num = 0; num < 9; num++){
if(row[i][num] || col[j][num] || square[i / 3][j / 3][num]){
continue;
}
row[i][num] = true;
col[j][num] = true;
square[i / 3][j / 3][num] = true;
board[i][j] = (char)('1' + num);
if(dfs(i, j + 1)){
return true;
}
board[i][j] = '.';
row[i][num] = false;
col[j][num] = false;
square[i / 3][j / 3][num] = false;
}
return false;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-10-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录