Bug 153524 - Fifteen Puzzle is 50% of the times unsolvable
Summary: Fifteen Puzzle is 50% of the times unsolvable
Alias: None
Product: plasma4
Classification: Plasma
Component: general (show other bugs)
Version: unspecified
Platform: Compiled Sources Linux
: NOR normal
Target Milestone: ---
Assignee: Jesper Thomschütz
Depends on:
Reported: 2007-12-05 22:29 UTC by Dario Teixeira
Modified: 2007-12-12 09:38 UTC (History)
1 user (show)

See Also:
Latest Commit:
Version Fixed In:

Test if a puzzle is solvable. In case it is not solvable reshuffle until it is. (2.62 KB, patch)
2007-12-06 19:39 UTC, Jonas P
fifteen.diff (1.56 KB, text/x-diff)
2007-12-11 16:43 UTC, Chani

Note You need to log in before you can comment on or make changes to this bug.
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)
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