Summary: | Fifteen Puzzle is 50% of the times unsolvable | ||
---|---|---|---|
Product: | [Plasma] plasma4 | Reporter: | Dario Teixeira <darioteixeira> |
Component: | general | Assignee: | Jesper Thomschütz <jesperht> |
Status: | RESOLVED FIXED | ||
Severity: | normal | CC: | plasma-bugs |
Priority: | NOR | ||
Version: | unspecified | ||
Target Milestone: | --- | ||
Platform: | Compiled Sources | ||
OS: | Linux | ||
Latest Commit: | Version Fixed In: | ||
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
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 |