Kaleidoscope Solver

Monday, Nov 11, 2019

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.

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.

kaleidoscope_puzzle

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_pattern_steps

car_pattern_solution

The Number 12

12_pattern_breakdown

12_pattern_steps

No single squares

no_single_squares_pattern_breakdown

no_single_squares_pattern_steps

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 :)