Kaleidoscope Classic solver

How it works

A given Kaleidoscope puzzle can be represented as an exact cover problem. Define 82 constraints, one for each of the 18 pieces and one for each of the 64 board squares. Define a choice for every unique placement of a particular piece on the board, on a particular side, in a particular place and orientation, which satisfies the colours of the given puzzle. Let this choice satisfy the corresponding piece constraint and the square constraint of every square covered during the piece’s placement. Then the solutions to the puzzle are the exact covers of these constraints by these choices.

The solver constructs the puzzle’s corresponding exact cover problem and passes it to a generic implementation of Algorithm X, a procedure which enumerates all exact covers. This implementation uses the dancing links data structure for efficiency. See also Donald Knuth’s paper on the exact cover problem, Algorithm X and Dancing Links.

A human being considers two solutions identical if they are visually indistinguishable. To account for this, the solver ensures that visually indistinguishable placements of pieces with symmetries are represented as a single choice. There is also a unique ambiguity when both monomino pieces are on their black sides, in which case the solver simply filters out one of the two indistinguishable solutions. Solutions are also considered uniquely up to rotational symmetry. (But not up to mirror symmetry; you could do this but it would be quite complicated.)