Skip to content
Solver for the Kaleidoscope pattern packing puzzle in Python
Python HTML CSS
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.sass-cache/7a33cdb66e3f1a47cb573e9ae292925ca1b8a013
images
solver
.gitignore
README.md
requirements.txt

README.md

Kaleidoscope Solver

This is an attempt to make a basic solver for the Kaleidoscope Classic, a polynomino packing puzzle with an 8x8 board and 18 checkered pieces, that can be arranged in over billlions of ways, and any single pattern formed can have anywhere from millions to a single solution. Given a specific pattern, a solution is an arrangement of the pieces, flipped or otherwise, that form the pattern.

Screenshot 2019-11-26 at 1 54 32 PM

The algorithm makes use of finding islands, edge matching, piece size and crookedness heuristics and backtracking to find the best fitting pieces.

Solver runs for a few patterns:

The Car Reflection

car

Screenshot 2019-11-26 at 9 28 56 AM Screenshot 2019-11-26 at 9 26 32 AM

The Number 12

12_patt

Screenshot 2019-11-26 at 9 34 07 AM Screenshot 2019-11-26 at 9 33 58 AM

No single squares

no_single_squares_sol

Screenshot 2019-11-26 at 9 32 55 AM Screenshot 2019-11-26 at 9 32 47 AM no_single_squares

Algorithm:

Try a set of moves until the board has no remaing holes and no remaining pieces, or no moves.

Preprocess:

  1. Define teritory (Separate holes) by adjacent same color cell edges.
  2. [unquestionable] Check if any holes have single-piece solution, and place them
  3. see if the magic wand (octomino) fits any of the holes (practically done in the first step)

While pieces remaining:

  1. Make a size progression for each hole by cell count, wrt available pieces.
  2. Look for the densest windows across holes. Rank by edge/cell density.
  3. Fit pieces to each hole, rank each window-hole combination by a. edges matched b. crookedness hueristic of pieces c. span (only small_wand, or in rare cases magic wand)
  4. Select the winner piece, but keep a set of other next best moves
  5. If no moves: a. Try a different sized piece, according to a different progression b. If still no moves, backtrack to parent and try its sibling.

Performance is still a bit choppy for highly checkered patterns, which can be solved with more robust pruning in the backtracking tree.

Can be upgraded into a playable web-app :)

You can’t perform that action at this time.