home
puzzles
genres
studio
help
about
links
forum


Pathfinder

A robot is situated in an environment with heaps of stones. Everytime he gets somewhere he picks up one stone from that heap. To decide where he will go next, he looks around and determines the sizes of the heaps in the squares neighbouring directly horizontally or vertically. His programming tells him which heapsizes he prefers. He will never move to an empty square. In case multiple neighbouring squares have the highest priority, he can not choose and gets stuck. Program the robot such that he will at some point arrive at the grey endstation. Give the priorities of the heaps of different sizes from left to right from highest to lowest priority. We will solve a small puzzle as an example.

Example

In this puzzle the answer is a permutation of the numbers 1, 2 and 3 (in a less formal way you could say: the numbers 1, 2 and 3 in some order). There are only 6 of those permutations and it would be possible to check each of them, but there it can be done much smarter.

Right at the start the robot needs to choose between 3 and 1 stones. Suppose the 3 comes before the 1 in his programming, then he goes to the right and turns it into a 2. Now he has to choose between 3 and 1 again, so he will again move towards the 3, reduces the size of the pile by 1 (we can simulate that by clicking the right mousebutton while pointing to a stone) and looks around. He sees two piles with 2 stones (to the north and to the east) and two piles of 1 stone (to the south and to the west). Whatever his preferences are, in a situation like this he will not be able to choose and will get stuck. Our assumption that 3 comes before 1 must have been wrong, 1 comes before 3.

Let's start all over again with this new knowledge in mind. This time the first step will be towards the south, next we will have to choose between 2 and 3 stones. Suppose that 2 comes before 3. The robot will move south again, has to go to the east because to the north there are is no stone left since we went there. The choice between the pile of 1 stone to the west and the two piles of 3 stones in the other directions is already determined. We walk back to the lower left of the grid and are stuck there. We conclude the 3 comes before the 2 and that means just one solution candidate remains: 1 3 2.

Starting in the upper left the robot will move to the south, to the east, again towards the south, again towards the east and he has reached his destination.

Background

This puzzle type was invented by Johan de Ruiter and appeared for the first time at the world puzzle championships in 2003.


Puzzles in this genre.
Info