Crossword Construction

Every newspaper crossword you solve was first built — somebody chose a grid pattern and then dropped real words into it so that every horizontal and every vertical run spells something legal. Solving is fun. Construction is the quiet nightmare on the other side.

The catch is the interlock. Each square where an across word crosses a down word must agree on a single letter. Pick a word for one slot and you constrain every slot it touches; those constrain their neighbors, and the ripples cross the whole board. Choose a great word in the top-left corner and you might make a slot in the bottom-right impossible to fill.

That cascade of "this choice forces that choice" is not a quirk of crosswords. It is the same shape — many local constraints that must all hold at once — that sits at the heart of the hardest problems in computer science.

Here is a tiny grid with a few open slots and a fixed list of words. Pick a word for each slot. Wherever an across and a down slot share a square, their letters must match — a single clash makes the whole fill illegal.

<p class="hint">{{hint}}</p>
<div id="grid" class="grid"></div>
<div class="slots" id="slots"></div>
<div class="status" id="status">{{choose_word}}</div>
<div class="btns">
  <button id="check" type="button">{{check_fill}}</button>
  <button id="solve" type="button">{{auto_solve}}</button>
  <button id="reset" type="button" class="ghost">{{clear}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.grid { display: grid; grid-template-columns: repeat(3, 44px); gap: 3px; margin: .4rem 0; }
.sq { width: 44px; height: 44px; display: flex; align-items: center; justify-content: center;
      font: 700 20px ui-monospace, monospace; border-radius: 6px; user-select: none; text-transform: uppercase; }
.sq.fill { background: #fff; border: 1px solid #1d3557; color: #1d3557; }
.sq.fill.clash { background: #ffe0e3; border-color: #c92f3c; color: #c92f3c; }
.sq.block { background: #1d3557; }
.slots { display: flex; flex-direction: column; gap: .4rem; margin: .6rem 0; }
.slot { display: flex; align-items: center; gap: .5rem; font-size: .9rem; }
.slot label { min-width: 86px; font-weight: 600; color: #1d3557; }
select { font: 600 14px ui-monospace, monospace; padding: .3rem .5rem; border: 1px solid #adb1b8;
         border-radius: 6px; text-transform: uppercase; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Try it by hand, then press Auto-solve to watch a backtracking search at work. It places a word, checks the crossings, and the moment two letters disagree it backs up and tries another word. Notice the asymmetry: checking a finished fill is instant — just read every crossing. Finding a fill means searching a tree of choices that branches at every slot.

How hard is crossword construction, really? Not the solving — the building.

• Checking a candidate fill is trivial: confirm every word comes from the list and every crossing square shows the same letter for its two words.
• Brute force tries every assignment of list-words to slots. With many slots and a large dictionary the number of combinations explodes far beyond what any computer can scan.
• It's NP-complete. Deciding whether a given grid can be filled from a given word list is one of the classic NP-complete problems (catalogued by Garey & Johnson, 1979, as "Crossword Puzzle Construction"). The interlocking slots act as variables and the shared squares act as constraints, so any constraint-satisfaction problem — and through it any SAT formula — can be smuggled into a crossword grid.
• So even deciding is-this-grid-fillable is equivalent to the whole NP-complete family. No known algorithm beats the exponential blow-up in the worst case.

That is the punchline: the moment the crossings tangle badly enough that no quick local reasoning settles them, you are staring at a genuine instance of the same problem behind P vs NP. The dead ends a constructor hits are not bad luck — they are intractability wearing a checkered grid.

"Choose values so that every shared constraint is satisfied" is one of the most common shapes a real problem can take, and crossword construction is its friendly face:

• Constraint solving and SAT: the slots-and-crossings structure is a textbook constraint-satisfaction problem, and the same backtracking and propagation tricks power industrial SAT and CSP solvers.
• Timetabling and scheduling: rooms, slots and people interlock exactly like across and down words — every shared resource is a crossing that must agree.
• Layout and packing: fitting components on a chip or words on a page is "assign pieces so nothing conflicts."
• Compilers: register allocation assigns a limited set of registers to variables under interference constraints — the same fit-without-clashing puzzle.

Learn why a crossword is hard to build and you've met constraint satisfaction — the engine under SAT, graph coloring and countless scheduling and layout problems.

A crossword hides a beautiful secret: the same interlocking squares that make solving satisfying make building genuinely hard. Every slot is a variable, every shared square a constraint, and through them any problem in NP can be poured into the grid. Checking a fill stays instant; deciding whether a grid can be filled at all is as hard as anything in computer science.

So the next time a half-built crossword collapses because one corner just won't accept a legal word, take comfort — you haven't constructed badly. You've simply run into P vs NP hiding behind a grid of black-and-white squares, and there may be no clever way around the backtracking at all.