Date: Fri, 08 Jul 94 15:24:30 -0400
From: der Mouse <mouse@collatz.mcrcim.mcgill.edu >
Subject: Re: SBP "Magic sQ"
```                                   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
+---+---+---+---+
```

Not hard, but cutely deceptive. The figure as supplied is a magic
square with the 1 and 6 switched. It is not possible to switch two
(there's an easy induction proof that only even permutations are
possible). Thus, either it's not possible or the solution involves
some other magic square.

Since the 8 must clearly be in the lower right corner of the resulting
magic square, there are only two squares possible. One is the magic
square that is almost present already; the other is its reflection:

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

Fortunately, the "other" magic square is an even permutation from the
provided start position. 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. Move the 8 aside, then
move as follows (* represents the blank space):

```2 9 4    2 9 4    2 9 4    2 9 4    2 9 4    2 9 4    2 9 4    2 9 4
7 5 3 -> 7 5 3 -> 7 5 3 -> * 5 3 -> 5 * 3 -> 5 3 * -> 5 3 6 -> 5 3 6 ->
1 6 *    1 * 6    * 1 6    7 1 6    7 1 6    7 1 6    7 1 *    7 * 1
+-------+
2 9 4    2 * 4    2 4 *    2 4 6    2 4 6    2 4 6  | 2 4 6 |  2 4 6
5 * 6 -> 5 9 6 -> 5 9 6 -> 5 9 * -> 5 9 1 -> 5 9 1 -> 5 9 1 -> * 9 1 ->
7 3 1    7 3 1    7 3 1    7 3 1    7 3 *    7 * 3  | * 7 3 |  5 7 3
+-------+
2 4 6    2 * 6    * 2 6    9 2 6    9 2 6    9 2 6    9 2 6    9 2 6
9 * 1 -> 9 4 1 -> 9 4 1 -> * 4 1 -> 4 * 1 -> 4 7 1 -> 4 7 1 -> * 7 1 ->
5 7 3    5 7 3    5 7 3    5 7 3    5 7 3    5 * 3    * 5 3    4 5 3

* 2 6    2 * 6    2 7 6    2 7 6    2 7 6
9 7 1 -> 9 7 1 -> 9 * 1 -> 9 5 1 -> 9 5 1
4 5 3    4 5 3    4 5 3    4 * 3    4 3 *
```

Then put the 8 back, and you're done, in a total of 30 moves (28 shown,
plus the two moves of the 8). For those who care about such things,
the boxed position is the midpoint at which the two searches met.
(This is fairly obvious - since the number of moves is even, the
configuration on which the searches met must be the middle one.)

This solution exhibits curious near-symmetries in portions of the path
taken by the blank space. Anyone have any thoughts on this? Perhaps I
should modify the program so it reports _all_ solutions of this length;
there may be something interesting lurking here.

der Mouse

mouse@collatz.mcrcim.mcgill.edu