Selamat datang optimasi algoritma generator Sudoku

Saya membuat algoritma DFS rekursif untuk menghasilkan/menyelesaikan papan sudoku di Java, tetapi butuh waktu lama untuk menghentikannya, dan penjelasan/optimasi akan diterima. Saya tidak dapat membayangkan bahwa membuat papan sudoku akan memakan waktu lama, terutama dengan semua aplikasi yang ada (walaupun mereka mungkin memiliki database.)

Pada dasarnya, saya melintasi semua sel, melihat apakah ada di antara [1-9] yang memenuhi batasan sudoku, dan melakukan backtrack pada cabang buntu. Untuk menghemat memori dan menghindari penyalinan array 2D yang berfungsi sebagai papan dengan setiap pemanggilan metode rekursif (dan berpotensi ada 81*9! daun di pohon itu, jika saya tidak salah...), saya membuat 2D matriks tumpukan bilangan bulat, di mana elemen didorong setiap kali cabang dieksplorasi, dan muncul jika menemui jalan buntu.

Di bawah ini adalah implementasinya. Setiap saran tentang percepatan akan diterima. Saya melakukan ini sebagai latihan pribadi, dan saya bertanya-tanya apakah ada sesuatu yang lebih baik tanpa gejala.

Semoga bukan bacaan yang buruk di bawah ini.. Terima kasih!

1) Implementasi algoritma: (perhatikan bahwa nilai berada dalam array "campur aduk" [1-9] untuk membuat papan unik.)

/**
 * 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) Implementasi 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) Implementasi fungsi kendala:

/**
 * 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;
}