Santa-Chilly Solver

An exact solver for the Santa-Chilly puzzle from c't 28/2023. The puzzle itself, along with its code, lives in a separate repository: https://github.com/607011/chilly/

This solver is the subject of my article Traveling Santa Problem in c't 15/2024, pp. 130-135, which derives the GTSP → ATSP → STSP transformation in detail.

Result: a provably optimal 103-move route, solved by Concorde in a fraction of a second with negligible memory. According to c't, the other submitted solvers needed minutes of computation or gigabytes of memory to find the optimal solution.

(Eine deutsche Fassung dieses Dokuments findet sich in README.de.md.)

The puzzle is a Traveling Salesman Problem (TSP). The presents to be collected are the cities and the game character, Chilly, is the salesman. The distance between two cities is the number of moves required to get from one present to the next.

• Because the character slides rather than steps, the moves are asymmetric. The distance from present A to present B is usually different from the distance from B to A.
• The character rarely comes to rest on the present itself. A present can be collected from several directions, so the position after collecting it varies, and so do all subsequent moves.

To handle the asymmetry, the problem is modelled as an asymmetric TSP, in which the edges between cities are directed.

To handle the varying resting positions, the set of possible end positions after collecting a given present is treated as a cluster of cities, of which exactly one must be visited. This is known as the generalized TSP.

Rather than implementing a TSP solver, the problem is exported to a TSPLIB file and handed to a proven exact solver: Concorde. Concorde is both faster and provably optimal, which a hand-rolled solver would not have been; the work of this project is turning the puzzle into something Concorde can accept.

Once Concorde has been compiled against the QSopt library, running concorde chilly.tsp produces a chilly.sol file, which this project reads back in.

Concorde is free for academic research. William Cook, the license holder, kindly granted permission to use and reference it in the context of the Chilly challenge.

1. Simulating the game yields a graph of every possible move. Moves that collect a present are recorded separately, which is what later provides the city-cluster information.
2. The shortest paths between all presents are computed with Dijkstra's algorithm, producing a reduced graph in which the presents are the nodes and the move counts from the first graph are the arc weights. This graph represents a generalized TSP.
3. To eliminate the clusters so that a general TSP solver can be used, the nodes of each cluster are connected by zero-weight arcs and their outgoing arcs are shifted to the preceding node in the cycle. The method is due to Noon and Bean [1]; a short summary is on the Set TSP problem page.
4. Since not every TSP solver handles the asymmetric case, the asymmetric matrix is converted into a symmetric one with twice the number of rows and columns, following Jonker and Volgenant [2]; a short summary is here. That matrix is then written to chilly.tsp.

The level described in level.txt is converted by this application into chilly.tsp. A TSP solver then produces chilly.sol, from which the application derives the following 103-move solution:

RULDLDLDULRUDDLULDLULULULULDLRULURDLDLURULDLDRDLDLDLDRULDLULULDRURUDLDLRUDRULDRDLRURDRDRDRDRURLDLDRDLDR

Requires JRE 17 or later.

The executable can be downloaded from the releases page.

Unpack the .zip or .tar archive. For a different puzzle, adjust the level.txt file in the working directory; its format is described below.

Start the program with

bin/chilly

or, on Windows

bin\chilly.bat

If an executable named concorde is found on the PATH, it is fed the chilly.tsp file. If all goes well, the solution appears on standard output.

Code changes are needed to experiment with, say, the OR-Tools, in which case the project has to be rebuilt.

A JDK 17 installation is required. Gradle does not need to be installed separately, as the project ships a Gradle wrapper.

./gradlew run --quiet --console=plain

On Windows:

gradlew.bat run --quiet --console=plain

To solve a different level, adjust level.txt.

The first line lists the connections between the holes, with indices starting at (0,0) in the top left corner of the board. The following lines describe the board itself: each character is one field, and every line is terminated by a | symbol.

The LevelValidityChecker looks for syntax errors only. It makes sure that a level file parses into a well-formed board. Whether the resulting level is playable is not checked, and the model itself makes assumptions about a level as well. Three cases are known to be handled badly.

Rows and columns without an obstacle. If a row or a column contains neither a tree, a rock nor a hole, Chilly never comes to rest when sliding along it. This is not detected. Depending on the direction, the move either throws an ArrayIndexOutOfBoundsException or loops forever.

Connections that do not match the board. The connections listed in the first line of the level file are not checked against the board. Every coordinate that starts a connection is expected to be an O field, because the search for presents along a move treats an O as the end of the slide, while the move itself follows the connection. If the two disagree, the computed distances are wrong and no warning is given.

Several presents collected by one move. A move is modelled as collecting at most one present. If a slide passes over two of them, the second one is not recorded. The solver then either schedules a further move to collect it, which makes the solution longer than necessary, or, if no other move collects that present, drops it from the problem entirely. Unlike the other two cases, this yields a wrong answer without reporting an error.

[1] C. E. Noon, J. C. Bean, An Efficient Transformation of the Generalized Traveling Salesman Problem, INFOR: Information Systems and Operational Research 31(1), 1993. DOI: 10.1080/03155986.1993.11732212

[2] R. Jonker, T. Volgenant, Transforming asymmetric into symmetric traveling salesman problems, Operations Research Letters 2(4), 161–163, 1983. DOI: 10.1016/0167-6377(83)90048-2