9
$\begingroup$

Four Shinto Priests have traveled from their various prefectures in pilgrimage to the top of Mount Fuji. You must find pathways for them to move up and down the mountain until they can all achieve the peak. Often, this will require you to guide them into positions from which they can assist each other.

History

James Droscha is best known as the designer of the piecepack game system, and one of his early piecepack games was a solitaire called Fujisan. He and Mark Goadrich then adapted it for dominoes and pawns in a paper on using entangled components in solitaire games.

I was excited to learn about the domino version, because I had written software to find harder than average layouts of the piecepack version, and I was collecting Domino games.

The Problem

This week, I'll be posting three new problems here on Puzzling.SE, getting more challenging each time. Don't worry if you don't have dominoes, you can print out the diagram. Here's the layout for today's problem, see the rules below.

Fujisan set up

Setup

Set up the dominoes to match the starting position above.

For a random starting position, remove all dominoes with the number six and all doubles from a standard set of double-six dominoes. Shuffle the remaining 15 dominoes face down, then place twelve face-up dominoes side by side. Leave the three remaining dominoes face down, and use them to lift up the two middle dominoes as the peak of Mount Fuji.

Place a Priest (pawn) beside each number at both ends of the mountain.

Moving a Priest

  1. A Priest may move onto a space if the number matches the number of unoccupied spaces the Priest must move in a straight line to get there (including the destination space itself, but not including the Priest's starting space). For example, a Priest may move onto a space with the number 4 if there are 3 unoccupied spaces between it and the Priest.
  2. Occupied spaces (containing intervening Priests) are not counted when determining if a Priest may move onto a particular space. For example, a Priest may move onto a space with the number 2 if there are 3 occupied spaces and one unoccupied space between it and the Priest.
  3. A Priest may move freely between the two spaces on a domino. This is the only manner in which a Priest may move onto a blank space.
  4. Once a Priest lands on the peak of the mountain, he will refuse to leave it, but he can move back and forth (in the same domino) or to and fro (between the two dominoes). Clarification: A Priest may pass over the peak dominoes as part of a move.
  5. A Priest must enter the mountain from his own starting row; that is, he cannot move back and forth while he remains on the ground.

Goal

The Priests will be content when they all reach the top of the mountain.

Post your solution as an answer with each move labeled for pawn A, B, C, or D, the direction, and the number of steps. If someone else has posted an answer, see if you can find one with fewer moves.

$\endgroup$
4
  • $\begingroup$ To clarify, so in the first move, only C can move to either the domino with value 2 or 3, right? $\endgroup$
    – justhalf
    Aug 10 at 3:27
  • $\begingroup$ That's correct, @justhalf. $\endgroup$
    – Don Kirkby
    Aug 10 at 6:06
  • $\begingroup$ For the random starting position, is it always solvable? Probably not, right? $\endgroup$
    – justhalf
    Aug 10 at 17:55
  • 1
    $\begingroup$ In 1000 randomly generated problems, @justhalf, 92% were solvable. Of those, the median solution length was 14, with half of them between 12 and 16. When I went looking for more challenging problems, I wanted them to be outside that range but still solvable. $\endgroup$
    – Don Kirkby
    Aug 10 at 19:17

3 Answers 3

6
$\begingroup$

I wrote a program which brute forces this. It found a solution with a length of

23 moves.

The sequence is:

Move Priest C to the top of domino 11
Move Priest C to the top of domino 8
Move Priest C to the top of domino 3
Move Priest C to the top of domino 2
Move Priest C to the bottom of domino 2
Move Priest C to the bottom of domino 4
Move Priest C to the bottom of domino 5
Move Priest C to the bottom of domino 1
Move Priest C to the top of domino 1
Move Priest A to the top of domino 2
Move Priest A to the bottom of domino 2
Move Priest C to the bottom of domino 1
Move Priest B to the bottom of domino 4
Move Priest B to the bottom of domino 5
Move Priest A to the bottom of domino 4
Move Priest C to the bottom of domino 6
Move Priest A to the bottom of domino 10
Move Priest B to the bottom of domino 11
Move Priest C to the top of domino 6
Move Priest D to the bottom of domino 7
Move Priest A to the bottom of domino 6
Move Priest D to the top of domino 7
Move Priest B to the bottom of domino 7

The code is here: https://github.com/timojch/FujisanPuzzleSolver

If the program is correctly written, then this solution is optimal. It searches paths in order of increasing length, so the first solution it finds would necessarily be an optimal solution.

However, I think this search is likely incomplete. I did manually check this solution to make sure it's valid (assuming I didn't mess that up), but if I keep running it after finding solutions, it stops after 29 moves thinking that there are no more distinct reachable board states. It never discovers the solutions posted by other users - so it seems plausible that it is missing other solutions as well. This might not be the shortest solution. The other possible explanation for not finding the other posters' solutions is that every board state that can be reached in 30+ moves can also be reached in 29 or fewer moves, but I haven't been able to confirm this.

$\endgroup$
1
  • $\begingroup$ Ah, clever, C can directly go into the peak, reducing the number of moves of the other two priests to move to the right side. $\endgroup$
    – justhalf
    Aug 10 at 6:39
5
$\begingroup$

I will use a coordinate system to refer to the spaces. The 0 to the direct right of the A's starting position is henceforth R1C1, the 4 next to the B's is R2C1, while left of the C and D are R1C12 and R2C12 respectively. This means the goal spaces are R1-2C6-7.

When planning how to attack this puzzle, the first thing is to notice is

how few options there are to move Priests into the board proper.

Looking at each Priest in turn:

  • A: the minimum number of other Priests required is 1, to reach R1C2's 1
  • B: the minimum number of other Priests required is 2, to reach R2C4's 2
  • C: this is the only one which can be moved out immediately, to either R1C10's 3 or R1C11's 2
  • D: the minimum number of other Priests required is 2, to reach R2C7's 4

Therefore, the optimal path to begin is clear:

Use C to get A out, combine them to help B (since that is closest), then coordinate two to move D from its starting spot.

Step 1:

First C must get to R1C1.

The first tricky bit is getting over the goal without being stuck there. Without any help, the only option is the 5 on R1C3, which requires going from the 3 on R1C8, which itself can be reached in a single jump from one of the possible break-out spaces C has.

The next difficulty is getting to R1C1 itself, which (being a 0) can only be reached via R2C1's 4, which can only be reached by R2C5. There is a nice sequence of little-numbers to jump to R2C5.

Thus this path: C to R1C11 (jump to the 2), R1C8 (jump to the 3), R1C3 (jump to the 5), R1C2 (jump to the 1), R2C2 (move along a domino), R2C4 (jump to the 2), R2C5 (jump to the 1), R2C1 (jump to the 4), R1C1 (move along a domino). Moves: 9

Step 1

Step 2:

Now the A can be released. Once it is, both it and the C obligingly move downwards to help B out, per the plan.

Thus this path: A to R1C2 (jump to the 1), R2C2 (move along a domino), C to R2C1 (move along a domino). Moves: 9 + 3 = 12

Step 2

Step 3:

The B gratefully leaves its starting position, then moves aside to untrap the other two Priests (both of which can only easily move using R2C4's 2).

Thus this path: B to R2C4 (jump to the 2), R1C4 (move along a domino). Moves: 12 + 2 = 14

Step 3

Step 4:

Now consider how two Priests will get back across to help D out. Using at most one Priest as a helper (since only one can stay behind), the only option turns out to be using the 3 in R1C8, which itself requires using R1C5, which can be reached by using that obliging sequence of little-numbers from before. Two Priests must go by this path so that their position can allow D to escape.

Thus this path: C to R2C4 (jump to the 2), R2C5 (jump to the 1), R1C5 (move along a domino), R1C8 (jump to the 3), R2C8 (move along a domino), R2C9 (jump to the 1), then A follows the same path excepting the move onto R2C9. Moves: 14 + 6 + 5 = 25

Step 4

Step 5:

Now two Priests can get to the goal, D directly from its starting position!

Thus this path: B to R1C6 (jump to the 2), then D to R2C7. Moves: 25 + 2 = 27

Step 5

Step 6:

The trick now is getting the last two Priests safely to the goal. No claims of optimality here, but by shuffling the Priests already at the goal it can be accomplished in two jumps by A.

Thus this path: A to R2C2 (jump to the 5), then D to R1C7 (move along a domino), then B to R2C6 (move along a domino), then A to R2C7 (jump to the 4). Moves: 27 + 4 = 31

Step 6

Step 7:

Finally, the last open goal spot suggests a clear path to it, as a 2-length jump is in easy reach of C.

Thus this path: C to R1C9 (move along a domino), R1C6 (jump to the 2). Moves: 31 + 2 = 33

Step 7

$\endgroup$
3
  • $\begingroup$ Nice solution! I didn't notice D can directly enter the peak with just 2 priests. Your solution is 6 moves shorter than mine :D $\endgroup$
    – justhalf
    Aug 10 at 4:10
  • $\begingroup$ I incorporated the obvious optimization to get A and C out after releasing B into my answer, while keeping my original idea. (yours still better overall) $\endgroup$
    – justhalf
    Aug 10 at 4:18
  • $\begingroup$ You can save 2 moves in step 4 by moving A directly from R2C5 to R2C10 probably? Will alter the ending sequence tho $\endgroup$
    – justhalf
    Aug 10 at 5:26
4
$\begingroup$

First off, the notation. For each move, the first letter would be the priest label, then < or > for left or right, then a number denoting the number of steps. If a priest move (up or down) on the same tile, I'll just specify the priest label by itself.

39 36 Moves (update thanks to bobble, I switched A and C to save 3 moves):

1. C<2
2. C<3
3. C<5
4. C<1
5. C
6. C>2
7. C>1
8. C<4
9. C
10. A>1
11. A
12. C
13. B>2
14. B>1
15. B
16. C>2
17. C
18. C>3
19. C
20. A>2
21. A>1
22. A>4
23. A
24. C
25. C>2
26. B>5
27. A
28. B
29. C
30. D<1
31. A<3
32. A
33. D<3
34. C<4
35. B
36. B<5

The idea is:

to first notice that only C can move, and C has two options: C<2 or C<3.
To enable A, we need one priest on the first blank tile next to A, so that's our first goal (move 1-9).
To enable B, we need two priests on B's row, so B can do B>2. This can simply be done by A and C (move 10-12)
To enable D, we need three priests on D's row, so D can do D<1. This means all three priests must not land on the peak, but must cross first to the right side and enable D (move 13-29), before moving on to the peak.
Afterwards, it's straightforward to move them into the peak (move 30-36)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.