[Mageia-discuss] Randomised game position (was: Mageia 2 Wireless LAN (Wifi) Connection Keeps Getting Disconnected)

[Deri James]

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