Hex Combinator

I’ve created this tiny experiment to help with a 3D printing project I once had in mind. The idea was to create a simple fit-the-blocks puzzle, but on a hexagonal grid.

As tends to happen with this variety of puzzles, there are a number of challenges that are best solved using computers. How to figure out which pieces to make? How to prove that one can actually fit them on the board? How many different combinations exist?

This tiny experiment helped me with finding these answers.

Field

First, let’s define the field — a collection of hex cells where the players can place their pieces.

This field has cells. It has no rotational symmetry.

The higher the rotational symmetry, the faster we can find the combinations.

Pieces

Next, let’s define which pieces are available for placement.

That’s pieces containing {{ state.pieces.reduce((sum, p) => sum + p.size, 0) }} cells in total.

Depending on the game we may want to either allow or disallow “flipping” the pieces (i.e. mirroring them in one of the directions):

Taking the symmetry and flipping of each piece into account we can work out the unique variations of those pieces.

By precomputing the variations of each piece we reduce the task to trying out different variations on different positions on the field — until we find the combination that leaves no empty cells.

There’s a total of piece variations in our case.

Combinations

Let’s now iterate over all possible combinations and find the solutions where pieces fit the field exactly leaving no vacant cells.

On each step we’ll pick one piece variation and place it somewhere on the field. If there’s no place for it, we’ll backtrack and take a different piece variation.