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.
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:
Try a set of moves until the board has no remaing holes and no remaining pieces, or no moves.
Preprocess:
- Define teritory (Separate holes) by adjacent same color cell edges.
- [unquestionable] Check if any holes have single-piece solution, and place them
- see if the magic wand (octomino) fits any of the holes (practically done in the first step)
While pieces remaining:
- Make a size progression for each hole by cell count, wrt available pieces.
- Look for the densest windows across holes. Rank by edge/cell density.
- 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)
- Select the winner piece, but keep a set of other next best moves
- 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 :)