15
$\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!

Improve this question
$\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$
    – Dmitry Kamenetsky
    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$
    – Dmitry Kamenetsky
    Oct 3, 2019 at 6:15
  • $\begingroup$ Can't I just diagonally shift all pegs in 9×6= 54 moves. $\endgroup$
    – Rishi
    Oct 3, 2019 at 6:48
  • $\begingroup$ @Rishi sorry I don't understand your solution. They need to jump, not shift. $\endgroup$
    – Dmitry Kamenetsky
    Oct 3, 2019 at 7:29
  • 2
    $\begingroup$ @Rishi Pegs must always jump over other pegs. $\endgroup$
    – Jaap Scherphuis
    Oct 3, 2019 at 8:16

3 Answers 3

Reset to default
41
$\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.

Improve this answer
$\endgroup$
9
  • 9
    $\begingroup$ ((((worship)))) $\endgroup$
    – Conifers
    Oct 3, 2019 at 16:13
  • 4
    $\begingroup$ That is so beautiful! $\endgroup$
    – Dmitry Kamenetsky
    Oct 3, 2019 at 22:01
  • 1
    $\begingroup$ If consecutive moves by the same piece count as a single move, you could probably optimize this some. (Looks great though.) $\endgroup$
    – Darrel Hoffman
    Oct 3, 2019 at 23:22
  • 5
    $\begingroup$ Upvoted for producing a short film. ;) $\endgroup$
    – Wyck
    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
    Oct 5, 2019 at 0:09
10
$\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!

Improve this answer
$\endgroup$
1
  • $\begingroup$ 27 is very good. It is not the minimum, however it is a great start. Hopefully others can extend your solution. $\endgroup$
    – Dmitry Kamenetsky
    Oct 5, 2019 at 13:01
1
$\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.

Improve this answer
$\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
    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$
    – Dmitry Kamenetsky
    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$
    – Dmitry Kamenetsky
    Nov 5, 2019 at 0:24

Your Answer

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

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