The idea is to set flags for each position, as row, column and square with the number on it. Recursive call, with the current position, if not '.', try recursive call itself for next depth (each depth is actually the cell inside), else loop from 1 to 9, if the number is not in any flags, row, column and square, then change the current position to that number, and recursive call with updated depth. If the recursive call returns false, revert the previous change, and do for next iteration.
This is a DFS process by recursive call.
public class Solution {
public void solveSudoku(char[][]board){
if(board == null){
return;
}
boolean[][] rowB = new boolean[10][10];
boolean[][] colB = new boolean[10][10];
boolean[][] gridB = new boolean[10][10];
for(int i = 0; i < 81; i++){
int rowN = i / 9;
int colN = i % 9;
int gridN = rowN / 3 * 3 + colN / 3;
if(board[rowN][colN] != '.'){
int num = board[rowN][colN] - '0';
rowB[rowN][num] = true;
colB[colN][num] = true;
gridB[gridN][num] = true;
}
}
solveOps(board, rowB, colB, gridB, 0);
}
private boolean solveOps(char[][] board, boolean[][] rowB, boolean[][] colB, boolean[][] gridB, int depth){
if(depth == 81){
return true;
}
int rowIndex = depth / 9;
int colIndex = depth % 9;
int gridIndex = rowIndex / 3 * 3 + colIndex / 3;
if(board[rowIndex][colIndex] != '.'){
return solveOps(board, rowB, colB, gridB, depth + 1);
}
for(int num = 1; num <= 9; num++){
if(!rowB[rowIndex][num] && !colB[colIndex][num] && !gridB[gridIndex][num]){
rowB[rowIndex][num] = true;
colB[colIndex][num] = true;
gridB[gridIndex][num] = true;
board[rowIndex][colIndex] = (char)(num + '0');
if(solveOps(board, rowB, colB, gridB, depth + 1)) {return true;};
board[rowIndex][colIndex] = '.';
rowB[rowIndex][num] = false;
colB[colIndex][num] = false;
gridB[gridIndex][num] = false;
}
}
return false;
}
}
没有评论:
发表评论