Jun 99 Challenge
Volume Number: 15
Issue Number: 6
Column Tag: Programmer's Challenge
by Bob Boonstra, Westford, MA
Tetraminx
The last Challenge I entered as a contestant was the Rubik's Cube Challenge, where
entries had to solve a scrambled Rubik's cube. While that Challenge was difficult
enough to cause me to retire from competition after winning, I've stayed interested in
puzzles. Some time ago I ran across Meffert's World Of Puzzles, an online puzzle
vendor at http://www.mefferts-puzzles.com/mefferts-puzzles/catalog.html, and
ordered a few of their puzzles. The Tetraminx is perhaps the least difficult puzzle,
much simpler than the Cube, but still interesting enough that I thought it might make a
good Challenge without driving any contestants into retirement.
The Tetraminx is formed by four hexagonal faces, each consisting of six triangles,
joined in the shape of a tetrahedron, plus four triangles to complete the solid, as
depicted at http://www.mefferts-puzzles.com/pictures/tetramix.jpg.
Scrambled Tetraminx
Your Challenge is to come up with a sequence of moves that will return the puzzle to
the goal state, where each of the hexagonal faces consist of triangular facelets of a
single color.
The prototype for the code you should write is:
#if defined (__cplusplus)
extern "C" {
#endif
typedef enum {
kYellow=1,kBlue,kRed,kGreen
} PieceColor;
typedef enum {
kLeftClockwise=1,kRightClockwise,
kBottomClockwise,kBackClockwise,
kLeftCounterClockwise,kRightCounterClockwise,
kBottomCounterClockwise,kBackCounterClockwise
} Move;
typedef enum {
/* single triangular faces named after the opposite hexagonal face
*/
kLeft,kRight,kBottom,kBack,
/* edge faces named kXY, where X is the hexagonal face they are
part of,
and Y is the adjacent hexagonal face */
kBR,kRK,kKB,
kLB,kBK,kKL,
kKR,kRL,kLK,
kLR,kRB,kBL,
/* corner faces named cXY, where X is the hexagonal face they are
part of,
and Y is the hexagonal face opposite the adjacent single
triangle */
cRL,cKL,cBL,
cLR,cBR,cKR,
cRB,cLB,cKB,
cLK,cRK,cBK
} PieceType;
typedef struct {
PieceType piece;
PieceColor color;
} PieceState;
long /* numberOfMoves */ Tetraminx (
PieceState state[28], /* initial state of the 28 pieces */
Move moves[], /* moves you generate */
long maxMoves /* maximum storage in move array */
);
#if defined (__cplusplus)
}
#endif
The puzzle is manipulated with four pairs of 120-degree rotation moves that we will
call kLeftXXX, kRightXXX, kBottomXXX, and kBackXXX, corresponding to the four