Traintrack puzzle game in Python
Traintrack puzzles are one-player games published in some UK newspapers. Here is an example from The Times newspaper Friday June 5 2020:
The objective of the game is to complete the traintrack between start point A and end point B. Each cell can be assigned a horizontal or vertical piece of track, or a track which goes from two adjacent sides. The track cannot cross itself and the puzzle is only complete when the number of pieces of track in each row and column matches the number at the top and side.
More examples of Traintrack puzzles can be found on the Puzzle Phil website.
To solve the puzzle we simply perform a depth-first search starting at the first terminal. At each cell we then calculate the next possible piece that can be connected, and then continue this process until we reach the end terminal cell. If we reach a wall or another piece that we cannot connect to, the algorithm back-tracks and tried other pieces. To make the process slightly more efficient, we do not need to perform an exhaustive search as we can back-track early if find that have already surpassed the number of cells in the current row or column.
After running the application, we are presented with an 8x8 grid of empty cells. We can then change the value of the numerical cells at the top-most row, and on the right-most column by clicking on them. We can also toggle through the possible values for the track cells by clicking on them. See the example below where we build the puzzle from The Times Newspaper:
Once we have created the board, the user can press the PLAY button and manually solve the puzzle:
If we are unable to manually solve the puzzle, we can click the SOLVE button to search for a solution:
For Python we need the following:
pygame (Tested with v1.9.6)
numpy (Tested with v1.18.3)
pip install pygame
pip install numpy