The Persistent Programmer's Puzzle

We've all encountered puzzles that defy manual solution—complex 3D arrangements requiring inhuman patience. Recently gifted a "very hard" wooden puzzle comprising 25 identical pieces and a 5x5x5 box, the author quickly realized that human cognition alone wouldn't suffice. The solution? Enlist the relentless computational power of a machine. This first installment details the elegant Haskell modeling required to prepare for algorithmic solving.

Anatomy of the Challenge

The puzzle's components are deceptively simple:
- A 5×5×5 cubic box representing a discrete 3D grid
- 25 identical pieces, each composed of four connected cubes forming a trunk (4×1×1) with a single protruding cube creating an L-shape

-- Representing the base piece in voxel coordinates
genericPiece :: [V3 Int]
genericPiece = [V3 0 0 0, V3 0 0 1, V3 0 0 2, V3 0 0 3, V3 0 1 2]

Mathematical Foundations: Rotations and Translations

Each piece's position and orientation is modeled as a Disposition—a combination of:
1. Rotation: A 3×3 matrix (M33 Int) representing orthogonal transformations
2. Translation: A 3D vector (V3 Int) specifying positional offset

data Disposition = Disposition { rotation :: M33 Int, translation :: V3 Int }

Constrained Enumeration Strategy

Brute-force enumeration is infeasible. Instead, we systematically narrow possibilities:

Rotation Matrix Generation

Valid rotations in discrete space must map basis vectors to axes-aligned directions. We generate candidate matrices using list comprehensions:

candidateRotations :: [M33 Int]
candidateRotations = 
  [ V3 (V3 r1x r1y r1z)
        (V3 r2x r2y r2z)
        (V3 r3x r3y r3z)
  | r1x <- [-1,0,1], r1y <- [-1,0,1], r1z <- [-1,0,1]
  -- ... all combinations for 9 coefficients
  ]

Translation Boundary Conditions

Translations are constrained by the puzzle's physical bounds (1–5 per axis). Since the generic piece includes the origin, translation coordinates directly map to grid positions:

candidateTranslations :: [V3 Int]
candidateTranslations = 
  [ V3 x y z | x <- [1..5], y <- [1..5], z <- [1..5] ]

Validation Through Linear Algebra

Candidate dispositions are filtered using mathematical invariants of rotation matrices:
1. Orthogonality: $M^T M = I$ (preserves vector norms)
2. Special Condition: det(M) = 1 (preserves orientation)

isRotation :: M33 Int -> Bool
isRotation m = 
  (m `multmm` transpose m) == identity && -- Orthogonal
  det m == 1                               -- Special

Final Validation Pipeline

Dispositions are valid only if:
1. Their rotation matrix satisfies isRotation
2. All transformed piece voxels fit within the 5×5×5 grid

validDispositions :: [Disposition]
validDispositions = 
  [ d | d <- candidateDispositions
      , isRotation (rotation d)
      , all inBox (pieceVoxels d)
  ]
  where 
    inBox v = all (\c -> c >= 1 && c <= 5) (toList v)

Why This Matters for Developers

This approach demonstrates how mathematical rigor transforms physical constraints into programmable rules. By leveraging:
- Group theory (rotation symmetries)
- Linear algebra (matrix orthogonality)
- Constraint propagation (boundary checks)

...we convert an intractable physical problem into a computationally solvable one. The final step—solving the full 25-piece arrangement using these validated dispositions—awaits in Part II, where Haskell's declarative power will shine.

Source: Original Haskell Puzzle Solution