See https://en.wikipedia.org/wiki/Knight%27s_tour or https://en.wikipedia.org/wiki/Polyomino
Published: 15 Sep 2023
To run the solver:
dune exec ./knight_solve.exe # Solve knights_tour
To play the game yourself interactively:
dune exec ./knight_play.exe
There are several 'executables' to run the solver.
To solve classic pentomino puzzle of 'chessboard with missing center':
dune exec ./pento_solve.exe
Solve hexomino puzzle with a similar 'donut' shape:
dune exec ./hexo_solve.exe
This generates all possible hexomino puzzle pieces, randomizes their ordering and then tries to solve them on square board with hole cut out in the middle.
It will keep running untul you press CTRL-C to terminate the process. As the piece order is randomized it will find different solutions each time you run this.
If you want something that produces more 'deterministic results', you can use the command:
dune exec ./solve_file.exe
This will read a puzzle specification from a file called
polymino-puzzle.txt. A sample is included in this repo. You can create your own by editing the file, or you can generate a 'random' hexomino puzzle with:
dune exec ./random_hexo_puzzle.exe
This will generate puzzle like
hexo_solve.exe but instead of solving the puzzle it will write it into a
polymino-puzzle.txt file which you can subsequently solve using
solve_file.exe solver search exhaustively and report 'progress' by:
printing solved boards in the terminal.
drawing the last solved board in a Graphics window.
occasionally drawing partially solved boards in Graphics window.
Note 1: graphical progress reporting is severely limited (only few partial boards are drawn and most are skipped). Drawing the boards is comparatively slow, so skipping it makes the search a lot faster.
Note 2: The total number of solutions to the hexomino puzzles is unknown but it is an astronomically large number and the solver will just keep searching forever until you terminate the process (CTRL-C).
opam install knigths_tour
This puzzle solver was essentially a test-case for experimenting with a general purpose 'searchspace solver'. This is included as a library that might potentially be of use outside of this project.