教你怎么用Java回溯算法解数独

Scanner sc = new Scanner(System.in);
int[][] board = new int[9][9];
// 输入
for (int i = 0; i < 9; i++) {
    for (int j = 0; j < 9; j++) {
        board[i][j] = sc.nextInt();
    }
}

public static void dfs(int[][] board, int r, int c) {
	// 所有数填完了，输出
    if (r == 9) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
        return;
    }
	// 空白填数
	if (board[r][c] == 0) {
		// 从 1-9 中依次选数
	    for (int k = 1; k <= 9; k++) {
	    	// 先判断放进去是否满足条件再选择
	        if (isValid(board, r, c, k)) {
	            // 做选择
	            board[r][c] = k;
	            // 决定下一个格子
	            next(board, r, c);
	            // 撤销选择
	            board[r][c] = 0;
	        }
	    }
	}
	// 非空白直接决定下一个格子
	else next(board, r, c);
}

// 递归下一个格子
public static void next(int[][] board, int r, int c) {
    if (c + 1 == 9) dfs(board, r + 1, 0);
    else dfs(board, r, c + 1);
}

// 判断是否合法
public static boolean isValid(int[][] board, int r, int c, int val) {
    // 列
    for (int i = 0; i < 9; i++) {
        if (board[i][c] == val) return false;
    }
    // 行
    for (int j = 0; j < 9; j++) {
        if (board[r][j] == val) return false;
    }
    // 3 * 3
    for (int x = r / 3 * 3, i = x; i < x + 3; i++) {
        for (int y = c / 3 * 3, j = y; j < y + 3; j++) {
            if (board[i][j] == val) return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    solveSudoku();
}

public static void solveSudoku() {
    Scanner sc = new Scanner(System.in);
    int[][] board = new int[9][9];
    // 输入
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            board[i][j] = sc.nextInt();
        }
    }
    dfs(board, 0, 0);
}

// 回溯填数
public static void dfs(int[][] board, int r, int c) {
    // 所有数填完了，输出
    if (r == 9) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
        return;
    }
    // 空白填数
    if (board[r][c] == 0) {
        for (int k = 1; k <= 9; k++) {
            if (isValid(board, r, c, k)) {
                // 做选择
                board[r][c] = k;
                // 决定下一个格子
                next(board, r, c);
                // 撤销选择
                board[r][c] = 0;
            }
        }
    }
    // 非空白直接决定下一个格子
    else next(board, r, c);
}

// 递归下一个格子
public static void next(int[][] board, int r, int c) {
    if (c + 1 == 9) dfs(board, r + 1, 0);
    else dfs(board, r, c + 1);
}

// 判断是否合法
public static boolean isValid(int[][] board, int r, int c, int val) {
    // 列
    for (int i = 0; i < 9; i++) {
        if (board[i][c] == val) return false;
    }
    // 行
    for (int j = 0; j < 9; j++) {
        if (board[r][j] == val) return false;
    }
    // 3 * 3
    for (int x = r / 3 * 3, i = x; i < x + 3; i++) {
        for (int y = c / 3 * 3, j = y; j < y + 3; j++) {
            if (board[i][j] == val) return false;
        }
    }
    return true;
}

输入：
5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 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

输入：
0 0 0 5 0 0 9 0 0
6 0 4 2 0 3 0 0 0
5 0 0 0 6 0 0 3 2
0 0 0 0 9 0 4 0 0
4 2 0 1 0 5 0 7 9
0 0 9 7 0 0 1 0 0
9 0 0 0 0 6 0 1 8
2 0 0 0 4 0 0 0 5
0 0 0 0 0 0 6 0 0

输出：
7 3 2 5 8 1 9 6 4
6 9 4 2 7 3 5 8 1
5 1 8 4 6 9 7 3 2
1 7 5 6 9 8 4 2 3
4 2 6 1 3 5 8 7 9
3 8 9 7 2 4 1 5 6
9 4 7 3 5 6 2 1 8
2 6 1 8 4 7 3 9 5
8 5 3 9 1 2 6 4 7

输入：
0 0 9 7 4 8 0 0 0
7 0 0 0 0 0 0 0 0
0 2 0 1 0 9 0 0 0
0 0 7 0 0 0 2 4 0
0 6 4 0 1 0 5 9 0
0 9 8 0 0 0 3 0 0
0 0 0 8 0 3 0 2 0
0 0 0 0 0 0 0 0 6
0 0 0 2 7 5 9 0 0

输出：
5 1 9 7 4 8 6 3 2
7 8 3 6 5 2 4 1 9
4 2 6 1 3 9 8 7 5
3 5 7 9 8 6 2 4 1
2 6 4 3 1 7 5 9 8
1 9 8 5 2 4 3 6 7
9 7 5 8 6 3 1 2 4
8 3 2 4 9 1 7 5 6
6 4 1 2 7 5 9 8 3