Logical Sudoku Solver in Java

Question

I've been working on a Sudoku solver as an introduction to the Java programming language. I know there's a bunch of ways to program a Sudoku solver, including a brute force/recursive approach and a logical approach. I've chosen the logical approach to start out to keep things simple.

This program solves Sudokus the exact same way I do when I'm using pen and paper. It picks a number, and then it picks a 3x3 region (I call these regions "squares" in my comments), and then it analyzes that region and the rows and columns that intersect it to see what boxes it can eliminate. Once all but one box has been eliminated, then that leaves us with our solved square.

I have big plans for the program, including adding a GUI, adding more logical techniques (Sudoku is surprisingly elaborate, check out all the techniques they have here for example), and adding that recursive/brute force technique in another method. Before I go further however, I'd like to run my code by you guys for review. That way if I have any bad habits we can catch them now.

My background is mainly PHP programming.

SudokuSolver class:

public class SudokuSolver
{
    public static void main(String[] args)
    {
        // score 51 - websudoku.com - medium difficulty - solved in 14 iterations using LAST CANDIDATE
        Sudoku easyToSolve = new Sudoku("036000820009500000800400007600100039003000500920006008500004002000002700071000450");

        // score 57 - websudoku.com - hard difficulty - my solver can't solve this yet - has some HIDDEN SINGLES
        Sudoku hardToSolve = new Sudoku("000007018094150700005600000106000000080070020000000904000003800008029140370400000");

        // Here are the methods you can use here:
        // printPuzzle() - prints the puzzle in a more readable form
        // solvePuzzle() - solves the puzzle
        // solvePuzzle(true) - shows you in detail how it solves the puzzle

        easyToSolve.solvePuzzle(true);
        hardToSolve.solvePuzzle(true);
    }
}

Sudoku class:

import java.util.Arrays;

public class Sudoku
{
    private byte[][] myPuzzle = new byte[][]
    {
        { 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 }
    };

    public Sudoku(String incomingPuzzle)
    {
        if ( incomingPuzzle.length() != 81 )
        {
            System.out.println("Invalid Sudoku puzzle syntax. Should be 81 numbers.");
            System.exit(1);
        }

        for ( int row = 0; row <= 8; row++ )
        {
            for ( int column = 0; column <= 8; column++ )
            {
                myPuzzle[row][column] = convertCharToByte(incomingPuzzle.charAt(row*9+column));
            }
        }

        if ( puzzleIsValid() == false )
        {
            System.out.println("Illegal puzzle.");
            System.exit(1);
        }
    }

    public void printPuzzle()
    {
        for ( byte y = 0; y <=8; y++ )
        {
            for ( byte x = 0; x <=8; x++ )
            {
                System.out.print(myPuzzle[y][x] + " ");
                if ( x == 2 || x == 5 )
                {
                    System.out.print("  ");
                }
            }
            System.out.println();
            if ( y == 2 || y == 5 || y == 8 )
            {
                System.out.println();
            }
        }
    }

    public void solvePuzzle()
    {
        solvePuzzle(false);
    }

    public void solvePuzzle(boolean showDetails)
    {
        // print puzzle in the console
        System.out.println("Unsolved puzzle:");
        printPuzzle();

        byte cyclesElapsed = 1;

        // iterate through each square in a 9x9 sudoku puzzle and try to solve the square
        while ( true )
        {
            byte squaresSolved = 0;

            // We need some way to pause execution if the puzzle either becomes solved or is discovered to be unsolvable.
            boolean somethingChanged = false;

            // check each square
            for ( byte square = 1; square <= 9; square++ )
            {
                // when we do our x-ray checks later we will need to know what row numbers and what column numbers to check
                byte[] coordinates = getSquareCoordinates(square, (byte) 1);
                byte checkThisRowFirst = coordinates[1];
                byte checkThisColumnFirst = coordinates[0];

                // make a boolean array to keep track of whether or not a coordinate in the square can be a solution for that numToCheck
                // true = possibly a solution, false = not a solution
                // once we are down to 1 true and 8 falses, we have solved that numToCheck and can update the box in myPuzzle
                boolean[] possiblyContainsNum = new boolean[] {true, true, true, true, true, true, true, true, true};

                // eliminate all occupied cells in the square
                // iterate through the 9 boxes in the square and plug it into the getSquareCoordinates method
                for ( byte i = 1; i <=9; i++ )
                {
                    byte[] coordinates2 = getSquareCoordinates(square, i);

                    if ( myPuzzle[coordinates2[1]][coordinates2[0]] != 0 )
                    {
                        possiblyContainsNum[i-1] = false;
                    }
                }

                // check each number 1 through 9
                // don't go box by box, go number by number
                for ( byte numToCheck = 1; numToCheck <= 9; numToCheck++ )
                {
                    // does the square contain this number already?
                    // if yes, skip. if no, try to solve
                    if ( squareContainsNumber(square, numToCheck) == false )
                    {
                        // I had possiblyContainsNum inside this loop for awhile, but then I realized it is
                        // more efficient to just compute it once and store it in memory. We'll make a new
                        // possiblyContainsNum for this numToCheck, copying the values of the original calculation
                        // (occupied squares) to start us off
                        boolean[] possiblyContainsNum2 = Arrays.copyOf(possiblyContainsNum, possiblyContainsNum.length);

                        // eliminate x-rays from rows and columns
                        // check the entire row or column (all 9 boxes), easier to code than 6 boxes

                        // row 1
                        if ( rowContainsNumber(checkThisRowFirst, numToCheck) == true )
                        {
                            possiblyContainsNum2[0] = false;
                            possiblyContainsNum2[1] = false;
                            possiblyContainsNum2[2] = false;
                        }

                        // row 2
                        if ( rowContainsNumber((byte) (checkThisRowFirst+1), numToCheck) == true )
                        {
                            possiblyContainsNum2[3] = false;
                            possiblyContainsNum2[4] = false;
                            possiblyContainsNum2[5] = false;
                        }

                        // row 3
                        if ( rowContainsNumber((byte) (checkThisRowFirst+2), numToCheck) == true )
                        {
                            possiblyContainsNum2[6] = false;
                            possiblyContainsNum2[7] = false;
                            possiblyContainsNum2[8] = false;
                        }

                        // column 1
                        if ( columnContainsNumber(checkThisColumnFirst, numToCheck) == true )
                        {
                            possiblyContainsNum2[0] = false;
                            possiblyContainsNum2[3] = false;
                            possiblyContainsNum2[6] = false;
                        }

                        // column 2
                        if ( columnContainsNumber((byte) (checkThisColumnFirst+1), numToCheck) == true )
                        {
                            possiblyContainsNum2[1] = false;
                            possiblyContainsNum2[4] = false;
                            possiblyContainsNum2[7] = false;
                        }

                        // column 3
                        if ( columnContainsNumber((byte) (checkThisColumnFirst+2), numToCheck) == true )
                        {
                            possiblyContainsNum2[2] = false;
                            possiblyContainsNum2[5] = false;
                            possiblyContainsNum2[8] = false;
                        }

                        // check possiblyContainsNum and see how many "true" cells there are
                        // if "true" cells == 1 then we have solved that numToCheck in that square
                        // go ahead and update myPuzzle[][]
                        byte counter = 0;
                        byte k = 0; // this will store the last value of j that was true
                        for ( byte j = 0; j <= 8; j++ )
                        {
                            if ( possiblyContainsNum2[j] == true )
                            {
                                counter++;
                                k = j;
                            }
                        }

                        if ( counter == 1 )
                        {
                            byte[] coordinates3 = getSquareCoordinates(square, (byte) (k+1));
                            myPuzzle[coordinates3[1]][coordinates3[0]] = numToCheck;
                            somethingChanged = true;
                            squaresSolved++;
                        }
                    }
                }
            }

            if ( showDetails == true )
            {
                System.out.println("Iteration " + cyclesElapsed + " complete. Solved " + squaresSolved + " squares.");
                printPuzzle();
            }
            cyclesElapsed++;

            // If no cells were solved during this iteration, that means that the puzzle is completely solved, is completely
            // unsolvable, or is unsolvable using just this technique. Time to exit the loop.
            if ( somethingChanged == false )
            {
                break;
            }
        }

        // do a quick check and make sure the puzzle is solved
        // if it isn't, throw an unsolvable puzzle error
        if ( puzzleIsSolved() == false )
        {
            System.out.println("Unsolvable using just the LAST CANDIDATE technique. More advacned techniques are needed.");
            System.out.println("Try plugging the 81 digit number into the sudoku solver at http://www.sudokuwiki.org/sudoku.htm");
            System.out.println();
            return;
        }

        // print puzzle in the console
        System.out.println("Solved puzzle:");
        printPuzzle();
    }

    private byte convertCharToByte(char f)
    {
        switch ( f )
        {
            case '0':
                return 0;
            case '1':
                return 1;           
            case '2':
                return 2;                   
            case '3':
                return 3;
            case '4':
                return 4;
            case '5':
                return 5;
            case '6':
                return 6;
            case '7':
                return 7;
            case '8':
                return 8;
            case '9':
                return 9;
            default:
                System.out.println("Invalid Sudoku puzzle syntax. Should be 81 numbers.");
                System.exit(1);
        }

        return 0; // the compiler made me put this, logically it should be unreachable
    }

    private boolean puzzleIsValid()
    {
        // 1) check each row and make sure there is only 1 number per row
        for ( byte y = 0; y <=8; y++ )
        {
            // we need a new oneThroughNine for each row, so we'll put this inside the "y" loop
            boolean[] oneThroughNine = new boolean[] {false, false, false, false, false, false, false, false, false};

            for ( byte x = 0; x <=8; x++ )
            {
                if ( myPuzzle[y][x] != 0 )
                {
                    if ( oneThroughNine[myPuzzle[y][x] - 1] == false )
                    {
                        oneThroughNine[myPuzzle[y][x] - 1] = true;
                    }
                    else
                    {
                        return(false);
                    }
                }
            }
        }

        // 2) check each column and make sure there is only 1 number per column
        for ( byte x = 0; x <=8; x++ )
        {
            // we need a new oneThroughNine for each column, so we'll put this inside the "y" loop
            boolean[] oneThroughNine = new boolean[] {false, false, false, false, false, false, false, false, false};

            for ( byte y = 0; y <=8; y++ )
            {
                if ( myPuzzle[y][x] != 0 )
                {
                    if ( oneThroughNine[myPuzzle[y][x] - 1] == false )
                    {
                        oneThroughNine[myPuzzle[y][x] - 1] = true;
                    }
                    else
                    {
                        return(false);
                    }
                }
            }
        }

        // 3) check each square and make sure there is only 1 number per square
        for ( byte square = 1; square <=9; square++ )
        {
            // we need a new oneThroughNine for each square, so we'll put this inside the "y" loop
            boolean[] oneThroughNine = new boolean[] {false, false, false, false, false, false, false, false, false};

            for ( byte i = 1; i <=9; i++ )
            {
                byte[] coordinates = getSquareCoordinates(square, i);

                if ( myPuzzle[coordinates[0]][coordinates[1]] != 0 )
                {
                    if ( oneThroughNine[myPuzzle[coordinates[0]][coordinates[1]] - 1] == false )
                    {
                        oneThroughNine[myPuzzle[coordinates[0]][coordinates[1]] - 1] = true;
                    }
                    else
                    {
                        return(false);
                    }
                }
            }
        }

        return(true);
    }

    private boolean puzzleIsSolved()
    {
        for ( byte y = 0; y <= 8; y++ )
        {
            for ( byte x = 0; x <= 8; x++ )
            {
                if ( myPuzzle[y][x] == 0 )
                {
                    return(false);
                }
            }
        }

        return(true);
    }

    private byte[] getSquareCoordinates(byte squareNumber, byte i)
    {
        byte[] startCoordinates = null;

        switch ( squareNumber )
        {
            case 1:
                startCoordinates = new byte[]{0,0};
                break;
            case 2:
                startCoordinates = new byte[]{3,0};
                break;
            case 3:
                startCoordinates = new byte[]{6,0};
                break;
            case 4:
                startCoordinates = new byte[]{0,3};
                break;
            case 5:
                startCoordinates = new byte[]{3,3};
                break;
            case 6:
                startCoordinates = new byte[]{6,3};
                break;
            case 7:
                startCoordinates = new byte[]{0,6};
                break;
            case 8:
                startCoordinates = new byte[]{3,6};
                break;
            case 9:
                startCoordinates = new byte[]{6,6};
                break;
        }

        byte[] finalCoordinates = null;

        // let's check the square in this order:
        //   1 2 3
        //   4 5 6
        //   7 8 9
        switch ( i )
        {
            case 1:
                finalCoordinates = new byte[] {startCoordinates[0], startCoordinates[1]};
                break;
            case 2:
                finalCoordinates = new byte[] {(byte) (startCoordinates[0]+1), startCoordinates[1]};
                break;
            case 3:
                finalCoordinates = new byte[] {(byte) (startCoordinates[0]+2), startCoordinates[1]};
                break;
            case 4:
                finalCoordinates = new byte[] {startCoordinates[0], (byte) (startCoordinates[1]+1)};
                break;
            case 5:
                finalCoordinates = new byte[] {(byte) (startCoordinates[0]+1), (byte) (startCoordinates[1]+1)};
                break;
            case 6:
                finalCoordinates = new byte[] {(byte) (startCoordinates[0]+2), (byte) (startCoordinates[1]+1)};
                break;
            case 7:
                finalCoordinates = new byte[] {startCoordinates[0], (byte) (startCoordinates[1]+2)};
                break;
            case 8:
                finalCoordinates = new byte[] {(byte) (startCoordinates[0]+1), (byte) (startCoordinates[1]+2)};
                break;
            case 9:
                finalCoordinates = new byte[] {(byte) (startCoordinates[0]+2), (byte) (startCoordinates[1]+2)};
                break;
        }

        return finalCoordinates;
    }

    private boolean squareContainsNumber(byte square, byte numToCheck)
    {
        for ( byte i = 1; i <= 9; i++ )
        {
            byte[] coordinates = getSquareCoordinates(square, i);

            if ( myPuzzle[coordinates[1]][coordinates[0]] == numToCheck )
            {
                return(true);
            }
        }

        return(false);
    }

    private boolean rowContainsNumber(byte rowToCheck, byte numToCheck)
    {
        for ( byte column = 0; column <= 8; column++)
        {
            if ( myPuzzle[rowToCheck][column] == numToCheck )
            {
                return(true);
            }
        }

        return(false);
    }

    private boolean columnContainsNumber(byte columnToCheck, byte numToCheck)
    {
        for ( byte row = 0; row <= 8; row++)
        {
            if ( myPuzzle[row][columnToCheck] == numToCheck )
            {
                return(true);
            }
        }

        return(false);
    }
}

Answer 1

If I were writing this program, I would try to simplify the solver by moving some of the complexity into the board's storage itself, hopefully removing some of it altogether in the process.

Note that I am using some Java 8 features in my code, so if you are using an earlier version you may need to substitute equivalent code for the Optional<Byte> (which is easy enough to just implement yourself) and the stream statements in the last two functions (which could be replaced with some loops and conditionals).

First off, I would use one of these to represent the marks on the grid:

Optional<Byte>

Unfortunately, that class is declared as final, so I can't declare a no-elements subclass to change the name to be clearer what I am using it for.

You also need cells to hold marks in the grid:

class Cell {
    Optional<Byte> value = Optional.empty();
    boolean editable = false;

    public Cell(Optional<Byte> value){
        this.value = value;
        if(!value.isPresent()) editable = true;
    }

    public Optional<Byte> getMark(){
        return value;
    }

    public boolean setMark(Optional<Byte> mark){
        if(!editable) return false;
        this.value = mark;
        return true;
    }
    public boolean isEditable(){
        return editable;
    }
}

The purpose of this is so we can mutate the contents of the board without having to redistribute a new copy to everyone. This will need additional parts (such as extending ReentrantLock) if concurrent access is desired, but most likely YAGNI.

Now, for the game logic itself, instead of hardcoding the restrictions on the cells into the big conditional mess, we can add objects to represent restrictions:

class Constraint {
    Set<Cell> cells = new HashSet<>();
    public Constraint(){}
    public Constraint(Cell ... cells){
        add(cells);
    }
    public Constraint add(Cell ... cells){
        this.cells.addAll(cells);
    }

    Set<Optional<Byte>> allMarks() {
        Set<Optional<Byte>> all = new HashSet<>();
        for(int idx = 0; idx < cells.size(); idx++)
            all.add(Optional.of(idx));
        return all;
    }

    public boolean isViolated(){
        Set<Optional<Byte>> marks = allMarks();
        for(Cell cell: cells)
            if(cell.contents.isPresent() && !marks.remove(cell.contents)) return false;
        return true;
    }
    public boolean isSatisfied(){
        Set<Optional<Byte>> marks = allMarks();
        marks.remove(Optional.empty());
        for(Cell cell: cells)
            if(!cell.contents.isPresent() || !marks.remove(cell.contents)) return false;
        return true;
    }
}

Just have one of these for every row, column, and block.

You then need a class for the board as a whole:

class Board {
    final int DEFAULT_SIZE = 9;

    public Cell [][] cells;
    Set<Constraint> constraints;

    public Board(String contents){
        this(DEFAULT_SIZE, contents);
    }

    public Board(int size, String contents){

        cells = new Cell[size][size];
        constraints = new HashSet<>(3*size);

        List<Constraint> rows = new ArrayList<>(size),
                columns = new ArrayList<>(size),
                blocks = new ArrayList<>(size);

        for(int idx = 0; idx < size; idx++){
            rows.add(new Constraint());
            columns.add(new Constraint());
            blocks.add(new Constraint());
        }

        int sqsize = (int)Math.sqrt(size);

        for(int idx = 0; idx < contents.size(); idx++){
            Cell cell = new Cell(markFor(contents.charAt(idx)));

            cells[idx/size][idx%size] = cell;
            rows.get(idx/size).add(cell);
            columns.get(idx%size).add(cell);
            blocks.get(idx/sqsize+sqsize*idx%sqsize).add(cell);
        }

        constraints.addAll(rows);
        constraints.addAll(columns);
        constraints.addAll(blocks);
    }

    Optional<Byte> markFor(char ch, int range){
        if(ch == ' ') return Optional.empty();
        else return Optional.of(Byte.valueOf(ch.toString(), range)));
    }


    public Set<Constraint> constraintsViolated(){
        return constraints.stream()
                .filter(c->c.isViolated())
                .collect(Collectors.toCollection(HashSet::new));
    }

    public Set<Constraint> constraintsNotSatisfied(){
        return constraints.stream()
                .filter(c->!c.isSatisfied())
                .collect(Collectors.toCollection(HashSet::new));
    }
}

The solver code can be far simplified if you use structures like this to store your data.

Answer 2

Quitting an application

if ( incomingPuzzle.length() != 81 )
{
    System.out.println("Invalid Sudoku puzzle syntax. Should be 81 numbers.");
    System.exit(1);
}

This is not a good way to quit an application where you use it. When you're in a class and you encounter an invalid state for your application, throw an exception. It's not the responsibility of the class to decide if you should terminate the application or not. If you throw an exception, you can control the flow of your application.

In a small program, you won't see the drawback of using this, but in more complex application you will likely want to close your application in a graceful manner. Even for your application you could want someday to save the state of the Sudoku you're working with maybe.

In your case, you could probably throw IllegalArgumentException, this is a RuntimeException taht unless explicitly catch somewhere, will terminate the application. The advantage of using an exception vs System.exit is that you could decide to catch the exception and terminate the application with what you need to do.

Boolean if

if ( showDetails == true )

This is the same as this :

if (showDetails)

I suggest you check directly with the boolean, it will remove "noise" form your code.

Method with boolean argument

The first time I read your main, I find it hard to understand what solvePuzzle(true) was suppose to mean. I needed to read a comment and look at the method to know that this turn on a more detailed output. I'm not a fan of this approach. I could suggest that you create a another method which would look like this :

public void solvePuzzleWithDetails()
{
    solvePuzzle(true);
}

You can now know simply by reading the method name that you will have more details in your output.

Answer 3

It looks good overall, but I have some comments:

1. Small detail: the starting curly brace in Java goes at the end of the line instead of on a new line. It's a small detail, but you never see Java code with the indentation you used (PHP).

2. Another small detail: the parentheses in return (false); look odd.

3. byte[][] myPuzzle = new byte[9][9]; sets everything to 0 by default. Java guarantees this; probably PHP does not.

4. As pointed out by Marc-Andre, it's better to throw exceptions when you fail rather then printing a sentence and then calling System.exit(1). It's really the same thing.

5. I would make this more OO by creating an interface SudokuSolver with a method solve(Sudoku). Your current algorithm would be one implementation (subclass) of this interface. If you code different solver algorithms, you just have to make them different implementations of SudokuSolver. The class Sudoku would then only represent the board and maybe you should rename such a class to SudokuBoard.

6. Some of your methods are too long. You should break long methods into shorter methods.

7. You don't need convertCharToByte: you can use Byte.parseByte(String.valueOf(someChar)).

8. getSquareCoordinates() has two series of swich-case statements. You can probably simplify that with a simple math formula. (I have not tried to do so).

Answer 4

A thing to consider may be all the System.out.println("") statements. In a later stage of your application, when an other GUI than the console is used, this statement will (maybe) not be helpful anymore, because the application will run without console.

Splitting your application a bit more into a core part (solving the Sudoku) and a GUI part (with Interface) can help. So the interface could have a printMessage method and the GUI (the console at the moment) can display it in any suitable form.

Once I used Apache Log4J and used different appender for different GUI.

I'm out of Java for some time now, maybe better solutions are available

Answer 5

A style thing: most of the methods in your class Sudoku are called things like printPuzzle, showPuzzle, etc. If these were instance methods of a class called Puzzle, it would be unnecessary to call them all this. They would be better named print, show, etc.

In your case the class is actually called Sudoku. Perhaps it would be better named Puzzle? Or perhaps Puzzle should actually be a different class, and the methods somethingPuzzle should be in that class?

In any case, there shouldn't be a discrepancy between what you call the class, and the word you use in your head to think about the object concerned, and the names of methods shouldn't be redundant.

I know this might seem trivial, but naming things correctly does make a difference, to how you document and how you are able to maintain your code. If object-oriented code involves objects, each of which we can point at and explain simply what it does, it can be very clean and straightforward. When we lose this, it can get very confusing quite fast.

Answer 6

A few add-ons to what others have mentioned:

• If its possible to avoid multiple switch statements with a simple if-else, do it.

  private byte convertCharToByte(char f)
  {
      int cellVal = f - '0';
      if( cellVal>=0 && cellVal<=9){
          return cellVal;
      }else{
           // throw an exception.
      }
  }
  

• The other one is the switch(squareNumber) with

  int rowNum = 3*((squareNumber-1)%3);
  int colNum = 3*((squareNumber-1)/3);
  startCoordinates = new byte[]{rowNum, colNum};
  

• Similarly for finalCoordinate

  int rowOffset = ((squareNumber-1)%3);
  int colOffset = ((squareNumber-1)/3);
  finalCoordinates = new byte[] {(byte) (startCoordinates[0]+rowOffset ), (byte) (startCoordinates[1]+colOffset )};
  

• Try your solver for the world's hardest sudoku.

A suggestion:

• Aim for a generic implementation. Why 9x9 only, why not 3x3, 4x4 ,etc.
• Have the rowNum and colNum as the class members and calculate based on it.

You will savour your implementation :)

Answer 7

You have already got lot's of good suggestions. I just want to add one more thing, you can simplify your if conditions. for example Condition if (puzzleIsValid() == false) which can be simplified as if (!puzzleIsValid()). Condition if (rowContainsNumber(checkThisRowFirst, numToCheck) == true) can be simplified as if (rowContainsNumber(checkThisRowFirst, numToCheck).