0

I created a recursive DFS algorithm to generate/solve sudoku boards in Java, but it's taking forever to terminate, and an explanation/optimization would be welcome. I can't imagine that generating a sudoku board would be so time-consuming, especially with all the apps around (although they might have a database.)

Basically, I traverse all cells, seeing whether any of [1-9] would satisfy the sudoku constraints, and backtrack on dead-end branches. To conserve memory and avoid copying the 2D array that serves as the board with each invocation of the recursive method (and there are potentially 81*9! leaves in that tree, if I'm not mistaken...), I created a 2D matrix of integer stacks, in which an element is pushed every time a branch is explored, and popped if it's a dead-end.

Below is the implementation. Any advice on speedup would be welcome. I'm doing this as a personal excercise, and I'm wondering if something asymptotically better exists.

Hope it's not a terrible read below.. Thank you!

1) The algorithm implementation: (note that values are in a "jumbled" array of [1-9] to create unique boards.)

/**
 * 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) The StackedBoard implementation:

/**
 * 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) The constraints function implementation:

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

1 Answer 1

4

If you are willing to make a complete left turn, there are much better algorithms for generating / solving Sudokus. Don Knuth's dancing links algorithm is known to be extremely good at rapidly enumerating all Sudoku solutions (once they're phrased as instances of the exact cover problem) and is commonly used as the main algorithm in Sudoku solvers, and it's worth looking into. It requires a lot of pointer/reference gymnastics, but it relatively short to code up.

If you want to stick with your existing approach, one useful optimization would be to always choose the most constrained cell as the next value to fill in. This will likely cause a cascade of "forced moves" that will help you reduce the size of your search space, though it's only a heuristic.

Hope this helps!

1
  • Thank you! I'll look into both solutions!
    – vivri
    Nov 1, 2013 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.