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
Lint Skipped
Unit
Unit Tests Skipped
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.