Sudoku-Solver with GUI - follow-up

Question

Background

A few months ago, I asked this and this question on my implementation of a Sudoku-Solver. I now tried to further improve this little project.

Changes

• Minor GUI-changes
• Input validation
• "Reset"-button
• Check if solution is unique (This question on stackoverflow helped)
• Naming
• Structuring Code with Classes
• Added tests

Code

Control.java (Starting the application)

import javax.swing.SwingUtilities;

public class Control {
  public static void main(String[] args) {
    SwingUtilities.invokeLater(Gui::new);
  }
}

Gui.java (responsible for the UI)

import java.awt.BorderLayout;
import java.awt.Font;
import java.awt.GridLayout;
import java.text.NumberFormat;
import javax.swing.JButton;
import javax.swing.JFormattedTextField;
import javax.swing.JFrame;
import javax.swing.JOptionPane;
import javax.swing.JPanel;
import javax.swing.JTextField;
import javax.swing.WindowConstants;
import javax.swing.text.NumberFormatter;

public class Gui {

  private final int GUI_SIZE = 700;
  private final int GRID_SIZE = 9;

  private JTextField[][] sudokuGrid;
  private JButton buttonOK;


  public Gui() {
    JFrame frame = new JFrame("Sudoku-Solver");
    frame.setSize(GUI_SIZE, GUI_SIZE);
    frame.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);
    JPanel panel = new JPanel(new BorderLayout());
    JPanel gridPanel = new JPanel(new GridLayout(GRID_SIZE, GRID_SIZE));

    /*
     * The following lines ensure that the user can only enter numbers.
     */

    NumberFormat format = NumberFormat.getInstance();
    NumberFormatter formatter = new NumberFormatter(format);
    formatter.setValueClass(Integer.class);
    formatter.setMinimum(0);
    formatter.setMaximum(Integer.MAX_VALUE);
    formatter.setAllowsInvalid(false);
    formatter.setCommitsOnValidEdit(true);

    /*
     * 81 text fields are now created here, which are used by the user to enter the Sudoku, which he
     * wants to solve.
     */

    sudokuGrid = new JFormattedTextField[GRID_SIZE][GRID_SIZE];
    Font font = new Font("Verdana", Font.BOLD, 40);
    for (int i = 0; i < GRID_SIZE; i++) {
      for (int j = 0; j < GRID_SIZE; j++) {
        sudokuGrid[i][j] = new JFormattedTextField(formatter);

        /*
         * "0" = empty field
         */

        sudokuGrid[i][j].setText("0");
        sudokuGrid[i][j].setHorizontalAlignment(JTextField.CENTER);
        sudokuGrid[i][j].setEditable(true);
        sudokuGrid[i][j].setFont(font);

        gridPanel.add(sudokuGrid[i][j]);
      }
    }
    JPanel buttonPanel = new JPanel();

    /*
     * When the user presses the OK-button, the program will start to solve the Sudoku.
     */

    buttonOK = new JButton("OK");
    buttonOK.addActionListener(e -> ok());

    /*
     * Reset-button makes it possible to solve another Sudoku without reopening the whole program.
     */

    JButton buttonReset = new JButton("Reset");
    buttonReset.addActionListener(e -> reset());
    buttonPanel.add(buttonOK);
    buttonPanel.add(buttonReset);
    panel.add(gridPanel, BorderLayout.CENTER);
    panel.add(buttonPanel, BorderLayout.PAGE_END);
    frame.add(panel);
    frame.setVisible(true);
  }

  private void ok() {
    SudokuSolver solver = new SudokuSolver();

    /*
     * The program now writes the enter numbers in an array.
     */

    int board[][] = new int[GRID_SIZE][GRID_SIZE];
    for (int i = 0; i < GRID_SIZE; i++) {
      for (int j = 0; j < GRID_SIZE; j++) {
        String s = sudokuGrid[i][j].getText();
        board[i][j] = Integer.valueOf(s);
      }
    }

    /*
     * Are there only numbers between 0 and 9?
     */

    if (solver.inputValidation(board)) {
      int solve = solver.solver(board, 0);
      if(solve == 0) {
        JOptionPane.showMessageDialog(null, "Not solvable.");
      }
      if (solve >= 1) {

        /*
         * Output of solved Sudoku.
         */

        for (int i = 0; i < GRID_SIZE; i++) {
          for (int j = 0; j < GRID_SIZE; j++) {
            sudokuGrid[i][j].setText("" + solver.getSolution(i, j));
            sudokuGrid[i][j].setEditable(false);
          }
        }
      } 
      if(solve > 1) {
        JOptionPane.showMessageDialog(null, "Multiple solutions possible.");
      }
      buttonOK.setEnabled(false);
    } else {
      JOptionPane.showMessageDialog(null, "Invalid input.");
    }
  }

  private void reset() {
    for (int i = 0; i < GRID_SIZE; i++) {
      for (int j = 0; j < GRID_SIZE; j++) {
        sudokuGrid[i][j].setText("0");
        sudokuGrid[i][j].setEditable(true);
      }
    }
    buttonOK.setEnabled(true);
  }
}

SudokuSolver.java (responsible for the logic)

public class SudokuSolver {

  private final int GRID_SIZE = 9;
  private final int EMPTY = 0;

  private int[][] solution = new int[GRID_SIZE][GRID_SIZE];

  public int getSolution(int i, int j) {
    return solution[i][j];
  }

  //Are there only numbers between 0 and 9 in the Sudoku?
  public boolean inputValidation(int[][] board) {
    for (int i = 0; i < GRID_SIZE; i++) {
      for (int j = 0; j < GRID_SIZE; j++) {
        if (board[i][j] < EMPTY || board[i][j] > GRID_SIZE) {
          return false;
        }
        for (int k = 0; k < GRID_SIZE; k++) {
          // More than one appearance in one row
          if (k != j && board[i][k] == board[i][j] && board[i][j] != EMPTY) {
            return false;
          }
          // More than one appearance in one column
          if (k != i && board[k][j] == board[i][j] && board[i][j] != EMPTY) {
            return false;
          }
        }

        // More than one appearance in one 3x3-box
        int row = i - i % 3;
        int column = j - j % 3;

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

    return true;
  }

  // Backtracking-Algorithm

  public int solver(int[][] board, int count) { // Starts with count = 0

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

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

          /*
           * Only empty fields will be changed
           */

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

            /*
             * Try all numbers between 1 and 9
             */

            for (int n = 1; n <= GRID_SIZE && count < 2; n++) {

              /*
               * Is number n safe?
               */
              if (checkRow(board, i, n) && checkColumn(board, j, n) && checkBox(board, i, j, n)) {

                board[i][j] = n;
                int cache = solver(board, count);
                if (cache > count) {
                  count = cache;
                  for (int k = 0; k < board.length; k++) {
                    for (int l = 0; l < board.length; l++) {
                      if (board[k][l] != EMPTY) {
                        solution[k][l] = board[k][l];
                      }

                    }
                  }

                  board[i][j] = EMPTY;

                } else {
                  board[i][j] = EMPTY;
                }

              }
            }
            return count;
          }
        }
      }
      return count + 1;
  }

  // Is number n already in the row?

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

  // Is number n already in the column?

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

  // Is number n already in the 3x3-box?

  private 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;
  }
}

Tests

I've used the sudokus presented here and here to test my application:

import org.junit.Test;
import org.junit.Assert;

public class Tests {

  //Test: Uniquely solveable sudoku
  @Test
  public void testOne() {
    SudokuSolver solver = new SudokuSolver();

    int[][] sudoku = {
        {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}};

    int[][] solution = {
        {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}};

    int result = solver.solver(sudoku, 0);
    Assert.assertEquals(1, result);
    for (int i = 0; i < solution.length; i++) {
      for (int j = 0; j < solution.length; j++) {
        Assert.assertEquals(solution[i][j], solver.getSolution(i, j));
      }
    }
  }

  //Test: Not uniquely solveable sudoku
  @Test
  public void testTwo() {
    SudokuSolver solver = new SudokuSolver();

    int[][] sudoku = {
        {9, 0, 6, 0, 7, 0, 4, 0, 3}, 
        {0, 0, 0, 4, 0, 0, 2, 0, 0}, 
        {0, 7, 0, 0, 2, 3, 0, 1, 0},
        {5, 0, 0, 0, 0, 0, 1, 0, 0}, 
        {0, 4, 0, 2, 0, 8, 0, 6, 0}, 
        {0, 0, 3, 0, 0, 0, 0, 0, 5},
        {0, 3, 0, 7, 0, 0, 0, 5, 0}, 
        {0, 0, 7, 0, 0, 5, 0, 0, 0}, 
        {4, 0, 5, 0, 1, 0, 7, 0, 8},};

    int[][] solution = {
        {9, 2, 6, 5, 7, 1, 4, 8, 3,}, 
        {3, 5, 1, 4, 8, 6, 2, 7, 9,},
        {8, 7, 4, 9, 2, 3, 5, 1, 6,}, 
        {5, 8, 2, 3, 6, 7, 1, 9, 4,}, 
        {1, 4, 9, 2, 5, 8, 3, 6, 7,},
        {7, 6, 3, 1, 9, 4, 8, 2, 5,}, 
        {2, 3, 8, 7, 4, 9, 6, 5, 1,}, 
        {6, 1, 7, 8, 3, 5, 9, 4, 2,},
        {4, 9, 5, 6, 1, 2, 7, 3, 8,}};

    int result = solver.solver(sudoku, 0);
    Assert.assertEquals(2, result);
    for (int i = 0; i < solution.length; i++) {
      for (int j = 0; j < solution.length; j++) {
        Assert.assertEquals(solution[i][j], solver.getSolution(i, j));
      }
    }
  }
}

Github-Repository : https://github.com/vulpini99/Sudoku-Solver

Question(s)

• What do you think about the codestructure?
• What is your opinion on the solving-algorithm?
• How can the code be improved in general?

---

Answer 1

What is your opinion on the solving-algorithm?

Let's do a performance test, here's my test case:

int[][] sudoku = {
    {0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,3,0,8,5},
    {0,0,1,0,2,0,0,0,0},
    {0,0,0,5,0,7,0,0,0},
    {0,0,4,0,0,0,1,0,0},
    {0,9,0,0,0,0,0,0,0},
    {5,0,0,0,0,0,0,7,3},
    {0,0,2,0,1,0,0,0,0},
    {0,0,0,0,4,0,0,0,9}};

On my PC, it took about 10 seconds. As Sudoku solving algorithms go, that's not horrible, but it's also not great. I can wait 10 seconds, but 10 seconds is a lot for a computer, it would be more reasonable to take some miliseconds (or less).

An important technique in constraint solving is propagating the consequences of choosing a particular value for a variable (the cells of a sudoku are variables in Constraint Satisfaction jargon). Propagating the consequences of filling in a cell means filling in other cells that have become "fillable". Doing this prevents the main recursive solver from trying options that are not consistent with the board, but checkRow/checkColumn/checkBlock still think are OK because the cell that would block that value is still empty. Roughly speaking, the more propagation, the better (up to a point).

The easiest propagation strategy is filling in Naked Singles. This can be done by trying all values for all empty cells, but a more efficient technique is collecting a set (or bitmask) of the possible values for all cells at once, and then going through them and promoting the singleton sets to filled-in cells. This is iterated until no more Naked Singles can be found. I benchmarked some code that implements that, that brings the test case that I'm using to around 2.2 seconds.

There are more propagation strategies for Sudoku, for example Hidden Singles. Again they could be found by brute force, but an alternative strategy is re-using the sets/masks from filling in the Naked Singles and using them to find values that are in exactly one of the cells in a row/column/block. There are various ways to do it. I benchmarked this as well, and by analysing the rows and columns (but not blocks) for Hidden Singles, the time improved to less than 0.3 miliseconds.

I can make that code available if you'd like, but perhaps you'd like to try your own approached to these techniques first.

More advanced propagation strategies are possible. Ultimately Sudoku is a game of intersecting AllDifferent constraints, for which there are special propagation techniques based on graph algorithms. There is a video about that on Coursera.

An other possible technique is filling the board in a different order: by order of most-constrained variable (aka cell) first (a common technique in Constraint Satisfaction). The same bitmasks/sets can be used for that as are used for finding Naked Singles. For this benchmark, this technique only helped when not filling Hidden Singles, improving the time to around 80 miliseconds.