# Gold Mine Solver

Gold Mine is yet another ingenious puzzle from SmartGames. Here you help a dwarf in a cave to get to one or more piles of gold by placing transparent tiles with ladders. (The position of the dwarf and the gold is fixed by the puzzle.)

An example solution from the rulebook:

We are going to use a bottom-up approach.

## Representation

The cave is a 7x4 grid where most cells are connected horizontally, but no cells are connected vertically (by default):

1 2 3 4 5 6 7
1 _______ _____
2 ___ _____ ___
3 _ _____ _____
4 _____ ___ ___

So a position is a pair of coordinates in this range:

position(X-Y) :- between(1, 7, X), between(1, 4, Y).

A puzzle always fixes the position of the dwarf and the gold, so we can represent it as puzzle(N, Dwarf, Golds), where N is the problem’s number. For example:

puzzle(1, 5-4, [7-4]).
puzzle(26, 5-2, [4-1,5-1,2-3]).
puzzle(48, 1-1, [5-2,2-3,6-3]).

There are 3 ladder tiles, two of which can be rotated in two ways:

Type 1:
..||..

Type 2:
||..||..   or  ..||..||

Type 3:
||             ||..
..||       or    ||

These can be described as ladder(Type-Rotation, Position), where the first argument can take the values

• 1-n/a (rotation is N/A)

• 2-left or 2-right (depending on which side the ladders are skewed to)

• 3-bottom or 3-top (depending on the position of the cell without a ladder)

So the possible values are described by the following rule:

direction(1, n/a).
direction(2, left).
direction(2, right).
direction(3, bottom).
direction(3, top).

The second argument is the anchor position of the ladder tile, for which we will always use the top-left cell of the tile.

## Connections

We need to know which cells are connected to a given cell. This is partly defined by the cave, but we also need to take the ladders into account. These will be handled by the connected(Ladders, Pos, Adjacent) rule.

We can move left in the cave if we are not in the first column, and if we are not at the left end of a “room”:

connected(_, X-Y, X1-Y) :-
X > 1, X1 is X - 1,
\+ member(X-Y, [5-1,3-2,6-2,2-3,5-3,4-4,6-4]).

Similarly for moving right:

connected(_, X-Y, X1-Y) :-
X < 7, X1 is X + 1,
\+ member(X-Y, [4-1,2-2,5-2,1-3,4-3,3-4,5-4]).

Moving up or down is a bit more complex. We can move up if there is a ladder at the current cell, and we can move down if there is a ladder at the target cell. We are going to use the DY variable to show the relative y-coordinate where the ladder needs to be. Otherwise it is just a switch-case on the ladder type:

connected(Ladders, X-Y, X-Y1) :-
( Y > 1, Y1 is Y - 1, DY = 0
; Y < 4, Y1 is Y + 1, DY = 1
),
Lx =:= X - 1, Ly =:= Y + DY
( Lx =:= X ; Lx =:= X - 2 ), Ly =:= Y + DY
( Lx =:= X - 1 ; Lx =:= X - 3 ), Ly =:= Y + DY
( Lx =:= X, Ly =:= Y + DY ; Lx =:= X - 1, Ly =:= Y + DY - 1 )
).

## Occupancy

Tiles cannot be placed on top of each other, so we need to be able to decide whether a given cell is already occupied by a cell. Here the dwarf and gold tiles also count, but they are the easiest to handle. We represent them by their position, which is the only cell they occupy:

occupies(X-Y, X-Y).

A type-1 ladder occupies its anchor position and also two cells to the right:

occupies(ladder(1-_, X-Y), X1-Y) :- between(0, 2, DX), X1 is X + DX.

Similarly for a type-2 ladder (with three cells to the right):

occupies(ladder(2-_, X-Y), X1-Y) :- between(0, 3, DX), X1 is X + DX.

A type-3 ladder always occupies the anchor position and the cell to the right and below:

occupies(ladder(3-_, X-Y), X1-Y1) :- X1 is X + 1, Y1 is Y + 1.

Depending on its orientation, it also occupies the cell either below to the right of the anchor position:

occupies(ladder(3-bottom, X-Y), X-Y1) :- Y1 is Y + 1.
occupies(ladder(3-top, X-Y), X1-Y) :- X1 is X + 1.

## Placement

Now we can place ladders. The place(Tiles, Type Tiles1) rule adds a ladder of the given type to the input list of tiles:

place(Tiles, Type, [Ladder|Tiles]) :-
direction(Type, Dir),
position(Pos),
\+ ( occupies(Ladder, P1),
member(T, Tiles),
occupies(T, P2),
P1 = P2
).

In other words:

1. First it checks if this tile is not already placed.

2. It chooses a suitable direction for the tile.

3. It chooses a suitable position for the tile.

4. It checks that all cells occupied by the tile are valid positions (not outside the board).

5. It checks that no cell occupied by the ladder tile is already occupied by another tile.

## Solver

We have a rule for connectedness, but we also need a rule to decide whether there is a path between two cells.

Obviously, position Pos2 can be reached from Pos1 when the two are connected:

reaches(Ladders, Pos1, Pos2, _) :- connected(Ladders, Pos1, Pos2).

It can also be reached if there is another position P that is connected to Pos1 and can reach Pos2. Here we need to be careful, and note the positions we have already visited, lest we get in an infinite cycle:

reaches(Ladders, Pos1, Pos2, Visited) :-
\+ member(P, Visited),
reaches(Ladders, P, Pos2, [P|Visited]).

Finally, we can write our solver. It places the dwarf, the piles of gold, the three ladders, and checks that the dwarf can reach the gold:

solve(Dwarf, Golds, Ladders) :-
place([Dwarf|Golds], 1, T1),
place(T1, 2, T2),
place(T2, 3, Tiles),
findall(L, ( member(L, Tiles), L = ladder(_,_) ), Ladders),
forall(member(Gold, Golds), reaches(Ladders, Dwarf, Gold, [])).

(Since Tiles contains the positions for the dwarf and the gold as well, we remove them before the final check.)

## Tests

?- puzzle(1, D, G), solve(D, G, L).

?- puzzle(26, D, G), solve(D, G, L).

?- puzzle(48, D, G), solve(D, G, L).

Nice!

## Experiments

A natural question to ask is how many puzzles are there? By “puzzles” I mean unambiguous puzzles, of course. First note that the dwarf and the piles of gold are not different at all, so a puzzle is just a list of 2 to 4 positions that are to be connected by the ladders:

unambiguous(Items, Solution) :-
between(2, 4, N),
length(Items, N),
maplist(position, Items),
sorted(Items),
Items = [Dwarf|Golds],

Here we require that these “items” are sorted, so each case is only checked once. We arbitrarily set the dwarf as the first item, and check if there is only a single solution.

The sorted/1 rule is quite trivial:

sorted([_]).
sorted([X,Y|Xs]) :- X @< Y, sorted([Y|Xs]).

This runs for a long time …

?- unambiguous(P, S), write(P), write(' -> '), write(S), nl, fail.

There are 965 puzzles: 9 with 1 pile of gold, 165 with 2 piles of gold, and 791 with 3 piles of gold.

That’s quite a lot … how many puzzle candidates are there? It’s just the number of combinations:

• C(7 * 4, 2) = 378 (so 2.4% is unambiguous)

• C(7 * 4, 3) = 3276 (so 5% is unambiguous)

• C(7 * 4, 4) = 20475 (so 3.9% is unambiguous)

In overall, almost 4% of all combinations are unambiguous.

## The whole program

position(X-Y) :- between(1, 7, X), between(1, 4, Y).

puzzle(1, 5-4, [7-4]).
puzzle(26, 5-2, [4-1,5-1,2-3]).
puzzle(48, 1-1, [5-2,2-3,6-3]).

direction(1, n/a).
direction(2, left).
direction(2, right).
direction(3, bottom).
direction(3, top).

connected(_, X-Y, X1-Y) :-
X > 1, X1 is X - 1,
\+ member(X-Y, [5-1,3-2,6-2,2-3,5-3,4-4,6-4]).
connected(_, X-Y, X1-Y) :-
X < 7, X1 is X + 1,
\+ member(X-Y, [4-1,2-2,5-2,1-3,4-3,3-4,5-4]).
connected(Ladders, X-Y, X-Y1) :-
( Y > 1, Y1 is Y - 1, DY = 0
; Y < 4, Y1 is Y + 1, DY = 1
),
Lx =:= X - 1, Ly =:= Y + DY
( Lx =:= X ; Lx =:= X - 2 ), Ly =:= Y + DY
( Lx =:= X - 1 ; Lx =:= X - 3 ), Ly =:= Y + DY
( Lx =:= X, Ly =:= Y + DY ; Lx =:= X - 1, Ly =:= Y + DY - 1 )
).

occupies(X-Y, X-Y).
occupies(ladder(1-_, X-Y), X1-Y) :- between(0, 2, DX), X1 is X + DX.
occupies(ladder(2-_, X-Y), X1-Y) :- between(0, 3, DX), X1 is X + DX.
occupies(ladder(3-_, X-Y), X1-Y1) :- X1 is X + 1, Y1 is Y + 1.
occupies(ladder(3-bottom, X-Y), X-Y1) :- Y1 is Y + 1.
occupies(ladder(3-top, X-Y), X1-Y) :- X1 is X + 1.

place(Tiles, Type, [Ladder|Tiles]) :-
direction(Type, Dir),
position(Pos),
\+ ( occupies(Ladder, P1),
member(T, Tiles),
occupies(T, P2),
P1 = P2
).

reaches(Ladders, Pos1, Pos2, _) :- connected(Ladders, Pos1, Pos2).
reaches(Ladders, Pos1, Pos2, Visited) :-
\+ member(P, Visited),
reaches(Ladders, P, Pos2, [P|Visited]).

solve(Dwarf, Golds, Ladders) :-
place([Dwarf|Golds], 1, T1),
place(T1, 2, T2),
place(T2, 3, Tiles),
findall(L, ( member(L, Tiles), L = ladder(_,_) ), Ladders),
forall(member(Gold, Golds), reaches(Ladders, Dwarf, Gold, [])).

unambiguous(Items, Solution) :-
between(2, 4, N),
length(Items, N),
maplist(position, Items),
sorted(Items),
Items = [Dwarf|Golds],