Modeling the Inglenook Shunting Puzzle
Loading...
Files
Accepted Version
Date
2025-08-11
Authors
Simonis, Helmut
Quesada, Luis
Journal Title
Journal ISSN
Volume Title
Publisher
ModRef 2025
Published Version
Abstract
We present different models for the Inglenook shunting puzzle, a well known problem for model railway enthusiasts. The puzzle consists of rearranging wagons in a railyard with the help of a shunting locomotive to form a train with selected wagons in a specific order. This can also be seen as a deterministic planning problem, where the length of the plan to be generated is not known in advance. Traditionally, these puzzles are solved by hand, there is only limited literature analyzing the puzzle as a combinatorial problem. We present different models of the problem, and compare their efficiency on the different problem sizes. For the default problem size, all states (350k) and moves (2.2M) can be precomputed, the resulting directed graph can then be analyzed using Dijkstra’s shortest path algorithm. We present an alternative view as a Constraint Satisfaction Problem modelled with large table constraints, which we test with different solver backends. Another alternative model uses string constraints to describe the allowed moves, without enumerating all states, we use the Z3 solver to search for solutions. A third model also does not rely on precomputed states, but models the states for a fixed-length path as constraints over finite domain variables. While there is an interest in solving this puzzle on its own, it also provides a scalable benchmark problem to test CP systems with large table constraints, string constraints, or complex logic formulas over finite domains.
Description
Keywords
Planning , Constraint programming , Table constraint , Inglenook puzzle
Citation
Simonis, H. and Quesada, L. (2025) 'Modeling the Inglenook Shunting Puzzle', ModRef 2025: The 24th workshop on Constraint Modelling and Reformulation, part of CP 2025: The 31st International Conference on Principles and Practice of Constraint Programming, 10-15 August, Glasgow, Scotland.