Solver for logic puzzles, easily extensible for other kind of puzzles
This solver for logic puzzles is intended to follow the same reasoning as humans do, while solving logic puzzles. Initially, this code is written to solve Sudokus (and variants of that puzzle), however it may be extended easily for other logic puzzles.
A puzzle has a form of input. In case of a sudoku this is the 9x9 grid with some numbers filled in. For other types of puzzles the input is different.
Using the input, a working input is generated. In this data form the data is expanded into a form which can be used for solving the puzzle.
A solver solves a puzzle given the puzzle working input and a set of strategies. If no more conclusions can be made the puzzle has either been solved or cannot be solved using the available strategies.
A strategy solves a very small part of the puzzle, by making conclusions based on the working input of the puzzle. In case of a sudoku, for example a row with every number between 1 and 9 filled in may be concluded that the remaining number has to be filled in in the empty square.
The output of the puzzle may be in the same form as the input, or in a different form. The output may contain a solved puzzle, or a partially solved puzzle with error messages why the puzzle could not be solved.
Run the command ./gradlew build. The tests are run automatically.
Run the command ./gradlew test.
Below are a few examples of puzzles which can be solved using the logic solver.
val input = Sudoku.readFromString("""
. . . . 4 5 . . 9
9 5 . . . 7 3 2 .
. 8 2 . 6 . 1 . .
6 7 . 4 . 8 9 . 2
. 1 5 6 . 9 4 . .
. . . . . . . . 8
. 3 . . 7 . . . 1
. . 7 8 . . . 4 .
. 4 6 3 . 2 7 . 5
""")
val output = SudokuSolver().solve(input)
The variable output will be
3 6 1 2 4 5 8 7 9
9 5 4 1 8 7 3 2 6
7 8 2 9 6 3 1 5 4
6 7 3 4 5 8 9 1 2
8 1 5 6 2 9 4 3 7
4 2 9 7 3 1 5 6 8
2 3 8 5 7 4 6 9 1
5 9 7 8 1 6 2 4 3
1 4 6 3 9 2 7 8 5
The Sudoku X has two diagonals on which all numbers from 1 till 9 are allowed exactly once.
val input = SudokuX.readFromString("""
. 3 . . 8 . . . .
9 . 6 5 3 7 . . .
2 . . . 9 . . . 5
. . 3 . . . 1 . 8
. . 9 8 . 6 3 . .
8 . 5 . . . 6 . .
1 . . . 6 . . . 4
. . . 1 5 8 7 . 2
. . . . 2 . . 1 .
""")
val output = SudokuSolver().solve(input)
The variable output will be
5 3 1 2 8 4 9 7 6
9 4 6 5 3 7 2 8 1
2 8 7 6 9 1 4 3 5
6 7 3 9 4 5 1 2 8
4 2 9 8 1 6 3 5 7
8 1 5 3 7 2 6 4 9
1 5 2 7 6 3 8 9 4
3 9 4 1 5 8 7 6 2
7 6 8 4 2 9 5 1 3
The Sudoku Hyper has four blocks in which all numbers from 1 till 9 are allowed exactly once.
val input = SudokuHyper.readFromString("""
7 . 3 . . 8 5 . .
. . . . . 5 1 . 9
5 . . . . . . 7 .
. . 4 . . . . 3 8
. . 6 . 5 . 7 . .
8 3 . . . . 2 . .
. 1 . . . . . . 4
6 . 9 2 . . . . .
. . 5 4 . . 9 . 2
""")
val output = SudokuSolver().solve(input)
The variable output will be
7 9 3 1 4 8 5 2 6
4 6 2 3 7 5 1 8 9
5 8 1 9 6 2 4 7 3
1 5 4 7 2 9 6 3 8
9 2 6 8 5 3 7 4 1
8 3 7 6 1 4 2 9 5
2 1 8 5 9 7 3 6 4
6 4 9 2 3 1 8 5 7
3 7 5 4 8 6 9 1 2
The double sudoku has two sudokus of which the bottom three blocks coincide with the top three blocks of the other.
val input = SudokuDouble.readFromString("""
. 8 1 . 4 . 7 3 .
. 4 9 . . . 8 1 .
. . . . 5 . . . .
6 . 4 . . . 9 . 7
. . . . . . . . .
7 . . 5 9 4 . . 3
. . . 6 . 5 . . .
. . . . 1 . . . .
. . . 4 . 8 . . .
6 . . 3 7 2 . . 5
. . . . . . . . .
8 . 3 . . . 6 . 1
. . . . 6 . . . .
. 4 6 . . . 8 3 .
. 8 1 . 5 . 2 9 .
""")
val output = SudokuSolver().solve(input)
The variable output will be
5 8 1 2 4 9 7 3 6
2 4 9 3 7 6 8 1 5
3 7 6 8 5 1 2 9 4
6 5 4 1 8 3 9 2 7
8 9 3 7 6 2 5 4 1
7 1 2 5 9 4 6 8 3
1 3 8 6 2 5 4 7 9
4 2 5 9 1 7 3 6 8
9 6 7 4 3 8 1 5 2
6 1 4 3 7 2 9 8 5
2 5 9 1 8 6 7 4 3
8 7 3 5 4 9 6 2 1
7 9 2 8 6 3 5 1 4
5 4 6 2 9 1 8 3 7
3 8 1 7 5 4 2 9 6
The sudoku samurai has five sudokus that are connected by four blocks of nine values.
val input = SudokuSamurai.readFromString("""
. 4 9 . . . . 7 3 3 9 . . . . 8 2 .
2 . 8 . . . 1 . 5 2 . 8 . . . 6 . 9
5 6 . . . . 4 8 . . 6 7 . . . . 1 3
. . . . 9 5 . . . . . . 3 6 . . . .
. . . 8 . 1 . . . . . . 5 . 2 . . .
. . . 7 6 . . . . . . . . 7 9 . . .
. 2 5 . . . . 6 7 . . . 8 4 . . . . 7 3 .
8 . 6 . . . 3 . 4 . 7 . 9 . 6 . . . 2 . 4
7 3 . . . . 5 2 . . . . . 3 1 . . . . 5 6
. . . 1 . 4 . . .
. 8 . . . . . 1 .
. . . 5 . 7 . . .
5 1 . . . . 6 9 . . . . . 2 7 . . . . 9 8
3 . 8 . . . 4 . 1 . 6 . 3 . 5 . . . 4 . 2
. 4 7 . . . . 5 2 . . . 4 6 . . . . 7 1 .
. . . 1 5 . . . . . . . . 4 1 . . .
. . . 6 . 8 . . . . . . 3 . 5 . . .
. . . . 9 4 . . . . . . 6 9 . . . .
1 6 . . . . 2 8 . . 9 1 . . . . 4 3
2 . 9 . . . 1 . 4 2 . 4 . . . 6 . 1
. 5 4 . . . . 3 7 5 7 . . . . 8 2 .
""")
val output = SudokuSolver().solve(input)
The variable output will be
1 4 9 2 5 8 6 7 3 3 9 5 4 1 6 8 2 7
2 7 8 4 3 6 1 9 5 2 1 8 7 5 3 6 4 9
5 6 3 9 1 7 4 8 2 4 6 7 9 2 8 5 1 3
6 8 7 3 9 5 2 4 1 5 8 9 3 6 1 4 7 2
9 5 4 8 2 1 7 3 6 6 7 3 5 4 2 1 9 8
3 1 2 7 6 4 8 5 9 1 2 4 8 7 9 3 6 5
4 2 5 1 8 3 9 6 7 3 1 5 8 4 2 6 9 5 7 3 1
8 9 6 5 7 2 3 1 4 8 7 2 9 5 6 1 3 7 2 8 4
7 3 1 6 4 9 5 2 8 9 4 6 7 3 1 2 8 4 9 5 6
2 3 5 1 9 4 6 7 8 .
7 8 9 6 2 3 5 1 4 .
1 4 6 5 8 7 2 9 3 .
5 1 2 4 8 7 6 9 3 4 5 8 1 2 7 4 5 6 3 9 8
3 9 8 5 2 6 4 7 1 2 6 9 3 8 5 9 1 7 4 6 2
6 4 7 9 1 3 8 5 2 7 3 1 4 6 9 8 2 3 7 1 5
9 3 6 1 5 2 7 4 8 6 5 8 2 4 1 9 3 7
4 2 5 6 7 8 3 1 9 9 4 2 3 7 5 1 8 6
7 8 1 3 9 4 5 2 6 7 1 3 6 9 8 2 5 4
1 6 3 7 4 9 2 8 5 8 9 1 7 6 2 5 4 3
2 7 9 8 3 5 1 6 4 2 3 4 5 8 9 6 7 1
8 5 4 2 6 1 9 3 7 5 7 6 1 3 4 8 2 9
The sudoku tiny has a 6x6 grid with 2x3 blocks. The numbers between 1 and 6 must be filled in, but otherwise the same rules apply as normal sudokus
val input = SudokuTiny.readFromString("""
. . . 6 4 2
. . . . . .
. . . . . 6
. . . . 3 .
4 . 5 . . .
2 . 6 5 . .
""")
val output = SudokuSolver().solve(input)
The variable output will be
3 5 1 6 4 2
6 2 4 3 5 1
5 4 3 1 2 6
1 6 2 4 3 5
4 1 5 2 6 3
2 3 6 5 1 4