From mouse@collatz.mcrcim.mcgill.edu Thu May 4 17:08:31 1995 Return-Path: Received: from Collatz.McRCIM.McGill.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA25728; Thu, 4 May 95 17:08:31 EDT Received: (root@localhost) by 2560 on Collatz.McRCIM.McGill.EDU (8.6.10 Mouse 1.0) id RAA02560 for cube-lovers@ai.mit.edu; Thu, 4 May 1995 17:08:15 -0400 Date: Thu, 4 May 1995 17:08:15 -0400 From: der Mouse Message-Id: <199505042108.RAA02560@Collatz.McRCIM.McGill.EDU> To: cube-lovers@ai.mit.edu Subject: Re: SBP "Magic sQ" 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