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).
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.
Created attachment 22387 [details] Test if a puzzle is solvable. In case it is not solvable reshuffle until it is.
Applied your patch, change #747142. Thanks Jonas :)
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
chani; qswap comes to mind ;)
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