From mouse@collatz.mcrcim.mcgill.edu Fri Jul 8 15:24:40 1994 Return-Path: Received: from Collatz.McRCIM.McGill.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA29240; Fri, 8 Jul 94 15:24:40 EDT Received: (root@localhost) by 8873 on Collatz.McRCIM.McGill.EDU (8.6.8.1 Mouse 1.0) id PAA08873; Fri, 8 Jul 1994 15:24:30 -0400 Date: Fri, 8 Jul 1994 15:24:30 -0400 From: der Mouse Message-Id: <199407081924.PAA08873@Collatz.McRCIM.McGill.EDU> To: Cube-Lovers@ai.mit.edu Subject: Re: SBP "Magic sQ" Cc: jkato@tmastb.eec.toshiba.co.jp > 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 adjacent tiles in a quadrilateral sliding-block puzzle of this sort (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