MeteorPuzzlePreliminaries
The Meteor Puzzle
This puzzle explores the many ways of tiling a 50-cell hexagonal plane with 10 different 5-cell pieces. A solution in Java can be found here.
An example solution, with each piece colored uniquely and the cells numbered sequentially, might look like this:
Data Structures
Since we often start with getting our data in order, how might we represent a board and a piece? Here is the solution format mandated by the "Computer Languages Benchmarks Game" (also known as the "Alioth shootout"):
As different algorithms may be used to generate the puzzle solutions, we require that the solutions be printed in a standard order and format. Here's one approach - working along each row left to right, and down the board from top to bottom, take the number of the piece placed in each cell on the board, and create a string from all 50 numbers, for example the smallest puzzle solution would be represented by 00001222012661126155865558633348893448934747977799
This would represent the solution show graphically above. Represented in character form, with a distinct digit representing each piece, the above string would correspond to this:
0 0 0 0 1 2 2 2 0 1 2 6 6 1 1 2 6 1 5 5 8 6 5 5 5 8 6 3 3 3 4 8 8 9 3 4 4 8 9 3 4 7 4 7 9 7 7 7 9 9
Variants of a Piece
One complication for each piece is that it has up to twelve possible variants depending on its orientation: there are six rotations of the original piece as shown on the sample board above and six more rotations of the piece's mirror image. Here's what these six rotations would look like for piece 0:
Starting with the piece in its original orientation:
Rotating clockwise by 1/6 of a turn:
Continuing by sixths, the 2/6 rotation:
The 3/6 rotation:
The 4/6 rotation:
The 5/6 rotation:
And here's what the mirror image would look like:
How to get the rotations of this mirror image should be obvious from the preceding.
One note to help with an eventual solution: notice how the last four rotations and the mirror image, as shown, leave groups of empty cells impossible to tile with the other 5-cell pieces. Therefore, these rotations placed as shown on the board, can be excluded as part of any feasible solution. Also, the original orientation and the first rotation constrain the possible companion pieces that will fit into the cells bordered by the piece and the edge of the board.
A Possible Piece Representation
Here's one idea I have for a data structure to represent each piece. This is very preliminary - a representation needs to be judged by how well it fits with the whole problem solution and I haven't gotten very far on this. So far, this represents the fruits of about 2 hours of work.
The basic idea is to number the edges of a hexagonal cell clockwise from 0 to 5 starting with the uppermost edge on the right side:
Each piece can be represented by a (number of cells/piece) by (number of sides/cell) boolean matrix with a one representing the side on which each cell attaches to its neighbors. So, piece 0 in its original orientation would be represented thusly:
NB. Piece 0 - original orientation 0 1 0 0 0 0 NB. Cell 0 attached on side 1 0 1 0 0 1 0 NB. Cell 1 attached on sides 1 and 4 0 1 0 0 1 0 NB. Cell 2 attached on sides 1 and 4 0 0 1 0 1 0 NB. Cell 3 attached on sides 2 and 4 0 0 0 0 0 1 NB. Cell 4 attached on side 5
This representation makes it simple to represent the rotations and the mirror images. The first two rotations would look like this:
NB. Piece 0 - 1/6 turn clockwise: _1|."(0 1) the above 0 0 1 0 0 0 NB. Cell 0 attached on side 2 0 0 1 0 0 1 NB. Cell 1 attached on sides 2 and 5 0 0 1 0 0 1 NB. Cell 2 attached on sides 2 and 5 0 0 0 1 0 1 NB. Cell 3 attached on sides 3 and 5 1 0 0 0 0 0 NB. Cell 4 attached on side 1 NB. Piece 0 - 2/6 turn clockwise: _1|."(0 1) the above 0 0 0 1 0 0 NB. Cell 0 attached on side 3 1 0 0 1 0 0 NB. Cell 1 attached on sides 0 and 3 1 0 0 1 0 0 NB. Cell 2 attached on sides 0 and 3 1 0 0 0 1 0 NB. Cell 3 attached on sides 0 and 4 0 1 0 0 0 0 NB. Cell 4 attached on side 1
And so on for the remaining rotations. The mirror image is accomplished simply enough as well:
NB. Piece 0 - mirror image: |."1 (Piece 0 - original orientation) 0 0 0 0 1 0 NB. Cell 0 attached on side 4 0 1 0 0 1 0 NB. Cell 1 attached on sides 1 and 4 0 1 0 0 1 0 NB. Cell 2 attached on sides 1 and 4 0 1 0 1 0 0 NB. Cell 3 attached on sides 1 and 3 1 0 0 0 0 0 NB. Cell 4 attached on side 0
Perhaps this representation should be transposed so the rotational shifts are done on the default axis.
Piece/Board Representation
Since I'm not sure how well the preceding representation would work with the eventual solution, here's another idea for representing a piece on the board. Here, each cell of a piece is represented on the board as a whole by ones, representing the cell itself and its neighbors, placed in a 50-element boolean vector representing the (ravel of the) board as a whole.
We could show piece 0 in its original orientation thusly (using "Pcell" to distinguish the "piece cell" as distinct from the board "cell"):
NB. Piece 0 - original orientation
50{.1 1 0 0 0 0 0 0 0 NB. Pcell 0 connected to self and cell 1
50{.1 1 1 0 0 0 0 0 0 NB. Pcell 1 connected to self, cell 0 and cell 2
50{.0 1 1 1 0 0 0 0 0 NB. Pcell 2 connected to self, cell 1 and cell 3
50{.0 0 1 1 0 0 0 0 1 NB. Pcell 3 connected to self, cell 2 and cell 8
50{.0 0 0 1 0 0 0 0 1 NB. Pcell 4 connected to self, and cell 3
The 1/6 rotation clockwise, shown here with numbered cells for reference to the scheme below,
would be represented under thusly:
NB. Piece 0 - 1/6 turn clockwise (1) 0 5}50$0 NB. Pcell 0 connected to self and cell 5 (1) 5 0 11}50$0 NB. Pcell 1 connected to self, cells 0 and 11 (1) 11 5 16}50$0 NB. Pcell 2 connected to self, cells 5 and 16 (1) 16 11 21}50$0 NB. Pcell 3 connected to self, cells 11 and 21 (1) 21 16}50$0 NB. Pcell 4 connected to self, cells 11 and 21
This scheme makes rotations more complex than the previous one but solves the problem of representing a piece's position and orientation within the board.