Sudoku-Solver with GUI in Java

Question

I've wrote a Sudoku-Solver in Java, which also contains a GUI, so you can just enter the Sudoku, press "OK" and it will solve the Sudoku using backtracking.

Here's the code:

import javax.swing.*;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import static javax.swing.WindowConstants.EXIT_ON_CLOSE;

public class SudokuSolver {

    public static void main(String[] args) {
        int[][] board = {
                { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        };

        board = getSudoku(board);

        boolean solve = solver(board);
        if(solve) {
            display(board);
        }
        else {
            JOptionPane.showMessageDialog(null,"Not solvable.");
        }
    }

    //Backtracking-Algorithm
    public static boolean solver(int[][] board) {

        for (int i = 0; i < 9; i++) {

            for (int j = 0; j < 9; j++) {

                if (board[i][j] == 0) {

                    for (int n = 1; n < 10; n++) {

                        if (checkRow(board, i, n) && checkColumn(board, j, n) && checkBox(board, i, j, n)) {

                            board[i][j] = n;
                            if (!solver(board)) {

                                board[i][j] = 0;
                            }
                            else {
                                return true;
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    public static boolean checkRow(int[][] board, int row, int n) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == n) {
                return false;
            }
        }
        return true;
    }

    public static boolean checkColumn(int[][] board, int column, int n) {
        for (int i = 0; i < 9; i++) {
            if (board[i][column] == n) {
                return false;
            }
        }
        return true;
    }

    public static boolean checkBox(int[][] board, int row, int column, int n) {
        row = row - row % 3;
        column = column - column % 3;

        for (int i = row; i < row + 3; i++) {
            for (int j = column; j < column + 3; j++) {
                if (board[i][j] == n) {
                    return false;
                }
            }

        }
        return true;
    }
    public static int[][] getSudoku(int[][] board) {

        JFrame frame = new JFrame();
        frame.setSize(800, 700);
        frame.setDefaultCloseOperation(EXIT_ON_CLOSE);
        JPanel panel = new JPanel();
        JPanel subpanel1 = new JPanel();
        subpanel1.setPreferredSize(new Dimension(500,500));
        subpanel1.setLayout( new java.awt.GridLayout( 9, 9, 20, 20 ) );
        JTextArea[][] text = new JTextArea[9][9];
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                text[i][j] = new JTextArea();
                text[i][j].setText("0");
                text[i][j].setEditable(true);
                Font font = new Font("Verdana", Font.BOLD, 40);
                text[i][j].setFont(font);

                subpanel1.add(text[i][j]);
            }
        }
        JPanel subpanel2 = new JPanel();
        JButton button = new JButton("OK");
        button.addActionListener(new ActionListener() {
            @Override
            public void actionPerformed(ActionEvent actionEvent) {
                for(int i = 0; i < 9; i++) {
                    for(int j = 0; j < 9; j++) {
                        String s = text[i][j].getText();
                        board[i][j] = Integer.valueOf(s);
                        helper(1);
                    }
                }

            }
        });

        subpanel2.add(button);
        panel.add(subpanel1, BorderLayout.WEST);
        panel.add(subpanel2, BorderLayout.EAST);
        frame.add(panel);
        frame.setVisible(true);

        while(helper(0)) {

        }
        frame.dispose();
        return board;

    }

    public static void display(int[][] board) {
        JFrame frame = new JFrame();
        frame.setSize(700,700);
        JPanel panel = new JPanel();
        panel.setLayout(new GridLayout (9,9, 3 ,3));
        JTextArea[][] text = new JTextArea[9][9];
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                text[i][j] = new JTextArea();
                text[i][j].setText("" + board[i][j]);
                text[i][j].setEditable(false);
                Font font = new Font("Verdana", Font.BOLD, 40);
                text[i][j].setFont(font);

                panel.add(text[i][j]);
            }
        }
        frame.add(panel);
        frame.setVisible(true);

    }
    private static boolean test = true;
    public static boolean helper(int x) {
        if(x == 1) {
            test = false;
        }
        System.out.print("");
        return test;
    }

}

Do you have any suggestions on how to improve the code?

Answer 1

Solver

Your back-tracking algorithm to find the solution to the puzzle is fine, although it is fairly inefficient.

• On each recursive call, the algorithm must search for the position of the next unknown, which means starting at [0][0] and searching over the same locations over and over on each call. You could improve it by creating an ArrayList<> of unknown positions, and directly indexing to the unknown corresponding to the current search depth. Or you could pass the current board position (i, j) as a starting point for the next level of the search.
• You could use a Set<>, such as a BitSet, to store the unused numbers in each row, column, and box. When processing each cell, you could "and" those sets together to create a much smaller set of candidate values to try.

But these optimizations are only necessary if your solver algorithm isn't fast enough. I haven't tried it.

An organizational improvement might be to move the Sudoku Solver code into its own class, so it could be used in other projects. For instance, you could make a JavaFX, or an SWT version of your program, and reuse the solver code ... if it was a stand-alone class.

GUI

Your GUI is where a lot of work is absolutely needed. This code is just plain awful.

Minor

Starting with the easiest to fix items:

• the getSudoku() method creates a JFrame and sets EXIT_ON_CLOSE, but the display() method creates a JFrame without EXIT_ON_CLOSE. If the user closes the second frame, the program will not immediately terminate.

• JTextArea is a multiline text edit window. You are creating 81 of these in a 9x9 grid. Surely you wanted to use the much lighter weight JTextField ... or even the JLabel when displaying the solution.

• You create 81 identical Font objects, one for each JTextArea. You should create just one, and set the font of each JTextArea (or JTextField/JLabel) to this common Font object. Simply move the statement out of the double loop.

• public static int[][] getSudoku(int[][] board) is this method allocating a new board and returning it, or is it just modifying the board it was given? Why have both an input parameter board and a return value, if the board that it is given is the board that is returned?

But the most SERIOUS problem is you are creating and manipulating Swing GUI objects from threads other than the Event Dispatching Thread (EDT). Swing is NOT thread safe. It is a convenience, and a thorn, that Swing allows you to build the GUI on the main thread. Swing goes to great lengths to allow it ... once. After the realization of any Swing GUI object, or after any Timer is started, all interaction must be performed on the EDT, or unexplainable, hard-to-debug behaviour -- up to and including application crashes -- are possible. So up to this line, which realizes the GUI components:

    frame.setVisible(true);

you are safe. However, it is followed by:

    while(helper(0)) {

    }
    frame.dispose();

which is a recipe for disaster. It is bad that this is an empty spin loop on the main application thread, but frame.dispose() is the violation about touching live Swing objects from threads other than the EDT. Then, the code returns to the main() function where display() is called, and more Swing GUI items are created on not the EDT.

Working on the EDT

First, you should divorce yourself from the main thread, and create your GUI on the EDT:

public class SudokuSolver {

    public static void main(String[] args) {
        SwingUtilities.invokeLater(new Runnable() {
            @Override
            void run() {
                createGUI();
            }
        });
    }

    private static void createGUI() {
        /* Create JFrame, JPanel, etc here */
        frame.setVisible(true); 
   }

   ...
}

Or, if you are comfortable with lambdas and method references:

public class SudokuSolver {

    public static void main(String[] args) {
        SwingUtilities.invokeLater(SudokuSolver::createGUI);
    }

    private static void createGUI() {
        /* Create JFrame, JPanel, etc here */
        frame.setVisible(true); 
   }

   ...
}

The invokeLater() method takes a runnable, switches to the Event Dispatching Thread, and runs the runnable. So this create all GUI objects on the EDT. The final step is the frame is made visible. And then execution ends. Nothing else happens. The main thread has already reached the end of main() and has terminated; nothing else happens there, either. The application has become purely an event driven GUI application. It is now waiting for the user to interact with the GUI elements.

Working off the EDT

Once the user has entered their grid, the press the "OK" button, and the actionPerformed method is called.

Note that this method called helper(1) a total of 81 times. At any point after this method was called once, and before it had been called the last time, the board[][] would have contained an incomplete starting point for the solution, but the main thread could start attempting to solve the grid, since the test flag would have been cleared! Just one more danger of multithreaded processing.

Instead, after both loops in the actionPerformed method, a SwingWorker should be created and given a copy of the board. This worker could solve the board in its background thread, and then in its done() method, which is run once again on the EDT, the solved board could be displayed in the GUI.