7
$\begingroup$

You have 8x8 board and 9 identical pieces placed in a 3x3 square at the bottom left corner of the board. You are going to play a very simple game. Your task is to move these 9 pieces to the 3x3 square in the upper right corner of the board, with as few moves as possible. Two kinds of move are allowed:

  1. You can move a piece one space up, down, left, or right, if the space it is moving to is empty.
  2. You can "jump" a piece over another single piece next to it in one of those four directions, if the space on the other side is empty. You are allowed to make multiple jumps (as many as you like) with the same piece, as part of the same move.

For example here is a game of 30 moves:

sample 30-move game

I don't know the answer so I can't give you hints or ideas...

Anyways good luck! BTW for the animation I used http://www.apronus.com/chess/diagram/editor/

Improve this question
$\endgroup$
9
  • $\begingroup$ Can the stones jump a series of stones in a line? (e.g. at the end of the animation could the last two moves be made to one move e6 to h6?) $\endgroup$
    – Jonathan Allan
    Jun 25, 2016 at 1:45
  • 1
    $\begingroup$ As I understand you mean moving from e6 to h6 at one jump. It violates rule 2. You can't jump over two stones. I guess I should write better. $\endgroup$
    – newzad
    Jun 25, 2016 at 1:54
  • $\begingroup$ I can't figure out what your rules mean. You're animation seems to jumping adjacent stones which is not allowed because an adjacent stone is an occupied space, violating rule 2. It also seems to be making diagonal moves which aren't specified by the rules. What kind of move was b1 to d5? Also there was c1 to c5 which would be jumping over two stones which you said is not allowed. $\endgroup$
    – User4407
    Jun 25, 2016 at 2:27
  • $\begingroup$ b1 to d5 is b1-b3-b5-d5 which counts as one move; and c1 to c5 is c1-c3-c5 also counts as one move. $\endgroup$
    – newzad
    Jun 25, 2016 at 2:34
  • 1
    $\begingroup$ I think I see. Rule two doesn't forbid the two consecutive squares from being occupied; rather, the second square after an occupied square has to be unoccupied. Kind of like checkers. $\endgroup$
    – User4407
    Jun 25, 2016 at 2:40

1 Answer 1

Reset to default
13
$\begingroup$

Using a computer to attempt to beat my original solution I found some

$22$ move games

Here is one:

start
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·
1 2 3 · · · · ·
4 5 6 · · · · ·
7 8 9 · · · · ·

1
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·
· · 6 · · · · ·
1 2 3 · · · · ·
4 5 · · · · · ·
7 8 9 · · · · ·

2
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·
· · 3 · · · · ·
· · 6 · · · · ·
1 2 · · · · · ·
4 5 · · · · · ·
7 8 9 · · · · ·

3
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·
· · · 3 · · · ·
· · 6 · · · · ·
1 2 · · · · · ·
4 5 · · · · · ·
7 8 9 · · · · ·

4
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·
· · · 3 1 · · ·
· · 6 · · · · ·
· 2 · · · · · ·
4 5 · · · · · ·
7 8 9 · · · · ·

5
· · · · · · · ·
· · · · · · · ·
· · · · 1 · · ·
· · · 3 · · · ·
· · 6 · · · · ·
· 2 · · · · · ·
4 5 · · · · · ·
7 8 9 · · · · ·

6
· · · · · · · ·
· · · · 7 · · ·
· · · · 1 · · ·
· · · 3 · · · ·
· · 6 · · · · ·
· 2 · · · · · ·
4 5 · · · · · ·
· 8 9 · · · · ·

7
· · · · · · · ·
· · · · · 7 · ·
· · · · 1 · · ·
· · · 3 · · · ·
· · 6 · · · · ·
· 2 · · · · · ·
4 5 · · · · · ·
· 8 9 · · · · ·

8
· · · · · · · ·
· · · · · 7 9 ·
· · · · 1 · · ·
· · · 3 · · · ·
· · 6 · · · · ·
· 2 · · · · · ·
4 5 · · · · · ·
· 8 · · · · · ·

9
· · · · · 5 · ·
· · · · · 7 9 ·
· · · · 1 · · ·
· · · 3 · · · ·
· · 6 · · · · ·
· 2 · · · · · ·
4 · · · · · · ·
· 8 · · · · · ·

10
· · · · · 5 · ·
· · · · · 7 · 9
· · · · 1 · · ·
· · · 3 · · · ·
· · 6 · · · · ·
· 2 · · · · · ·
4 · · · · · · ·
· 8 · · · · · ·

11
· · · · · 5 · ·
· · · · · 7 · 9
· · · · 1 · · ·
· · · 3 · · · ·
· · 6 · · · · ·
4 2 · · · · · ·
· · · · · · · ·
· 8 · · · · · ·

12
· · · · · · 5 ·
· · · · · 7 · 9
· · · · 1 · · ·
· · · 3 · · · ·
· · 6 · · · · ·
4 2 · · · · · ·
· · · · · · · ·
· 8 · · · · · ·

13
· · · · · · 5 ·
· · · · · 7 4 9
· · · · 1 · · ·
· · · 3 · · · ·
· · 6 · · · · ·
· 2 · · · · · ·
· · · · · · · ·
· 8 · · · · · ·

14
· · · · · · 5 ·
· · · · · 7 4 9
· · · · 1 · · ·
· · · 3 · · · ·
· · 6 · · · · ·
· 2 · · · · · ·
· 8 · · · · · ·
· · · · · · · ·

15
· · · · · · 5 ·
· · · · · 7 4 9
· · · · 1 · · 8
· · · 3 · · · ·
· · 6 · · · · ·
· 2 · · · · · ·
· · · · · · · ·
· · · · · · · ·

16
· · · · · · 5 ·
· · · · · 7 4 9
· · · · 1 · · 8
· · · 3 · · · ·
· 2 6 · · · · ·
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·

17
· · · · · · 5 2
· · · · · 7 4 9
· · · · 1 · · 8
· · · 3 · · · ·
· · 6 · · · · ·
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·

18
· · · · · · 5 2
· · · · · 7 4 9
· · · · 1 · · 8
· · · 3 · · · ·
· · · 6 · · · ·
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·

19
· · · · · 6 5 2
· · · · · 7 4 9
· · · · 1 · · 8
· · · 3 · · · ·
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·

20
· · · · · 6 5 2
· · · · · 7 4 9
· · · 3 1 · · 8
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·

21
· · · · · 6 5 2
· · · · · 7 4 9
· · · · 1 3 · 8
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·

22
· · · · · 6 5 2
· · · · · 7 4 9
· · · · · 3 1 8
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·

I reduced the search space by not allowing stones to moves to (although they can jump via) the spots marked with an * below:

* * * * · · · · 
* * * · · · · · 
* * · · · · · ·
* · · · · * * * 
· · · · * * * * 
1 2 3 * * * * * 
4 5 6 * * * * *
7 8 9 * * * * *

I then

searched for states reachable within $13$ moves and then searched for the existence of an inversion* of a depth $13$ state in the states reachable in up to $10$ moves.

* rotate $180^\circ$ and reflect in the diagonal from bottom-left to top-right.

This yielded (not counting those that could be reflected into the blocked off space space):

\begin{align}155\space&23\text{ move games}\\7\space&22\text{ move games}\end{align}

Of course

There could be games that use the blocked off space with even less moves.

My original (human only) attempt:

$24$

start
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 
1 2 3 · · · · · 
4 5 6 · · · · · 
7 8 9 · · · · · 

1
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 
· · 3 · · · · · 
1 2 · · · · · · 
4 5 6 · · · · · 
7 8 9 · · · · · 

2
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 
· · 9 · · · · · 
· · 3 · · · · · 
1 2 · · · · · · 
4 5 6 · · · · · 
7 8 · · · · · · 

3
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 
· · · 9 · · · · 
· · 3 · · · · · 
1 2 · · · · · · 
4 5 6 · · · · · 
7 8 · · · · · · 

4
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 
· · · 9 1 · · · 
· · 3 · · · · · 
· 2 · · · · · · 
4 5 6 · · · · · 
7 8 · · · · · · 

5
· · · · · · · · 
· · · · · · · · 
· · · · 1 · · · 
· · · 9 · · · · 
· · 3 · · · · · 
· 2 · · · · · · 
4 5 6 · · · · · 
7 8 · · · · · · 

6
· · · · · · · · 
· · · · 7 · · · 
· · · · 1 · · · 
· · · 9 · · · · 
· · 3 · · · · · 
· 2 · · · · · · 
4 5 6 · · · · · 
· 8 · · · · · · 

7
· · · · · · · · 
· · · · · 7 · · 
· · · · 1 · · · 
· · · 9 · · · · 
· · 3 · · · · · 
· 2 · · · · · · 
4 5 6 · · · · · 
· 8 · · · · · · 

8
· · · · · 5 · · 
· · · · · 7 · · 
· · · · 1 · · · 
· · · 9 · · · · 
· · 3 · · · · · 
· 2 · · · · · · 
4 · 6 · · · · · 
· 8 · · · · · · 

9
· · · · · · 5 · 
· · · · · 7 · · 
· · · · 1 · · · 
· · · 9 · · · · 
· · 3 · · · · · 
· 2 · · · · · · 
4 · 6 · · · · · 
· 8 · · · · · · 

10
· · · · · · 5 · 
· · · · · 7 · · 
· · · · 1 · · · 
· · · 9 · · · · 
· · 3 · · · · · 
· 2 · · · · · · 
4 · 6 · · · · · 
· · 8 · · · · · 

11
· · · · · · 5 · 
· · · · · 7 8 · 
· · · · 1 · · · 
· · · 9 · · · · 
· · 3 · · · · · 
· 2 · · · · · · 
4 · 6 · · · · · 
· · · · · · · · 

12
· · · · · · 5 · 
· · · · · 7 · · 
· · · · 1 · 8 · 
· · · 9 · · · · 
· · 3 · · · · · 
· 2 · · · · · · 
4 · 6 · · · · · 
· · · · · · · · 

13
· · · · · · 5 · 
· · · · · 7 · · 
· · · · 1 · 8 · 
· · · 9 · · · · 
· · 3 · · · · · 
· 2 6 · · · · · 
4 · · · · · · · 
· · · · · · · · 

14
· · · · · · 5 · 
· · · · · 7 6 · 
· · · · 1 · 8 · 
· · · 9 · · · · 
· · 3 · · · · · 
· 2 · · · · · · 
4 · · · · · · · 
· · · · · · · · 

15
· · · · · · 5 · 
· · · · · 7 · 6 
· · · · 1 · 8 · 
· · · 9 · · · · 
· · 3 · · · · · 
· 2 · · · · · · 
4 · · · · · · · 
· · · · · · · · 

16
· · · · · · 5 · 
· · · · · 7 · 6 
· · · · 1 · 8 · 
· · · 9 · · · · 
· · 3 · · · · · 
· 2 · · · · · · 
· 4 · · · · · · 
· · · · · · · · 

17
· · · · · · 5 4 
· · · · · 7 · 6 
· · · · 1 · 8 · 
· · · 9 · · · · 
· · 3 · · · · · 
· 2 · · · · · · 
· · · · · · · · 
· · · · · · · · 

18
· · · · · · 5 4 
· · · · · 7 · 6 
· · · · 1 · 8 · 
· · · 9 · · · · 
· 2 3 · · · · · 
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 

19
· · · · · 2 5 4 
· · · · · 7 · 6 
· · · · 1 · 8 · 
· · · 9 · · · · 
· · 3 · · · · · 
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 

20
· · · · · 2 5 4 
· · · · · 7 · 6 
· · · · 1 · 8 · 
· · 3 9 · · · · 
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 

21
· · · · · 2 5 4 
· · · · · 7 3 6 
· · · · 1 · 8 · 
· · · 9 · · · · 
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 

22
· · · · · 2 5 4 
· · · · · 7 3 6 
· · · 9 1 · 8 · 
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 

23
· · · · · 2 5 4 
· · · · · 7 3 6 
· · · · 1 · 8 9 
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 

24
· · · · · 2 5 4 
· · · · · 7 3 6 
· · · · · 1 8 9 
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 
· · · · · · · ·

Improve this answer
$\endgroup$
5
  • $\begingroup$ Nice. I'm curious if exist games with smaller than 24 moves. $\endgroup$
    – newzad
    Jun 25, 2016 at 11:11
  • $\begingroup$ For reasons of symmetry (even number of pieces, even number of XY locations), and reversibility (any valid move can be run in reverse), if N<24, then N =2*k where k <=11. So you would be looking for 22, 20, 18... moves. $\endgroup$
    – Penguino
    Jun 27, 2016 at 0:27
  • $\begingroup$ @Penguino I think I agree it'll probably be even, but there are 9 stones, so maybe not? $\endgroup$
    – Jonathan Allan
    Jun 27, 2016 at 3:18
  • $\begingroup$ Yes - my mistake. I meant "Assuming 9 is an even number...", which is patently false... $\endgroup$
    – Penguino
    Jun 27, 2016 at 3:52
  • $\begingroup$ @nikamed, I have improved upon my solution using computer search $\endgroup$
    – Jonathan Allan
    Jun 28, 2016 at 2:37

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.