August 1998 Programmer's Challenge

BlockBuster

Mail solutions to: progchallenge@mactech.com
Due Date: 11:59pm ET, Saturday, 1 August 1998

One of the Vice Presidents at the Real Job (we'll call him Don) has a collection of unusual puzzles at his conference table. The kind that require you to move a large block through a small hole, untangle a set of intertwined metal loops, do the impossible with rope, or otherwise do something that requires mastery of the fourth spatial dimension or a greater aptitude toward right-brain thinking than I possess. Don retired this week, and, in his honor, this month's Challenge is devoted to a spatial reasoning exercise. Not a puzzle that would have been worthy of his conference table, perhaps, but something in that same spirit.

Our puzzle is a variation of the Soma Cube, reportedly conceived by a writer from Denmark named Peter Hein as he was listening to a lecture on quantum physics. (That's one class I don't remember being able to daydream through!) The object of the Soma Cube is to form a 3x3 cube using seven shapes formed from three or four of the smaller cubes:

Of course, the Soma can be assembled into other shapes besides a cube, which forms the basis for our Challenge. Your job will be to write code that will assemble a larger number of potentially larger shapes into an even larger designated shape.

The prototype for the code you should write is:

#if defined(__cplusplus)
extern "C" {
#endif

#define kUnknown 0xFFFF

typedef struct Cubie {
SInt16 xCoord; /* x coordinate of cubie */
SInt16 yCoord; /* y coordinate of cubie */
SInt16 zCoord; /* z coordinate of cubie */
UInt16 value; /* ordinal value assigned to the Piece this cubie is part of */
} Cubie;

typedef struct Piece {
UInt32 numCubies; /* number of individual cubies in this piece */
Cubie *theCubies; /* array of cubies in this piece */
/* NOTE: the declaration of theCubies is modified slightly from the published version */
} Piece;

Boolean BlockBuster(

/* return TRUE if you were able to solve the puzzle */
long numPieces, /* number of pieces to assemble */
Piece thePieces[], /* the pieces to assemble */
Piece theGoal /* the structure you should assemble */
/* set theGoal.theCubies[i].value to thePieces[k].theCubies[j].value
if cubie j of piece k occupies cubie i in the reassembled puzzle */
);

#if defined(__cplusplus)
extern "C" {
#endif

The building block for our puzzle is the Piece, which is formed from numCubies individual cubes, provided to you in an array pointed to by theCubies. Each Piece has a unique nonzero identifier, which is associated with the value field in the Cubie structure. Cubies also have x, y, and z coordinates that define their relative orientation toward one another. There are no restrictions on the size or shape of a Piece, except that the constituent Cubies will all be connected (i.e., adjacent to another Cubie in the same Piece in x, y, or z.

Your BlockBuster routine is given an array (thePieces) of numPieces Pieces to work with. It is also provided with theGoal, an assembly of Cubies that you are to create from thePieces. For convenience, theGoal is also described using the Piece data structure. On input, the occupied coordinates are assigned a value of kUnknown. On output you should replace that value with the value of the Piece that occupies that coordinate. You may rotate and translate thePieces as you desire, but you may not break them by changing the relative orientation of the Cubies. You must use each Piece exactly once in assembling theGoal shape. All puzzles will be solvable, but if you feel you cannot solve a puzzle, BlockBuster should return FALSE.

As an example, the Pieces in the standard Soma Cube might be described as follows (with each 4-tuple representing the x, y, z, and value components of a cubie:

{0,0,1, 5}, {1,0,1, 5}, {0,1,1, 5}, {0,0,0, 5},
{0,0,0, 1}, {1,0,0, 1}, {0,1,0, 1},
{0,0,0, 3}, {1,0,0, 3}, {2,0,0, 3}, {0,1,0, 3},
{0,0,0, 7}, {1,1,1, 7}, {0,1,0, 7}, {0,1,1, 7},
{0,0,0, 6}, {1,0,0, 6}, {0,1,0, 6}, {0,1,1, 6},
{0,0,0, 4}, {1,0,0, 4}, {2,1,0, 4}, {1,1,0, 4},
{0,0,0, 2}, {1,0,0, 2}, {2,0,0, 2}, {1,1,0, 2},

The winner will be the solution that assembles a number of theGoal shapes in the minimum amount of time. There are no storage constraints for this Challenge, except that it must execute on my 192MB 8500/200.

This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, or Pascal

You can get a head start on the Challenge by reading the Programmer's Challenge mailing list. It will be posted to the list on or before the 12th of the preceding month. To join, send an email to listserv@listmail.xplain.com with the subject "subscribe challenge-a". You can also join the discussion list by sending a message with the subject "subscribe challenge-D".