Back on

Date: Fri, 8 Jul 1994 15:24:30 -0400

I quoted and wrote:

                                   Sliding Block Puzzle "Magic sQ"
Fig.1 is incomplete.                      +---+---+---+
Can you complete a magic square           | 2 | 9 | 4 |
with minimum sliding steps?               +---+---+---+
                                          | 7 | 5 | 3 |
You, very easy or not?                    +---+---+---+---+
                                          | 1 | 6 | 8 |   |  Fig.1
                                          +---+---+---+---+

[...]. It's then just a straightforward tree search to find a
solution. A simple brute-force "meet in the middle" breadth-first
search finds a solution easily.

If we mark the squares as

0 1 2
3 4 5
6 7 8 9

then I gave a solution which makes the blank space follow the path 8 7
6 3 4 5 8 7 4 1 2 5 8 7 6 3 4 1 0 3 4 7 6 3 0 1 4 7 8 9.  I remarked:

This solution exhibits curious near-symmetries in portions of the
path taken by the blank space. [...] Perhaps I should modify the
program so it reports _all_ solutions of this length;

I finally got around to generating all minimal-length solutions. It
turns out, curiously enough, that each solution is uniquely determined
by the pattern of its middle position. There are ten solutions, listed
here in terms of the path taken by the blank space, with the middle
position written out:

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

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

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

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

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

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

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

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

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

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

Of course, whether this actually matters to anyone is another story :-)

der Mouse

mouse@collatz.mcrcim.mcgill.edu