CUTWIST

Cutwist

A twisty puzzle is a solid cut by flat planes. Every 3D puzzle here is made by one routine that splits a shape with a plane, and every puzzle's state is a list of whole numbers.

Each flat face of a solid lies on a plane, and the solid is everything on the inner side of all its face planes. So any of them can be made the same way: start with a shape the solid fits inside, like a sphere, and slice off whatever is outside each face's plane, one plane at a time.

A sphere is the natural picture, but the program can only slice shapes with flat faces, so a sphere has to be faked with hundreds of small ones, and every slice has to clip all of them. Any starting shape works as long as the solid fits inside it, so the code starts from a box, which has six faces. (The real box is far bigger than the solid; it's drawn smaller here so the slices show.)

Slicing a shape with no dents by a plane leaves a shape with no dents, so the whole program needs one geometric routine: split a shape by a plane.

The pieces come from the same routine. Take the finished solid and split it by each cut plane in turn: wherever a plane passes through a piece, that piece becomes two. The new faces a cut exposes are marked as plastic instead of sticker, so they're drawn black. A 3×3×3 cube is six cuts, two across each of its three directions. Choosing other directions (corners instead of faces, say) and other depths gives every other puzzle.

Every cut is made in all the directions of its kind at once, like every face or every corner. So the pattern of cuts has the same symmetry as the solid: turn the solid any way that lands it back in its own outline, and the cuts land on cuts.

Parallel cuts split the puzzle into layers, and a turn rotates one layer about the line through the center perpendicular to those cuts. For the layer to fit back into the shape, the turn has to land every piece exactly on a spot where a piece was. That works when the rotation carries the whole solid onto itself: a quarter turn about a cube's face, a third of a turn about its corner (the skewb), a quarter turn about an octahedron's corner, a fifth of a turn about a dodecahedron's face (the megaminx). The cuts share the solid's symmetry, so those rotations carry the cuts onto cuts too, and the turned layer fits.

A cube can be picked up and set back down in its own outline in 24 ways: any of its 6 faces on top, turned any of 4 ways. A dodecahedron can in 60. When the engine builds a puzzle, it finds all of these rotations and numbers them, with 0 meaning "not rotated". To find them, it tries every way of sending one face and a neighboring face onto another such pair, and keeps the rotations that carry every face onto a face. Here are all 24 for a cube, numbered by which face ends up on top: 0 to 3 keep white on top, 4 to 7 put yellow there, and so on, and each step down a column is one more quarter turn about the vertical.

The engine gives every piece one of these numbers. It keeps each piece's home shape, from the solved puzzle, plus the number of the rotation that carries it from home to where it is now. Each rotation spins the whole puzzle about its center, so a piece carried by one ends up somewhere else as well as facing a new way: the one number says both which spot the piece is in and which way it faces. A piece at 0 is in its home spot, facing its home way. The whole puzzle is a list of these numbers, one per piece, starting as all zeros.

Turns keep the pieces on the list, because every turn is itself one of the rotations. Here's a solved 2×2×2 with one piece lit, next to an uncut cube with the same corner lit. Each of the three layers the piece is in takes a quarter turn each way, going back to the start after each. Each turn moves the lit piece exactly the way it moves the whole uncut cube, lit corner and all, so the piece's number becomes that rotation's number. On the right is the piece by itself, turned the same way, with the rest of the cube as a wireframe.

That right-hand picture is the whole idea. Think of every piece as its own complete copy of the puzzle's shape, with all of it hidden except the piece's own chunk, like a mask. To turn a layer, find the pieces whose visible chunk is in that layer, and rotate their whole copies by the turn. When a whole copy rotates, its visible chunk goes along, the way a sticker on a ball goes along when you spin the ball: it ends up in a new spot, facing a new way. So the rotation takes care of both where the piece is and which way it faces, and the mask never changes.

So the engine barely needs to know about pieces at all. It needs to know how to rotate the whole shape (the 24 rotations, and what doing one after another gives) and which chunk each piece shows. Everything else follows. Precisely, a turn works like this:

1. Find the pieces in the layer. For each piece, rotate the center of its home shape by the piece's current rotation, and see which side of the cut it lands on.
2. Look up each new number. Call the turn's rotation r, and say a piece in the layer currently holds number g. Doing rotation g and then rotation r always gives another rotation on the list, so the engine builds a table of all these combinations up front. The piece's new number is whatever the table says for "g, then r". (Starting from solved, g is 0, and "0, then r" is just r, as in the diagram above.)
3. Draw. Each piece's home shape is rotated by its current number's rotation and drawn.

Pieces outside the layer keep their numbers. Undoing a turn is the same lookup with the opposite rotation. Here's a 2×2×2, mixed up a little, whose 8 pieces each hold one of its 24 rotations. The boxed number on each piece is its rotation, and it rides along with the piece. The gray #0 to #7 around the cube mark where each piece started, and stay put.

All zeros is the state the puzzle starts in, but it isn't the only solved one. Turn both layers of a 2×2×2 the same way, one after the other, and the whole cube has turned: every piece now holds the same number, and every face is still one color.

So the engine doesn't look for zeros. It keeps a second table: for each rotation, which face it sends each face to. With it, it works out which face every sticker points at now, and calls the puzzle solved when every face shows a single color. That also covers pieces that look alike. A 3×3×3's center spun in place has a new number but looks the same, and on a 4×4×4 two centers of the same color can swap places without anything changing.

The obvious way to build this is to store every corner of every piece as an x, y and z, and have a turn rotate those corners. That would have worked. A computer can't rotate exactly, though: a quarter turn uses cos 90°, which is 0 but comes out as 6.1×10⁻¹⁷, so four quarter turns bring (1, 0, 0) back as (1, −2.4×10⁻¹⁶, 0). Every turn adds a little more error. The chart turns a megaminx at random both ways and measures how far the moved corners have drifted from the exact positions.

That never becomes visible. The difference shows up in the yes/no questions. With drifting corners, "which side of this cut is the piece on?" and "is the puzzle solved?" have to compare numbers that are almost equal, so each needs a tolerance. With the list of whole numbers, they have exact answers. "Solved" becomes a second table lookup: for each sticker, which face its piece's rotation points it at, then checking that every face shows one color. Two puzzle states can be compared number by number.

The torus, Klein bottle and projective plane use the same idea in 2D. The state is one whole number per cell: which piece is there, times 4, plus two bits for whether it's been mirrored left-right or top-bottom by sliding across a flipped edge. A slide moves the numbers around a loop and flips those bits where the loop crosses a mirrored edge.