Fix fifteen puzzle solveability
ClosedPublic

Authored by poboiko on May 18 2017, 8:47 PM.

Details

Summary

Thus fixes bug 358940: fifteen puzzle often appears unsolveable.
There were two issues.

  1. Floating point division when determining the row with blank tile (blankRow = 2.75 seems weird).
  2. Even after fixing the first issue, applet didn't want to confirm that I've solved the puzzle. Seems like corresponding check was wrong: indeed, if one has solved 4x4 board (size=16, so pieces[i] = {1,2,...,15,0}), comparison with i=15 corresponds to 15>0, which is always true.

Clearly, to check if 15 numbers are ordered, one needs 14 (size-2) comparison operations.

Test Plan

Played puzzle ~10 times with sizes 2x2, 3x3 and 4x4.
Not a single one appeared unsolveable, and after solving it applet confirmed I've done it correctly.

Diff Detail

Repository
R114 Plasma Addons
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
poboiko created this revision.May 18 2017, 8:47 PM
Restricted Application added a subscriber: plasma-devel. · View Herald TranscriptMay 18 2017, 8:47 PM
mart accepted this revision.May 22 2017, 8:52 AM
This revision is now accepted and ready to land.May 22 2017, 8:52 AM
This revision was automatically updated to reflect the committed changes.