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/

$\endgroup$
  • $\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 '16 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 '16 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 '16 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 '16 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 '16 at 2:40
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 
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 
· · · · · · · · 

$\endgroup$
  • $\begingroup$ Nice. I'm curious if exist games with smaller than 24 moves. $\endgroup$ – newzad Jun 25 '16 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 '16 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 '16 at 3:18
  • $\begingroup$ Yes - my mistake. I meant "Assuming 9 is an even number...", which is patently false... $\endgroup$ – Penguino Jun 27 '16 at 3:52
  • $\begingroup$ @nikamed, I have improved upon my solution using computer search $\endgroup$ – Jonathan Allan Jun 28 '16 at 2:37

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.