Bug 153524

Summary: Fifteen Puzzle is 50% of the times unsolvable
Product: [Unmaintained] plasma4 Reporter: Dario Teixeira <darioteixeira>
Component: generalAssignee: Jesper Thomschütz <jesperht>
Status: RESOLVED FIXED    
Severity: normal CC: plasma-bugs-null
Priority: NOR    
Version First Reported In: unspecified   
Target Milestone: ---   
Platform: Compiled Sources   
OS: Linux   
Latest Commit: Version Fixed/Implemented In:
Sentry Crash Report:
Attachments: Test if a puzzle is solvable. In case it is not solvable reshuffle until it is.
fifteen.diff

Description Dario Teixeira 2007-12-05 22:29:20 UTC 
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).
Comment 1 Lubos Lunak 2007-12-06 13:18:26 UTC 
There's a simple algorithm to check if a puzzle is solvable. IIRC it's checking each title with each other and the number of times when they're in the wrong order (as compared to the solved 1-15 order) must be even. It should certainly possible to find it somewhere on the net.
Comment 2 Jonas P 2007-12-06 19:39:55 UTC 
Created attachment 22387 [details]
Test if a puzzle is solvable. In case it is not solvable reshuffle until it is.
Comment 3 Jesper Thomschütz 2007-12-11 08:45:27 UTC 
Applied your patch, change #747142. Thanks Jonas :)
Comment 4 Chani 2007-12-11 16:43:06 UTC 
here's a patch that doesn't have the extra loop; it should be faster (whereas 
the first patch could in theory run forever)


Created an attachment (id=22490)
fifteen.diff
Comment 5 Thomas Zander 2007-12-11 23:53:10 UTC 
chani;  qswap comes to mind ;)
Comment 6 Chani 2007-12-12 09:38:47 UTC 
SVN commit 747528 by chani:

improved puzzle generation (guaranteed to not run forever)
CCBUG: 153524


 M  +24 -16    fifteen.cpp  


WebSVN link: http://websvn.kde.org/?view=rev&revision=747528