# 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.

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.

# Skyline puzzle

One of my coworkers brought the following puzzle to work:

The puzzle is called Skyline and it’s a packing puzzle. The objective is to place the metal rod in one of the holes in the base and place the nine wooden pieces around it. It was designed by Jean Claude Constantin. When solved, the puzzle looks something like this:

Sometimes with these kinds of puzzles it’s quicker to write a program that finds a solution than trying to solve it by hand. Check out this github repository for a Prolog program that finds solutions for a given rod location.

To use this program open the file skyline.pl in your favorite Prolog interpreter (e.g. SWI-Prolog) and execute the following:

```?- print_solution(pos(4,4)).
+-------+
|ggeeeeh|
|gggdehh|
|ggiddhh|
|iii ddh|
|iiicfff|
|bicccff|
|baaaaaf|
+-------+
true```

You can press ; to find alternative solutions. The pos(X,Y) part refers to the location of the metal rod.

# Bridge and torch puzzle

Four people need to cross a bridge at night which only supports two people at the same time. Person A needs 1 minute to cross the bridge, B needs 2 minutes, C needs 5 minutes and D needs 10 minutes. When two people cross the bridge they move at the slowest person’s pace.  They have a torch which has battery left for only 17 minutes. They can’t cross the bridge without light. How can they manage to cross the bridge?

One might guess that an obvious solution would be to let the fastest person (A) shuttle each other person over the bridge and return alone with the torch. This would give the following schedule:

 A, B -> 2 A <- 1 A,C -> 5 A <- 1 A,D -> 10

The total duration of this schedule would be 19 minutes, so the torch would run out of battery while person A and D are still on the bridge.

The optimal solution consists of letting the two slowest people (C and D) cross the bridge together, giving the following schedule:

 A, B -> 2 B <- 2 C,D -> 10 A <- 1 A,B -> 2

Which gives a total crossing time of exactly 17 minutes.

Writing a prolog program to solve this kind of river crossing problems is a walk in the park. Check it out if you want to know an alternative solution.

# Einstein’s riddle

The following puzzle is said to be invented by Einstein. Supposedly, he also claimed that only 2% of the world’s population would be smart enough to solve it.

There are 5 houses in 5 different colors in a row. In each house lives a person with a different nationality. These 5 owners drink a certain drink, smoke a certain brand of cigar, and keep a certain pet. No owners have the same pet, smoke the same brand of cigar or drink the same drink.

The question is: WHO OWNS THE FISH?

HINTS:

• the Brit lives in the red house
• the Swede keeps dogs as pets
• the Dane drinks tea
• the green house is on the immediate left of the white house
• the green house owner drinks coffee
• the person who smokes Pall Mall rears birds
• the owner of the yellow house smokes Dunhill
• the man living in the house right in the center drinks milk
• the Norwegian lives in the first house
• the man who smokes blends lives next to the one who keeps cats
• the man who keeps horses lives next to the one who smokes Dunhill
• the owner who smokes Bluemaster drinks beer
• the German smokes prince
• the Norwegian lives next to the blue house
• the man who smokes blends has a neighbor who drinks water

Working out the solution with nothing more that a pen and some paper is certainly doable by, I suspect hope, a larger percentage of people than the 2 % mentioned above. But as an example of how to solve these kinds of logic puzzles using Prolog, I wrote this code.

# Sudoku solver

It’s pretty straightforward to make a Sudoku solver in Prolog especially when applying CLP (Constraint Logic Programming).

Here is how to use my program:

`:- solve_sudoku.`

Then you can enter the known numbers one by one.

```+-+-+-+-+-+-+
|9 8| 5 |  7|
|72 |1```

When complete, the program determines and prints the solution.

```+-+-+-+-+-+-+
|938|254|617|
|726|193|854|
|514|876|329|
+-+-+-+-+-+-+
|692|387|145|
|187|465|293|
|453|921|768|
+-+-+-+-+-+-+
|345|712|986|
|871|649|532|
|269|538|471|
+-+-+-+-+-+-+```

Typing

`:- sudoku(L), write_sol(L).`

Gives

```+-+-+-+-+-+-+
|123|456|789|
|456|789|123|
|789|123|456|
+-+-+-+-+-+-+
|214|365|897|
|365|897|214|
|897|214|365|
+-+-+-+-+-+-+
|531|642|978|
|642|978|531|
|978|531|642|
+-+-+-+-+-+-+```

By pressing ; over and over again, you could enumerate all 6,670,903,752,021,072,936,960 possible Sudoku solution grids, but this might take a while..

It shouldn’t be too hard to extend this program to actually create new puzzles. If anyone does, let me know.

The prolog environment I used here is SWI-Prolog.