rcorless@uwovax.uwo.ca (09/29/90)
With regard to the solvability of the puzzle-24 game, I seem to remember from my number-theory days (about 12 years ago now... sigh) that the puzzle will be solvable precisely when you have written the numbers down as an - even - permutation of the sequence 1..24 (or n, if you like). This is because the smallest exchange you can make with the puzzle is a three-cycle. By "even permutation" I mean a permutation that can be written as a product of three-cycles, and by "three-cycle" I mean a permutation of the sort (1,2,3) -> (2,3,1). These are called even because every permutation can be written as a product of simple exchanges, and every three-cycle needs 2 exchanges. For example, the above permutation is the product of 1<=>2 and 2<=>3. It turns out that exactly half of all permutations are even, so your observation that half your games are solvable sounds spot-on. I seem to recall that the inventor of the 15-puzzle (he was famous for puzzles) made a big splash by offering a big prize for solving a particular puzzle - which, as he well knew, was in the impossible half. I don't remember if there is a simple test for evenness of a permutation. It ought to be easy to write an "even" permutatation generator, though. Just start with the ordered set and perform random three-cycles on it. This is equivalent to starting with your puzzle solved, I guess. -- ======== Robert Corless, Applied Mathematics, University of Western Ontario ======== London, Ontario, Canada N6A 5B9 e-mail : RCORLESS@uwovax.uwo.ca