MeteorPuzzlePreliminaries

From J Wiki
Jump to navigation Jump to search

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: AMeteorPuzzleSoln250Numbered.jpg

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: Piece0 0OriginalOrientation.jpg

Rotating clockwise by 1/6 of a turn: Piece0 1SixthTurn.jpg

Continuing by sixths, the 2/6 rotation: Piece0 2SixthsTurn.jpg

The 3/6 rotation: Piece0 3SixthsTurn.jpg

The 4/6 rotation: Piece0 4SixthsTurn.jpg

The 5/6 rotation: Piece0 5SixthsTurn.jpg

And here's what the mirror image would look like: Piece0 6MirrorImage.jpg

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:

HexagonSidesNumberedsm.png

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, Piece0 1SixthTurnNumbered.jpg

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.