[Panel-devel] [Bug 153524] New: Fifteen Puzzle is 50% of the times unsolvable

[Dario Teixeira]

------- You are receiving this mail because: -------
You are the assignee for the bug, or are watching the assignee.
         
http://bugs.kde.org/show_bug.cgi?id=153524         
           Summary: Fifteen Puzzle is 50% of the times unsolvable
           Product: plasma
           Version: unspecified
          Platform: Compiled Sources
        OS/Version: Linux
            Status: UNCONFIRMED
          Severity: normal
          Priority: NOR
         Component: general
        AssignedTo: panel-devel kde org
        ReportedBy: darioteixeira yahoo com


Version:            (using KDE KDE 3.96.0)
Installed from:    Compiled From Sources
OS:                Linux

It seems that method Fifteen::shuffle() uses a naive algorithm to shuffle the tiles. It essentially inserts tiles at random, only making sure the same tile is not used twice.  The problem is that the Fifteen Puzzle has this interesting property that only half of random starting positions are solvable...

(The easiest way of guaranteeing that a Puzzle is indeed solvable is perhaps by simply starting from the solved solution and iteratively moving one piece at a time at random.  Essentially you just backtrack your way from a solved solution to a shuffled one).