2020-05-03 37. Sudoku Solver Ha
题目在后面，先记录点心得：
这个hard的题目还是有点难的，我卡住了好像一个钟左右（这两天做其他medium提都是几分钟到几十分钟），快要放弃想要看别人答案的时候摸索出来几个门路，还是解出来了（因为这题还是想自己做出来，毕竟代码都写得差不多了，而且不觉得自己有什么大错误）：
1、也是回溯方法，注意的细节是找下一个空格的时候，如果当前行不是起始行，y要从0开始，否则就直接跳过没有判断的格子了：
for (int j = (i == x ? y : 0); j < board[0].length; j++)
2、还有就是对于结束的判断，正确的判断条件为，找不到'.'符号，就是正确了（因为每一步填各自都验证了正确性，所以能够填满就是正确）
3、另外就是这个程序开始觉得很难排查问题，因为本身解数独就比较困难，需要看很多格子，慢慢数出来。这里我是借了题目的便利，因为题目给了一个正确答案，所以我把每次遍历的board打印出来，然后看看我的程序解到哪一步出错了（也就是把一行正确答案拷贝出来，然后黏贴到控制台输出去搜索，看看程序有没有解对）。就是用这个方法，我才发现了程序其实都解对了，就是结束条件不对。所以有时候排查问题的能力也很重要，需要想些新思路检查自己到底是哪里不对。
题目：
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfyall of the following rules:
Each of the digits1-9 must occur exactly once in each row.
Each of the digits1-9must occur exactly once in each column.
Each of the the digits1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Empty cells are indicated by the character '.'.
（图片挂了传不了，想看图可以去原网页看https://leetcode.com/problems/sudoku-solver/）
A sudoku puzzle...
（同上）
...and its solution numbers marked in red.
Note:
The given board contain only digits 1-9 and the character '.'.
You may assume that the given Sudoku puzzle will have a single unique solution.
The given board size is always 9x9.
代码：
class Solution {
public void solveSudoku(char[][] board) {
findNextEmptyCellAndSolve(board, 0, 0);
}
private boolean findNextEmptyCellAndSolve(char[][] board, int x, int y) {
for (int i = x; i < board.length; i++) {
for (int j = (i == x ? y : 0); j < board[0].length; j++) {
char c = board[i][j];
if (c == '.') {
if (doSolve(board, i, j)) return true;
return false;
}
}
}
return true;
}
private boolean doSolve(char[][] board, int i, int j) {
int curCell = board[i][j];
for (char candidate = '1'; candidate <= '9'; candidate++) {
boolean invalid = false;
for (int d = 0; d < 9; d++) {
if (board[i][d] == candidate || board[d][j] == candidate) { invalid = true; break; }
}
if (invalid) continue;
for (int a = i / 3 * 3; a < i / 3 * 3 + 3; a++) {
for (int b = j / 3 * 3; b < j / 3 * 3 + 3; b++) {
if (board[a][b] == candidate) { invalid = true; break; }
}
if (invalid) break;
}
if (invalid) continue;
board[i][j] = candidate;
if (findNextEmptyCellAndSolve(board, i, j + 1)) return true;
board[i][j] = '.';
}
return false;
}
}
第二种方法：
上面的方法还不是很快，看了些排名前面的代码，发现原来可以用几个数组直接辅助判断，就不需要每次都循环，而且空间复杂度也是固定的
private boolean row[][] = new boolean[N][N];
private boolean col[][] = new boolean[N][N];
private boolean adj[][][] = new boolean[n][n][N];
完整代码：
class Solution {
private static final int n = 3;
private static final int N = n * n;
private boolean row[][] = new boolean[N][N];
private boolean col[][] = new boolean[N][N];
private boolean adj[][][] = new boolean[n][n][N];
public void solveSudoku(char[][] board) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] != '.') {
row[i][board[i][j] - '1'] = true;
col[j][board[i][j] - '1'] = true;
adj[i / 3][j / 3][board[i][j] - '1'] = true;
}
}
}
findNextEmptyCellAndSolve(board, 0, 0);
}
private boolean findNextEmptyCellAndSolve(char[][] board, int x, int y) {
for (int i = x; i < board.length; i++) {
for (int j = (i == x ? y : 0); j < board[0].length; j++) {
char c = board[i][j];
if (c == '.') {
if (doSolve(board, i, j)) return true;
return false;
}
}
}
return true;
}
private boolean doSolve(char[][] board, int i, int j) {
int curCell = board[i][j];
for (char candidate = '1'; candidate <= '9'; candidate++) {
if (row[i][candidate - '1'] || col[j][candidate - '1'] || adj[i / 3][j / 3][candidate - '1']) continue;
row[i][candidate - '1'] = col[j][candidate - '1'] = adj[i / 3][j / 3][candidate - '1'] = true;
board[i][j] = candidate;
if (findNextEmptyCellAndSolve(board, i, j + 1)) return true;
row[i][candidate - '1'] = col[j][candidate - '1'] = adj[i / 3][j / 3][candidate - '1'] = false;
board[i][j] = '.';
}
return false;
}
}
