Cracking the Corn Puzzle via CP-SAT

One random Friday at RC, I found myself fiddling with a 3D-printed puzzle. The setup was simple: a white "cob" featuring various grooves and a set of "corn" pieces. Each piece consisted of between 3 and 10 kernels fused together in specific shapes.

The Objective: Slide every piece into the grooves so they fit perfectly—leaving no gaps and ensuring zero overlaps.

As a software engineer living in the year of our lord 2026, I quickly lost interest in manual trial-and-error. I turned to Claude for help. After some initial friction—since computer vision still isn't perfect and I had to manually describe some piece geometries—Claude generated a Python script that solved it. The resulting code was far more elegant than anything I would have drafted, providing a great learning opportunity.

The "Naive" Path: Recursive Backtracking

Had I tackled this alone, I likely would have used brute force recursive backtracking. This is the standard "Intro to CS" approach:

1. Pick a piece and place it in a legal spot.
2. Repeat until the puzzle is solved.
3. If you hit a dead end (no legal moves left), backtrack to the previous step.
4. Try a different configuration and repeat.

While basic, you can optimize this by:

• Symmetry Breaking: Recognizing that rotating the entire cob doesn't change the solution.
• Early Pruning: Failing immediately if a single kernel space becomes isolated and impossible to fill.

Logic Flow: Backtracking vs. CP-SAT

The "Professional" Path: OR-Tools CP-SAT

When I saw the first line of Claude's code, I realized I was overthinking the implementation:

from ortools.sat.python import cp_model

Instead of writing a custom search algorithm, Claude used Google's OR-Tools CP-SAT, an industrial-grade library designed for satisfiability and constrained optimization problems.

The core philosophy of CP-SAT is to model a problem as a collection of variables (often binary) and a set of assertions (constraints) that must all be true simultaneously.

Modeling the Corn Puzzle

This specific puzzle is a variation of the Exact Cover problem. Here is how it is represented mathematically:

1. Variables We use binary variables $V_{i,n}$, where $i$ is the piece and $n$ is a specific possible placement.

• $V_{i,n} = 1$ if piece $i$ is placed in position $n$.
• $V_{i,n} = 0$ otherwise.

2. Constraints To ensure a valid solution, we apply two classes of constraints:

(Where $C_s$ is the set of all possible piece placements that cover space $s$.)

If the total kernel count equals the total cob spaces, these two rules are sufficient.

The Implementation

While the logic to enumerate every possible rotation and position for the pieces was complex, the actual solver call was incredibly concise:

# An artisanal hand-crafted CP-SAT invocation
for plist in by_piece:
    m.Add(sum(v for v, _ in plist) == 1)

for clist in by_cell:
    m.Add(sum(v for v, _ in clist) == 1)

m.solve(m)

Expanding the Lesson: Sudoku

To solidify this knowledge, I teamed up with Zaki and Tommy at Recurse to solve a more classic puzzle: Sudoku.

Sudoku is even simpler to model because we don't need to calculate rotations. We simply create a variable for each cell with a value between 1 and 9.

The Sudoku Checklist:

• Define a $9 \times 9$ grid of integer variables.
• Constrain every row to be all_different.
• Constrain every column to be all_different.
• Constrain every $3 \times 3$ box to be all_different.

Here is the implementation logic:

model_vars = [[None for _ in range(9)] for _ in range(9)]

for i in range(9):
    for j in range(9):
        board_var_name = f"s[{i},{j}]"
        if board[i][j] == -1:
            model_vars[i][j] = model.new_int_var(1, 9, board_var_name)
        else:
            # For pre-filled cells, the variable is constrained to a single value
            model_vars[i][j] = model.new_int_var(board[i][j], board[i][j], board_var_name)

# Row Constraints
for r in range(9):
    model.add_all_different([model_vars[r][c] for c in range(9)])

# Column Constraints
for c in range(9):
    model.add_all_different([model_vars[r][c] for r in range(9)])

# Box Constraints
for off_r in range(3):
    for off_c in range(3):
        model.add_all_different([model_vars[3 * off_r + numpad % 3][3 * off_c + numpad // 3] for numpad in range(9)])

This approach solved our reference Sudoku almost instantaneously.

Final Thoughts

There is still plenty to explore within the realm of constraint programming, but the primary takeaway is clear: don't reinvent the wheel. The next time I encounter a problem that looks like a puzzle, I'll head straight for the solver documentation.