Code Logic

The puzzle in its solved position can be taken as 6 rigid pieces each composed of a 3D array of 5 mm cubes. The cubes of each piece are joined together to form a solid pice of wood. Taking a coordinate system at the center of the solved puzzle and whose unit is the edge of a cube, the pieces are located as follows: The convex hull of one piece is {|x|<6 & |y|<1 & 0<|z|<2}. The parallel mate to this piece reverses the sign of z. Three other piece pairs are had by the even permutations of the coordinates.

Instead of interpenetrating, the pieces proper have cube shaped notches carved in them. The program array p depicts the shape of this carving. There is one array entry for each piece. Each entry has 16 bits, one bit for each cube in the volume of intersection. Each bit in an entry is 1 just in case that cube is not carved out ot the piece.

There are 6 locations for each piece and 6 pieces. The solution requires allocating the pieces to the locations and then specifying which of the 8 possible orientations that piece takes at its allocated location.

The big cube region C = {|x|<2 & |y|<2 & |z|<2} contains all of the pairwise intersection of the hulls. Within C only the 8 small cubes in the corners belong to no piece. The volume of the intersection of C with the union of the hulls is thus 64−8 = 56. We bit map this region C with values whose type is cf. The constant array p has an entry for each piece. The 16 bits of p[i] are respectively 1 if that cubic portion of piece i is filled in and 0 if it is carved out. Four consecutive bits of a p element depict four cubes in the long direction of the piece. There are 56 one bits in the collective array p, one for each of the cubes of the big cube C. This means that there are no cavities in the solved position.

As we seek to solve the puzzle, each of the 6 pieces can go into each of the 6 positions, and then in each of 8 ways; 48 positions, altogether. The array pz is computed at the beginning and maps the solid portions of that piece within C. pz[i][j][k] depicts for piece i, in location j and orientation k, which parts of C are occupied by the non carved portion of that piece.

Order of search

Routine perm, borrowed from here, permutes the array L and thus allocates the pieces to the locations. L[j] indicates which location piece j is allocated to. We leave piece 0 fixed in location 0 and with orientation 0 and thus kill two birds with one stone: We thus avoid 47/48 of the searching. For each of the 5! allocations of the other pieces to locations we call routine x which recursively considers each possible orientation of each piece, with early short cutting when cubes overlap. The program as it stands finds two solutions having tentatively placed pieces 606 times.

About 1/2 of the program is debugging apparatus. Some slows the inner loop but I leave it in place for the search turns out to be fast. Early code planning emphasized efficiency because mature optimization is not always inexpensive and the search was potentially expensive. Such early design decisions made the code slightly obscure, but not large. The data formats are small and efficient and the program and data thus fit in cache which is a significant performance issue with todays computers. This page helped mitigate obscurity for me as I developed the program. This page was developed as I wrote and debugged the program.

An alternative solution plan is to allocate locations to pieces. There are many detailed difference but the large outline of the program is the same. Indeed as I wrote the code I would forget which plan I was using. This page was written to serve to remind me of a few of these choices. Obviously the code won't work with confusion of such details. Some propose keeping such prose in the source of the program. I find that style both hard to read and write. Also typographical details afforded by html are unavailable even as comments in most programming languages. Knuth’s “Literate programming” addresses these problems but I have not invested in acquiring and learning such a technology. This page is a by-product of the program—not an after thought. The program would not have succeeded without some sort of page like this.

Mental aids used in interpreting the output of the program.

The two found solutions are mirror images of each other. The displayed cf values are each four 16 bit images. If each image is reversed end-for-end, the other solution results.

Here is code to manifest the symmetries of the pieces; such symmetries will produce duplicate results. The output of the code is included as a comment at the end of the code. I have already accounted for the 8 element group of piece 0 which is the key piece. I do this by not permuting piece 0 in the search for solutions. Here I consider the 16 element group by incuding reflections.

The 2nd numeric column in the output is 1 when the symmetry is a reflection. The symmetries are all between a piece and itself and are all reflections. Only pieces 2 and 4 have any symmetry; each has a motion taking it to its mirror image. If both perform this motion, the alternate solution is found.