36. 有效的数独 Valid Sudoku
题目
请你判断一个 9 x 9 的数独是否有效。
只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
-
数字 1-9 在每一行只能出现一次。
-
数字 1-9 在每一列只能出现一次。
-
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
注意：
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 ’.’ 表示。
示例
示例 1：
输入：board =
[["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
示例 2：
输入：board =
[["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
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 ‘.’
思路
其实就是验证满足上面的 3 个条件：
1）每一行
2）每一列
3）每一个小正方体
java 实现
public boolean isValidSudoku(char[][] board) {
//1. 每一行
for(int i = 0; i < 9; i++) {
char[] row = board[i];
if(!isValid(row)) {
return false;
}
}
//2. 每一列
for(int i = 0; i < 9; i++) {
char[] columns = getColumns(board, i);
if(!isValid(columns)) {
return false;
}
}
//3. 每一个小的 9 宫格
for(int i = 0; i < 9; i++) {
char[] box = getSubBox(board, i);
if(!isValid(box)) {
return false;
}
}
return true;
}
/**
* 获取小9宫格
*
* 规律：
*
* 0 00 01 02
* 10 11 12
* 20 21 22
*
* 2 （第二行，第一个九宫格）
*
* 根据 index 获取对应的行+列信息
*
* row: 0 1 2
* 3 4 5
* 6 7 8
*
* @param board
* @param index
* @return
*/
private char[] getSubBox(char[][] board, int index) {
char[] box = new char[9];
int size = 0;
int rowNum = index/3;
int columnNum = index%3;
for(int i = rowNum*3; i < rowNum*3+3; i++) {
for(int j = columnNum*3; j < columnNum*3+3; j++) {
box[size++] = board[i][j];
}
}
return box;
}
/**
* 获取指定的列
* @param board
* @param columnIndex
* @return
*/
private char[] getColumns(char[][] board, int columnIndex) {
char[] columns = new char[9];
int size = 0;
for(int i = 0; i < 9; i++) {
char[] rows = board[i];
columns[size++] = rows[columnIndex];
}
return columns;
}
/**
* 只能包含：. 1-9
*
* 不能重复 主要是这个
* @param chars
* @return
*/
private boolean isValid(char[] chars) {
char[] nums = new char[9];
int numSize = 0;
for(char c : chars) {
if(!isValidChar(c)) {
return false;
}
// 忽略处理 .
if('.' == c) {
continue;
}
// 数据重复
if(contains(nums, c)) {
return false;
}
nums[numSize++] = c;
}
// 合法
return true;
}
/**
* 合法的值：. 或者 1-9
* @param c
* @return
*/
private boolean isValidChar(char c) {
if('.' == c) {
return true;
}
if('1' <= c && c <= '9') {
return true;
}
return false;
}
/**
* 是否包含
* @param chars
* @param target
* @return
*/
private boolean contains(char[] chars, char target) {
for(char c : chars) {
if(target == c) {
return true;
}
}
return false;
}
37. 解数独
题目
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ’.’ 表示。
例子
示例 1：
输入：board = [["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"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
提示
提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 ‘.’
题目数据 保证 输入数独仅有一个解
V1-基本回溯版本
思路
我们可以遍历 [i,j] 位置，如果位置为 ‘.’，在位置上尝试添加 1-9 的数字，然后判断是否合法(T36 解法)。
如果合法，则递归判断是否为已解决。
如果已解决，则直接返回结果；如果没有，则回溯。
java 实现
/**
* 基本思路：
*
* 1. 这一题应该需要回溯？
*
* 2. i,j 位置的元素。首先通过 行、列、小九宫格，来把一个位置可行的元素过滤出来，放在 set 中。
*
* 3. 尝试在这个位置放入一个元素，然后依次放剩下的。如果可以，则可行，如果不行，则回溯重来。
*
* 3.1 完成的条件。放入的元素个数，刚好等于初始 . 的个数
* @param board 棋盘
*/
public void solveSudoku(char[][] board) {
if(board == null || board.length == 0)
return;
solve(board);
}
public boolean solve(char[][] board){
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
if(board[i][j] == '.'){
for(char c = '1'; c <= '9'; c++){//trial. Try 1 through 9
if(isValid(board, i, j, c)){
board[i][j] = c; //Put c for this cell
if(solve(board))
return true; //If it's the solution return true
else
board[i][j] = '.'; //Otherwise go back
}
}
return false;
}
}
}
return true;
}
private boolean isValid(char[][] board, int row, int col, char c){
for(int i = 0; i < 9; i++) {
if(board[i][col] != '.' && board[i][col] == c) return false; //check row
if(board[row][i] != '.' && board[row][i] == c) return false; //check column
if(board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] != '.' &&
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; //check 3*3 block
}
return true;
}
效果
这种比较暴力，性能也会差一些。
TC: 20ms, 27.43%
MC: 401MB, 35.96%
V2-回溯版本优化
思路
我们可以通过数组模拟 isValid 方法，提升一下效率。
定义 3 个二维数组，根据 board 初始化数组。
boolean[][] rowUsed = new boolean[9][10];
boolean[][] colUsed = new boolean[9][10];
boolean[][][] boxUsed = new boolean[3][3][10];
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(board[i][j] != '.') {
int num = (int)(board[i][j] - '0');
rowUsed[i][num] = true;
colUsed[j][num] = true;
boxUsed[i/3][j/3][num] = true;
}
}
}
然后直接回溯使用：
boolean backtracking(int row, int col) {
// 列到达末尾，则换下一行进行处理。
if(col == board[0].length) {
col = 0;
row++;
// 最后结束，终止条件
if(row == board.length) {
return true;
}
}
// 待填入的位置
if(board[row][col] == '.') {
// 尝试 9 种数字
for(int i = 1; i <= 9; i++) {
boolean canUse = !(rowUsed[row][i] || colUsed[col][i] || boxUsed[row/3][col/3][i]);
// 在每行、列、小9宫格可以填写的数字。
if(canUse) {
// 使用
board[row][col] = (char)(i + '0');
rowUsed[row][i] = true;
colUsed[col][i] = true;
boxUsed[row/3][col/3][i] = true;
// 回溯
if(backtracking(row, col + 1)) {
return true;
}
// 清空
board[row][col] = '.';
rowUsed[row][i] = false;
colUsed[col][i] = false;
boxUsed[row/3][col/3][i] = false;
}
}
} else {
// 继续下一列
return backtracking(row, col + 1);
}
return false;
}
效果
TC: 3ms, 96.67%
MC: 40mb, 42.8%
这个使用数组替代方法的好处是，很多数据可以复用，而不是每次都要从头开始计算。
小结
针对数独的合法性校验，本身并不难。
数独解法，在数独的合法性基础之上。一般需要逐个尝试的问题，都可以采用回溯来解决。
有时候使用数组等进行预处理，可以进一步提升算法的效率。
希望本文对你有帮助，如果有其他想法的话，也可以评论区和大家分享哦。
各位极客的点赞收藏转发，是老马持续写作的最大动力！
开源地址
为了便于大家学习，所有实现均已开源。欢迎 fork + star~
参考资料
https://leetcode.com/problems/valid-sudoku/
https://leetcode.cn/problems/sudoku-solver/
