java - 数独生成器算法优化 欢迎

Question

我创建了一个递归 DFS 算法来用 Java 生成/解决数独板，但它需要永远终止，欢迎提供解释/优化。我无法想象生成数独板会如此耗时，尤其是周围有所有应用程序(尽管它们可能有数据库。)

基本上，我遍历所有单元格，查看 [1-9] 中的任何一个是否满足数独约束，并在死胡同分支上回溯。为了节省内存并避免在每次调用递归方法时复制充当棋盘的二维数组(如果我没记错的话，那棵树中可能有 81*9! 叶子……)，我创建了一个二维数组整数堆栈矩阵，每次探索分支时都会压入一个元素，如果是死胡同则弹出。

下面是实现。欢迎任何关于加速的建议。我这样做是作为个人练习，我想知道是否存在渐近更好的东西。

希望下面的内容不会太糟糕。谢谢!

1) 算法实现:(请注意，值位于 [1-9] 的“困惑”数组中以创建独特的板。)

/**
 * Provides one solution to a board with an initial configuration, or <code>null</code> if there is none.
 * The search is randomized, s.t. the algorithm can serve to populate an empty board. 
 * 
 * @param initial The initial board given to solve.
 * @return The fully solved board, or null if no solution found.
 */
public static int[][] solveBoard (int[][] initial){
    return solveBoard(new StackedBoard(initial), 0, 0);
}

private static int[][] solveBoard (StackedBoard board, int xPos, int yPos){

    // base case - success
    int remaining = 81;
    for (int x = 0; x < 9; x++){
        for (int y = 0; y < 9; y++){
            if (board.peekAt(x, y) != Board.EMPTY){
                remaining--;
            }
        }
    }
    if (remaining == 0){
        return board.flatView();// the only creation of an array.
    }

    // recursive case
    for (int x = 0; x < 9; x++){
        for (int y = 0; y < 9; y++){
            if (board.peekAt(x, y) == Board.EMPTY){
                for (int val : getJumbledRandomVals()){
                    if (isMoveLegal(board, x, y, val)){
                        board.pushAt(x, y, val);
                        int[][] leafBoard = solveBoard(board, x, y);
                        if (leafBoard != null) {
                            return leafBoard;
                        }
                    }
                }
            }
        }
    }

    // base case - dead branch
    board.popAt(xPos, yPos);
    return null;
}

2) StackedBoard 实现:

/**
 * Represents square boards with stacked int elements.
 */
class StackedBoard {

    ArrayList<ArrayList<Stack<Integer>>> xaxis = new ArrayList<ArrayList<Stack<Integer>>>();

    /**
     * 
     * @param init A square array - both dimensions of equal length, or <code>null</code> if no initialization.
     */
    public StackedBoard (int[][] init) {
        for (int i = 0; i < 9; i++){
            ArrayList<Stack<Integer>> yaxis = new ArrayList<Stack<Integer>>();
            xaxis.add(yaxis);

            for (int j = 0; j < 9; j++){
                Stack<Integer> stack = new Stack<Integer>();
                yaxis.add(stack);
            }
        }

        if (init != null){
            for (int x = 0; x < init.length; x++){
                for (int y = 0; y < init.length; y++){
                    getStackAt(x, y).push(init[x][y]);
                }
            }   
        }
    }

    public Stack<Integer> getStackAt (int x, int y){
        return xaxis.get(x).get(y);
    }

    public int peekAt (int x, int y){
        return getStackAt(x, y).peek();
    }

    public void pushAt (int x, int y, int value){
        getStackAt(x, y).push(value);
    }

    public Integer popAt (int x, int y){
        try {
            return getStackAt(x, y).pop();  
        } catch (EmptyStackException e){
            // shhhhh!
            return Board.EMPTY;
        }

    }

    /**
     * Flat view of the stacked-board; peek of the top elements.
     */
    public int[][] flatView (){
        int[][] view = new int[xaxis.size()][xaxis.size()];

        for (int x = 0; x < xaxis.size(); x++){
            for (int y = 0; y < xaxis.size(); y++){
                view[x][y] = getStackAt(x, y).peek();
            }
        }

        return view;
    }
}

3)约束函数实现:

/**
 * Is the move legal on the suggested board?
 * 
 * @param board The board.
 * @param x The X coordinate, starts with 0.
 * @param y The Y coordinate, starts with 0.
 * @param value The value.
 * @return <code>true</code> iff the move is legal.
 */
private static boolean isMoveLegal (StackedBoard board, int x, int y, int value){
    // by value
    if (1 > value || value > 9){
        return false;
    }

    // by column
    for (int i = 0; i < 9; i++){
        if (board.peekAt(i, y) == value){
            return false;
        }
    }

    // by row
    for (int i = 0; i < 9; i++){
        if (board.peekAt(x, i) == value){
            return false;
        }
    }

    // by lil square
    int lowerX = x < 3 ? 0 : (x < 6 ? 3 : 6);
    int upperX = lowerX + 2;
    int lowerY = y < 3 ? 0 : (y < 6 ? 3 : 6);
    int upperY = lowerY + 2;

    for (int i = lowerX; i <= upperX; i++){
        for (int j = lowerY; j <= upperY; j++){
            if (board.peekAt(i, j) == value){
                return false;
            }
        }
    }

    return true;
}

Answer 1

如果您愿意完全左转，则有更好的算法来生成/解决数独问题。 Don Knuth 的 dancing links algorithm众所周知，它非常擅长快速枚举所有数独解决方案(一旦它们被表述为 exact cover problem 的实例)并且通常用作数独求解器中的主要算法，值得研究。它需要大量的指针/引用体操，但编写代码相对较短。

如果您想坚持现有的方法，一个有用的优化是始终选择最受约束的单元格作为下一个要填充的值。这可能会导致一连串的“强制移动”，这将帮助您减少搜索空间的大小，尽管这只是一种启发式方法。

希望这对您有所帮助!