17
$\begingroup$

You are given a 9x9 grid with a set of 9 pegs (red circles) arranged in a 3x3 pattern in the corner, as shown below:

enter image description here

A peg can jump over another adjacent peg in any direction (horizontal, vertical or diagonal as shown in blue), provided that the destination cell is empty. A move consists of taking one peg and making one or more consecutive jumps, as shown below:

enter image description here

Can you transfer all the 9 pegs to the opposite corner of the grid, arranged in the same 3x3 pattern?

Bonus question: what is the smallest number of moves you can do it in?

Good luck!

$\endgroup$
8
  • $\begingroup$ @Bass that's a good point. I don't think it would be possible to show optimality without a computer. However, I was hoping that people can still do this by hand and get sub-optimal answers. Would that still be ok for a puzzle? Perhaps I need to reword the question somehow? $\endgroup$ Commented Oct 3, 2019 at 5:59
  • $\begingroup$ Ok I've modified the problem. The primary objective is to complete the puzzle in any number of moves. The bonus question asks for the minimal number of moves. $\endgroup$ Commented Oct 3, 2019 at 6:15
  • $\begingroup$ Can't I just diagonally shift all pegs in 9×6= 54 moves. $\endgroup$
    – Rishi
    Commented Oct 3, 2019 at 6:48
  • $\begingroup$ @Rishi sorry I don't understand your solution. They need to jump, not shift. $\endgroup$ Commented Oct 3, 2019 at 7:29
  • 2
    $\begingroup$ @Rishi Pegs must always jump over other pegs. $\endgroup$ Commented Oct 3, 2019 at 8:16

4 Answers 4

8
+100
$\begingroup$

21 moves for a 9x9 board

enter image description here

My code did a meet-in-the-middle search. 21 moves is optimal.

Other board sizes

14 moves for 7x7
enter image description here

Shifting the pegs 2 squares diagonally takes 9 moves.
Shifting the pegs 4 squares diagonally takes 14 moves.
Shifting the pegs 6 squares diagonally takes 21 moves.
Shifting the pegs 8 squares diagonally can be done in 27 moves by applying the 4 squares solution twice and combining the 14th & 15th move. There may be better solutions.

2x2 pegs

17 moves is optimal on a 13x13 board:
enter image description here

4x4 pegs

9 moves is optimal on a 5x5 board:
enter image description here

13 moves is optimal on a 6x6 board:
enter image description here

$\endgroup$
4
  • $\begingroup$ Finally someone has solved this puzzle after so many years! Love the animations too. It is interesting how some of them do a whole loop. Well deserved bounty. $\endgroup$ Commented May 7 at 11:31
  • $\begingroup$ I assume all of these are optimal except the last result? It would also be interesting to consider shifting a 4*4 group of pegs. $\endgroup$ Commented May 7 at 11:49
  • 2
    $\begingroup$ Thanks! Yes, 5x5->9, 7x7->14, 9x9->21 are optimal. Hmm, I'll try a 4x4 group tonight. It's interesting because it can be shifted an odd number of squares. $\endgroup$ Commented May 7 at 13:50
  • 1
    $\begingroup$ Love the new results for 2*2 and 4*4 groups! They are mesmerising to watch. I suspect there is a formula for 2*2 for any grid size. $\endgroup$ Commented May 9 at 11:00
50
$\begingroup$

I was having a slow work day, so I fired up Blender and made this:

GIF animation

In 13 hops, the block of 9 pegs can be moved two places down and to the right. By repeating the process two more times, the pegs can be moved to the bottom right corner.

$\endgroup$
9
  • 9
    $\begingroup$ ((((worship)))) $\endgroup$
    – Conifers
    Commented Oct 3, 2019 at 16:13
  • 4
    $\begingroup$ That is so beautiful! $\endgroup$ Commented Oct 3, 2019 at 22:01
  • 5
    $\begingroup$ Upvoted for producing a short film. ;) $\endgroup$
    – Wyck
    Commented Oct 4, 2019 at 2:53
  • 2
    $\begingroup$ Brilliant answer! Would you like a bounty award as a gift (after you earn the checkmark, I presume)? :) $\endgroup$
    – Mr Pie
    Commented Oct 5, 2019 at 0:09
  • 2
    $\begingroup$ @MrPie No, no. I don't need any encouragement to goof off from work! (Thanks, though 😁) $\endgroup$
    – r3mainer
    Commented Oct 6, 2019 at 19:32
12
$\begingroup$

It's possible.

Assume the pegs are in the upper left corner of a slightly enlarged chess board, which has indices $1 - 9$ and A - I. Now make the moves

b8-d6, c7-e5, d6-f4, e5-g3, f4-h2, g3-i1

b9-d7, c9-c7, c8-e6, c7-e7, d7-f5, e7-e5, e6-g4, e5-c5, f5-h3, g5-g3, g4-i2, g3-i3

a7-c7, a9-a7, a8-c6, c7-c5, a7-c7, b7-d5, c5-e5, c7-c5, c6-e4, e5-e3, c5-e5, d5-f3, e3-g3, e5-e3, e4-g2, g3-g1, e3-g3, f3-h1

EDIT

If I'm counting right, the wonderfully animated solution of @squeamish ossifrage has $12 \times 3 = 36$ moves, which is the same number of moves as my solution above. Inspired by the animated solution, I found that I can move the $9$ peg block two places down and to the right with just $9$ moves:

b8-d6, c7-e5, b9-d7, c9-c7-e7-c5, a7-c7-e7, a9-a7-c7, a8-c6-e6, c8-c6, b7-d5

This reduces the total number of moves to $9 \times 3 = 27$ moves. I don't know if this is the minimum, but it's a start.

EDIT 2

Made a computer program to look for a solution with fewer moves. It managed to improve my previous solution so it now only takes

$23$ moves

Here they are:

a8-c6, b9-d7, b7-d5, c7-e5, a9-c5, c9-e7, a7-c7, b8-f4, c8-g4, c6-e6, e5-e3, c5-e5, d5-h3, g4-i2, e5-i1, e7-i3, c7-g3, d7-f5, e6-g2, g3-g1, e3-g3, f5-h1, f4-h2

I had to make some assumptions to get a solution within a reasonable time, so I'm not absolutely sure this is the minimum. I'd love to see the minimum if this is not it!

$\endgroup$
2
  • $\begingroup$ 27 is very good. It is not the minimum, however it is a great start. Hopefully others can extend your solution. $\endgroup$ Commented Oct 5, 2019 at 13:01
  • $\begingroup$ Great work. I had to give the tick to the new improved solution. $\endgroup$ Commented May 7 at 11:32
2
$\begingroup$

If we allow moving a peg into a neighboring cell (without jumping) then the optimal solution requires

16 moves

The solution is

enter image description here It is a symmetrical solution so only the first 8 moves are shown. The remaining moves are simply a repeat of the first 8 moves in reverse order (palindromic). This elegant solution was found by H.Ajisawa and T.Maruyama, and it was proven to be optimal by George I. Bell in 2009: https://arxiv.org/pdf/0803.1245.pdf (page 13). NOTE that this solution doesn't answer the original puzzle as we have allowed a move into the neighboring cell in step 3. The optimal solution to the original puzzle remains an open question, but we know it cannot be done in less than 16 moves.

$\endgroup$
3
  • 2
    $\begingroup$ The solution above doesn't follow the rules you set out. In the third frame, a peg makes a move which is not a jump. In your rule description you said "A move consists of taking one peg and making one or more consecutive jumps, where you defined a jump in the previous sentence. You reinforced this in a comment "They need to jump, not shift". $\endgroup$
    – Jens
    Commented Nov 5, 2019 at 0:14
  • 1
    $\begingroup$ Oh you are right! I didn't even notice this. Hmmm. At this point it would be unfair to modify the rules of the original puzzle, instead I will modify my answer and leave it unaccepted. $\endgroup$ Commented Nov 5, 2019 at 0:17
  • 1
    $\begingroup$ Now I wonder if we can somehow avoid the third ("illegal") move and replace it with alllowed moves such that we can still solve the original puzzle efficiently? $\endgroup$ Commented Nov 5, 2019 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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