最后一遍-L37-Sudoku Solver
描述：
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
The '.' character indicates empty cells.
Example 1:
Input: 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"]]
Output:
[
["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"]]
Constraints:
board.length == 9
board[i].length == 9
board[i][j] is a digit 1-9 or '.'.
It is guaranteed that the input board has only one solution.
解数独，都主要的思路就是针对每一个格子的测试，如果不行，就换下一个元素，行了之后，继续测试下一个格子 这样我们就能够，想到回溯算法，这个是最容易联想的思路了
具体的代码为：
import java.util.*;
public class L37 {
private char[][] board = new char[][]{
{'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'}
};
public static void main(String[] args) {
L37 test = new L37();
test.solveSudoku(test.getBoard());
for (int i = 0; i < test.getBoard().length; i++) {
System.out.println(Arrays.toString(test.getBoard()[i]));
}
}
public void solveSudoku(char[][] board) {
if(board == null || board.length == 0) return;
solve(board);
}
private 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 k = '1'; k <='9' ; k++) {
if(isvalidate(board,i,j,k)){
board[i][j]=k;
if(solve(board)){
return true;
}
board[i][j]='.';
}
}
return false;
}
}
}
return true;
}
private static boolean isvalidate(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;
}
public void solveSudoku_reform(char[][] board) {
doSolve(board, 0, 0);
}
private boolean doSolve(char[][] board, int row, int col) {
for (int i = row; i < 9; i++, col = 0) { // note: must reset col here!
for (int j = col; j < 9; j++) {
if (board[i][j] != '.') continue;
for (char num = '1'; num <= '9'; num++) {
if (isvalidate(board, i, j, num)) {
board[i][j] = num;
if (doSolve(board, i, j + 1))
return true;
board[i][j] = '.';
}
}
return false;
}
}
return true;
}
public char[][] getBoard() {
return board;
}
public void setBoard(char[][] board) {
this.board = board;
}
}