公众号:
bigsai回复进群加入打卡
有效的数独
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。
示例 1:
输入:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: true
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
示例 2:
输入:
[
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: false
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
解释:
除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
说明:
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
给定数独序列只包含数字 1-9 和字符 ‘.’ 。
给定数独永远是 9x9 形式的。
分析
本题的话就是要选择合理的方式去判断是否有效。是否有效需要满足三个维度：
- 行是否有效
- 列是否有效
- 3x3的格子内是否有效。
而每一个维度考虑的问题都是有相关性的，例如这一行的1-9每个数字只能出现一次，这一列也是，这个3x3也是。这样的话我们就可以通过三个boolean数组来判断各自对应的区间是否满足。因为每个区间每个数字最多只能出现一次，所以判断所有次数满足条件即可，一旦不满足就停止返回false。
当然这个有点麻烦的就是需要求当前是在第几个3x3的小方格内，经过思考(i/3)*3+j/3这个表达式可以很好的表示。
实现代码为：
public boolean isValidSudoku(char[][] board) { boolean hang[][]=new boolean[9][9];//第一个是 9个坑，第二个是数字位置
boolean lie[][]=new boolean[9][9];
boolean fangge[][]=new boolean[9][9];
for(int i=0;i<board.length;i++)
{ for(int j=0;j<board[0].length;j++) { if(board[i][j]=='.') {continue;} int num=board[i][j]-'1'; if(hang[i][num]||lie[j][num]||fangge[(i/3)*3+j/3][num]) { return false; } else { hang[i][num]=true; lie[j][num]=true; fangge[(i/3)*3+j/3][num]=true; } }
}
return true; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
解数独
题目描述：
编写一个程序，通过填充空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。
一个数独。
答案被标成红色。
提示：
给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。
分析
此题相比上一题难度稍微大一些，是一个八皇后问题的变种，对于上一题我想我们已经知道怎么判断这个是否满足规则——使用三个boolean数组判断。
但是，这一题有难度的就是需要我们手动放数据进去，手动去试探，并且每一步放置之后对后面都有影响。我们该如何思考这种问题呢？
dfs回溯，八皇后问题其实就是典型的回溯过程，而这种二维的回溯需要考虑一些问题，我们对于每一行每一行考虑。 每一行已经预有一些数据事先标记，在从开始试探放值，满足条件后向下递归试探。一直到结束如果都满足那么就可以结束返回数组值。
对于八皇后问题后面还会出一篇细讲，这里的话有两点需要注意的在这里提一下：
- 用二维两个参数进行递归回溯判断起来谁加谁减比较麻烦，所以我们用一个参数
index用它来计算横纵坐标进行转换，这样就减少二维递归的一些麻烦。 - 回溯是一个来回的过程，在回来的过程正常情况需要将数据改回去，但是如果已经知道结果就没必要再该回去可以直接停止放置回溯造成值的修改(这里我用了一个isfinish的boolean类型进行判断)。
具体ac代码为：
boolean isfinish=false;
boolean hang[][]=new boolean[9][10];//第一个是 9个坑，第二个是数字位置
boolean lie[][]=new boolean[9][10];
boolean fangge[][]=new boolean[9][10];
public void solveSudoku(char[][] board) {
//首先遍历一遍 将已有元素的行列信息提前做处理
for(int i=0;i<board.length;i++)
{ for(int j=0;j<board[0].length;j++) { if(board[i][j]=='.') {continue;} int k=board[i][j]-'0'; hang[i][k]=true; lie[j][k]=true; fangge[(i/3)*3+j/3][k]=true; }
} dfs(0,board); }
private void dfs( int index, char[][] board) {
if(isfinish) return;//已有结果不需要再计算
if(index==81) {//到达最后一个前面都满足条件说明可以停止了
isfinish=true;
return;
}
int i=index/9;//行
int j=index%9;//列
if(board[i][j]!='.')//已经有数字
{
dfs( index+1, board);
}
else {//此处需要补充数字
for(int k=1;k<10;k++)
{ //如果不满足直接跳过 if(hang[i][k]||lie[j][k]||fangge[(i/3)*3+j/3][k]) {continue;} //满足临时试探修改 进行回溯 board[i][j]=(char) (k+'0'); hang[i][k]=true; lie[j][k]=true; fangge[(i/3)*3+j/3][k]=true; //递归回溯 dfs( index+1, board); //递归完成后需要复原，如果结束了不需要复原直接停止 if(isfinish)return; board[i][j]='.'; hang[i][k]=false; lie[j][k]=false; fangge[(i/3)*3+j/3][k]=false;
}
}
}
- 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
结语
好啦，本次打卡结束，对于八皇后问题是一个经典的回溯递归问题，不久就会出一篇相关内容问题的具体分析，敬请来公众号bigsai分享。如果想加入打卡还请加笔者公众号bigsai 回复进群。一起打卡，回复bigsai获取5G的pdf学习资源。
别忘了下方一键三联哦！
文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。
原文链接：bigsai.blog.csdn.net/article/details/108995426