L-Panel

L-Panel is the puzzle of tiling with bent pieces. The grid is a rectangle of white cells interrupted by an irregular scattering of black cells. The solver covers every white cell with L-shaped tetrominoes, each occupying exactly four cells in one of eight orientations (four rotations of the L-tetromino and their four mirror images, equivalently the L- and J-tetrominoes of Tetris). No tile may overlap another, no tile may cross a black cell, and no white cell may be left uncovered.

L-Panel is a pure exact-cover puzzle. Unlike the shading and line-drawing puzzles elsewhere in this volume, there are no numeric clues to satisfy and no symmetry conditions to obey: the black cells alone determine the geometry, and the solver’s task is to jigsaw the remaining white region into L-tiles. The puzzle rewards patience with pattern-recognition over calculation, and it is particularly satisfying to watch a constraint solver reduce it to a single integer-programming expression and return the tiling in a few milliseconds.

The L-tetromino (also called the “L-piece”) is one of the seven one-sided tetrominoes studied in mathematical recreational theory. Every connected region with area divisible by four is L-tileable provided its shape is not too pathological, but deciding tileability of an arbitrary region is NP-hard in general (Moore and Robson, $2001$); L-Panel instances are hand-designed so that the black-cell scaffolding leaves a uniquely tileable white region.

Rules and a small instance

An L-Panel puzzle is an $R \times C$ grid of cells, each either white or black. The number of white cells must be divisible by four. A solution is a set of L-tetrominoes (any of the eight orientations) such that:

1. Every white cell belongs to exactly one tile.

2. No tile covers a black cell.

3. No two tiles overlap.

Figure 21.1 is a $6 \times 6$ L-Panel with eight black cells. The remaining $28$ white cells partition uniquely into $7$ L-tiles.

The programming model

The model is the textbook exact-cover formulation.

Candidate tiles

Enumerate the eight orientations of the L-tetromino as lists of $(\Delta r, \Delta c)$ offsets: $$\mathcal{S} \;=\; \bigl\{ \text{L, J, and all } 90^\circ \text{ rotations} \bigr\}.$$ For every cell $(r, c)$ of the grid and every shape $S \in \mathcal{S}$, form the placement $$P(r, c, S) \;=\; \{ (r + \Delta r, c + \Delta c) \,:\, (\Delta r, \Delta c) \in S \}.$$ Retain $P(r, c, S)$ as a candidate tile if all four of its cells lie inside the grid and none is black. Let $\mathcal{T}$ denote the resulting set of candidate tiles (as frozensets, to deduplicate placements of the same tile encountered via different anchor cells).

Exact cover

Introduce a Boolean variable $t_T \in \{0, 1\}$ for each $T \in \mathcal{T}$, with $t_T = 1$ meaning “tile $T$ is selected.” For every white cell $(r, c)$, $$\sum_{T \in \mathcal{T} \,:\, (r, c) \in T} t_T \;=\; 1.$$ This is a classical exact-cover constraint: the $|\mathcal{T}|$-by-$N$ incidence matrix $[(r, c) \in T]$ has row sum equal to $1$ in every white-cell row. The constraint is tight: if a white cell is covered by zero tiles, it is uncovered (forbidden); if it is covered by two or more tiles, they overlap (forbidden).

No explicit overlap constraint is needed, because the exact-cover condition on every white cell implies that every chosen tile’s four cells are each covered by exactly that tile and no other.

A solver in thirty lines

from ortools.sat.python import cp_model
from collections import defaultdict

L_SHAPES = [
    [(0,0),(1,0),(2,0),(2,1)],
    [(0,0),(0,1),(0,2),(1,2)],
    [(0,1),(1,1),(2,1),(2,0)],
    [(1,0),(1,1),(1,2),(0,0)],
    [(1,0),(1,1),(1,2),(0,2)],
    [(0,0),(0,1),(1,0),(2,0)],
    [(0,0),(0,1),(1,1),(2,1)],
    [(0,0),(1,0),(0,1),(0,2)],
]

def solve_lpanel(board):
    R, C = len(board), len(board[0])
    polys = set()
    for r in range(R):
        for c in range(C):
            for sh in L_SHAPES:
                p = frozenset(
                    (r+dr, c+dc) for dr, dc in sh)
                if all(0 <= pr < R and 0 <= pc < C
                        and board[pr][pc] != -1
                       for pr, pc in p):
                    polys.add(p)
    m = cp_model.CpModel()
    t = {p: m.NewBoolVar("") for p in polys}
    cell_to_polys = defaultdict(list)
    for p in polys:
        for cell in p:
            cell_to_polys[cell].append(p)
    for r in range(R):
        for c in range(C):
            if board[r][c] != -1:
                m.Add(sum(t[p]
                           for p in cell_to_polys[(r, c)])
                      == 1)
    s = cp_model.CpSolver()
    s.Solve(m)
    return [p for p in polys if s.Value(t[p])]

The toy of Figure 21.1 solves uniquely in about $14$ milliseconds.

A hard instance

Figure 21.3 is a $10 \times 10$ L-Panel in the style of Alex Bellos’s Puzzle Ninja: twelve black cells scatter the interior, leaving $88$ white cells (exactly $22$ L-tiles) for the solver. CP-SAT returns the unique tiling in about $3$ milliseconds.

Sources. L-Panel appears in Alex Bellos’s Puzzle Ninja: Pit Your Wits Against the Japanese Puzzle Masters (Guardian Faber, $2017$), where it is credited to Japanese pencil-puzzle tradition. The hard instance of Figure 21.3 is puzzle $7$ from that collection. The exact-cover formulation used here is due to Dancing Links (Knuth, $2000$), though CP-SAT propagates the same logic via row-sum unit constraints; Knuth’s DLX algorithm remains the canonical exact-cover tool for hand-tuned enumeration. Tiling a region by L-tetrominoes is NP-hard in general (Moore and Robson, $2001$).