Sudoku, Instant Insanity, Tangrams, the Soma Cube, Pentomino Tiling and even logic puzzles like "Who Owns the Zebra" can all be thought of as tasks in which a "shattered" or disassembled object needs to be reconstructed from a collection of pieces.

Whether you are fixing a broken Greek urn, or solving a puzzle, a standard technique involves backtracking, that is, making a series of guesses until you hit a dead end, and then backing up to the last choice you made and trying the next one. This is a steady and sure procedure, but can be slow, and doesn't provide much insight into the problem.

Many of these problems can instead, almost magically, be turned into the task of solving an underdetermined linear system, something we know a lot about. I will concentrate on the particular case of tiling a region with polyominoes.

We consider a Fictitious Domain formulation of an elliptic PDE, and solve the arising saddle-point problem by an inexact preconditioned Uzawa iteration.

Solving the arising ‘inner’ elliptic problems with an adaptive finite element method, we prove that the overall method converges with the best possible rate.

This is a joint work with S. Berrone (Torino), A. Bonito (Texas A&M), and M. Verani (Milano)