比較常規(guī)的回溯問(wèn)題
采用boolean數(shù)組進(jìn)行去重

package No37_SudokuSolver;

public class Solution {
    char[][] board;
    boolean rowUsed[][];
    boolean colUsed[][];
    boolean boxUsed[][][];

    public void solveSudoku(char[][] board) {
        this.board = board;
        this.rowUsed = new boolean[9][10]; // board中的數(shù)為1-9 為了能夠讓下標(biāo)對(duì)應(yīng)數(shù)字 我們這里創(chuàng)建大小為10而不是9
        this.colUsed = new boolean[9][10];
        this.boxUsed = new boolean[3][3][10];

        /* 初始化三個(gè)used */
        for (int i = 0; i < 9; i ++) {
            for (int j = 0; j < 9; j ++) {
                if (board[i][j] == '.')
                    continue;
                int num = board[i][j] - '0';
                rowUsed[i][num] = true;
                colUsed[j][num] = true;
                boxUsed[i / 3][j / 3][num] = true;
            }
        }

        trackBack(0, 0);


    }

    private boolean trackBack(int row, int col) {
        if (col == 9) { // col最大為8 說(shuō)明當(dāng)前行已滿(mǎn) 換下一行
            col = 0;
            row += 1;
            if (row == 9) { // row最大為8 說(shuō)明當(dāng)前表已滿(mǎn) 結(jié)束
                return true;
            }
        }

        if (board[row][col] != '.') { // 需要細(xì)想
//            if (trackBack(row, col + 1))
//                return true;
//            return false;
            return trackBack(row, col + 1); // 因?yàn)楫?dāng)前層就只有給定的一個(gè)選擇 所以是可以直接返回的
        }

        for (int i = 1; i < 10; i ++) { // 可選擇數(shù)字為1-9
            if (!rowUsed[row][i] && !colUsed[col][i] && !boxUsed[row / 3][col / 3][i]) {
                board[row][col] = (char) ('0' + i);
                rowUsed[row][i] = colUsed[col][i] = boxUsed[row / 3][col / 3][i] = true;
                if (trackBack(row, col + 1)) { // 一個(gè)為false無(wú)法說(shuō)明為false 只有當(dāng)for循環(huán)中的所有都為false 才真正為false 由于我們只需要一個(gè)解法玉控，所以遇到true我們就可以返回了
                    return true;
                }
                rowUsed[row][i] = colUsed[col][i] = boxUsed[row / 3][col / 3][i] = false;
                board[row][col] = '.';
            }
        }
        return false;
    }

    public static void main(String[] args) {
        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'}
        };

        Solution solution = new Solution();
        solution.solveSudoku(board);
        for (char[] cs : board) {
            for (char c : cs) {
                System.out.print(c);
            }
            System.out.println();
        }
    }
}

題解傳送門(mén)