in Prolog, Puzzle solving

Icosian game

The Irish mathematician William Rowan Hamilton is probably best known for discovering quaternions. He is also the inventor of the Icosian game.

The game’s objective is to find a path around a dodecahedron such that every vertex is visited once, no edge is visited multiple times, and the path ends in de same vertex it started from. Instead of using a 3d dodecahedron, the game was distributed as a pegboard with holes at the vertices of the 2d dodecahedral graph.

The game was meant to be played by two people. The first player would set up the challenge by placing the first five pegs in any five consecutive holes and then the second player would be required to place the remaining fifteen pegs consecutively in such a way that the succession would be cyclical.

One of the few remaining copies (from the collection of the puzzle museum)

In graph theory, a path that visits every vertex of a graph once is now known as a Hamiltonian path. A path that visits every vertex once and that ends in the same vertex as it started off from is called a Hamiltonian cycle. So playing this game is essentially searching for a Hamiltonian cycle in the dodecahedral graph.

The Icosian game was never a commercial success, probably because it’s too easy. I wrote some Prolog code to solve this game and explore possible solutions. Entering solve_icosian_puzzle. and pressing ; repeatedly will yield possible solutions.

Suppose you want to explore how the cycle that starts with the vertices Q, R, S, N, P could be continued, you would enter:

icosian_puzzle_edges(Adj), Tour = [q,r,s,n,p|Rest], hamiltonian_cycle(Adj,Tour), print_icosian_solution(Tour).

This game might remind you of the Travelling Salesman Problem (TSP). Finding a Hamiltonian cycle can be considered a special case of the TSP, namely, one where each pair of vertices with an edge between them has distance 1, while vertex pairs without an edge between them are separated by a distance of infinity.

Write a Comment

Comment