On Friday 10 Aug 2012 09:58:45 RICHARD WALKER wrote: > Do you know those little plastic squares with 24 alphabet tiles in a > 5x5 grid? The idea is to push the tiles around until you have them in > alphabetic order left to right, top to bottom, with an empty square in > the bottom right corner. > > Back in the mid-eighties I wrote a version of this game for my > Sinclair QL. I stored the tiles in a one-dimension array where they > were initially shuffled. > > I discovered, after much trial and error, that the chances of being > able to solve the puzzle after shuffling is almost exactly 1 in 2. The > problem is that 50% of shuffles results in an order where, by the > rules of tile movement, two adjacent tiles must be exchanged - and > that is not possible. > > Any ideas how to test the shuffled result to determine if such a > transposition exists without solving the game? >
One solution is not to randomise the array, but start from the solved position and do 50 random (but legal) moves. This will leave a position from which you can guarantee there is at least one solution (the reverse of the 50 random moves). Cheers Deri
