Java 回溯算法破解「世界最難數獨」：約束傳播與深度優先搜索實戰

背景：Arto Inkala 的「AI Escargot」

2012 年，芬蘭數學家 Arto Inkala 設計出當時難度最高的數獨「AI Escargot」，僅有一解，純邏輯推演極難，需回溯搜索。本文用 Java 實現帶約束傳播的深度優先搜索（DFS + Backtracking），毫秒級求解。

核心數據結構：Cell（格子）

class Cell {
    final int row, col;      // 座標
    final int block;         // 所屬 3x3 宮索引 0-8
    int value;               // 0 表示空
    boolean fixed;           // true=題目給定，不可修改

    Cell(int row, int col, int value, boolean fixed) {
        this.row = row; this.col = col; this.block = (row/3)*3 + col/3;
        this.value = value; this.fixed = fixed;
    }
    boolean isEmpty() { return value == 0; }
}

約束檢查：O(1) 判斷合法性

使用三個 boolean[9][10] 陣列記錄行/列/宮已佔用數字，避免重複掃描：

class SudokuSolver {
    private final Cell[][] grid = new Cell[9][9];
    private final boolean[][] rowUsed = new boolean[9][10];  // rowUsed[r][digit]
    private final boolean[][] colUsed = new boolean[9][10];
    private final boolean[][] boxUsed = new boolean[9][10];
    private final List empties = new ArrayList<>();    // 所有空格，按候選數少到多排序

    public SudokuSolver(int[][] puzzle) {
        for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++) {
            int v = puzzle[r][c];
            boolean fixed = v != 0;
            grid[r][c] = new Cell(r, c, v, fixed);
            if (fixed) { setUsed(r, c, v, true); }
            else { empties.add(grid[r][c]); }
        }
        // 啟發式：優先填候選數最少的格子（MRV 原則）
        empties.sort(Comparator.comparingInt(this::candidateCount));
    }

    private int candidateCount(Cell cell) {
        int cnt = 0;
        for (int d = 1; d <= 9; d++) if (canPlace(cell, d)) cnt++;
        return cnt;
    }
    private boolean canPlace(Cell c, int d) {
        return !rowUsed[c.row][d] && !colUsed[c.col][d] && !boxUsed[c.block][d];
    }
    private void setUsed(int r, int c, int d, boolean used) {
        rowUsed[r][d] = used; colUsed[c][d] = used; boxUsed[(r/3)*3+c/3][d] = used;
    }
}

遞歸回溯主流程

public boolean solve() { return dfs(0); }

private boolean dfs(int idx) {
    if (idx == empties.size()) return true; // 全部填滿，找到解
    
    Cell cell = empties.get(idx);
    for (int d = 1; d <= 9; d++) {
        if (canPlace(cell, d)) {
            place(cell, d);
            if (dfs(idx + 1)) return true;
            remove(cell, d); // 回溯
        }
    }
    return false; // 1-9 都不行，向上回溯
}

private void place(Cell c, int d) { c.value = d; setUsed(c.row, c.col, d, true); }
private void remove(Cell c, int d) { c.value = 0; setUsed(c.row, c.col, d, false); }

測試：AI Escargot 實測

public static void main(String[] args) {
    int[][] hardest = {
        {8,0,0,0,0,0,0,0,0},
        {0,0,3,6,0,0,0,0,0},
        {0,7,0,0,9,0,2,0,0},
        {0,5,0,0,0,7,0,0,0},
        {0,0,0,0,4,5,7,0,0},
        {0,0,0,1,0,0,0,3,0},
        {0,0,1,0,0,0,0,6,8},
        {0,0,8,5,0,0,0,1,0},
        {0,9,0,0,0,0,4,0,0}
    };

    long start = System.nanoTime();
    SudokuSolver solver = new SudokuSolver(hardest);
    boolean solved = solver.solve();
    long costMs = (System.nanoTime() - start) / 1_000_000;

    System.out.println("求解：" + (solved ? "成功" : "失敗") + "，耗時 " + costMs + " ms");
    solver.printGrid();
}

輸出：

求解：成功，耗時 3 ms
8 1 2 | 7 5 3 | 6 4 9
9 4 3 | 6 8 2 | 1 7 5
6 7 5 | 4 9 1 | 2 8 3
------+-------+------
1 5 4 | 2 3 7 | 8 9 6
3 6 9 | 8 4 5 | 7 2 1
2 8 7 | 1 6 9 | 5 3 4
------+-------+------
5 2 1 | 9 7 4 | 3 6 8
4 3 8 | 5 2 6 | 9 1 7
7 9 6 | 3 1 8 | 4 5 2

性能優化關鍵點總結

1. 位掩碼優化：用 int 位運算替換 boolean[][]，rowMask[r] | (1< 判斷佔用，極致快；
2. MRV 啟發式：優先填候選數最少的格子（Minimum Remaining Values），大幅剪枝；
3. 裸單/隱單預處理：遞歸前反覆填入「唯一候選」格子，縮小搜索空間；
4. 迭代加深/跳躍式回溯：極難題可引入 DLX (Dancing Links) 算法 X，將數獨建模為精確覆蓋問題。