Introduction

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.

Fill the Grid

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">Pick a 3-letter word for each slot. Wherever an Across and a Down slot share a square, their letters <b>must</b> match. Checking a fill is instant — finding one means backtracking through a tree of choices.</p>
<div id="grid" class="grid"></div>
<div class="slots" id="slots"></div>
<div class="status" id="status">Choose a word for every slot.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Crossword construction: fit words from a fixed list into a grid so that every crossing square agrees on one letter. Checking a fill is a quick scan of the crossings; finding one is NP-complete (Garey & Johnson, 1979) — a backtracking search over the tree of word choices, pruning whenever two letters clash.
const WORDS = ['CAT','DOG','CAD','TUG','BAT','GUM','RID','SUN'];

// Slots: each is a list of [row,col] cells (all length 3). Two slots that share a cell impose an equality constraint on the letters placed there.
const SLOTS = {
  A1: { cells: [[0,0],[0,1],[0,2]] }, // across, top row
  A2: { cells: [[2,0],[2,1],[2,2]] }, // across, bottom row
  D1: { cells: [[0,0],[1,0],[2,0]] }, // down, left column
  D2: { cells: [[0,2],[1,2],[2,2]] }, // down, right column
};
const ORDER = ['A1','A2','D1','D2'];
const LABEL = { A1:'Across 1', A2:'Across 2', D1:'Down 1', D2:'Down 2' };
const key = (r,c) => r + ',' + c;
// Cells that are part of some slot; everything else is a black block.
const CELLS = new Set();
ORDER.forEach(s => SLOTS[s].cells.forEach(([r,c]) => CELLS.add(key(r,c))));

const choice = {}; // slot -> word (or '')
ORDER.forEach(s => choice[s] = '');

// Letter each slot places on a cell, given current choices.
function letterAt(r,c){
  const out = [];
  for(const s of ORDER){
    const w = choice[s]; if(!w) continue;
    SLOTS[s].cells.forEach(([cr,cc],i) => { if(cr===r && cc===c) out.push(w[i]); });
  }
  return out;
}

function buildSelectors(){
  const host = document.getElementById('slots'); host.innerHTML='';
  for(const s of ORDER){
    const row = document.createElement('div'); row.className='slot';
    const lab = document.createElement('label'); lab.textContent = LABEL[s] + ':';
    const sel = document.createElement('select');
    const blank = document.createElement('option'); blank.value=''; blank.textContent='— pick —'; sel.appendChild(blank);
    WORDS.forEach(w => { const o=document.createElement('option'); o.value=w; o.textContent=w; sel.appendChild(o); });
    sel.value = choice[s];
    sel.addEventListener('change', () => { choice[s]=sel.value; render(); setStatus('Choose a word for every slot.',''); });
    row.appendChild(lab); row.appendChild(sel); host.appendChild(row);
  }
}

function render(){
  const g = document.getElementById('grid'); g.innerHTML='';
  for(let r=0;r<3;r++)for(let c=0;c<3;c++){
    const d=document.createElement('div'); const k=key(r,c);
    if(!CELLS.has(k)){ d.className='sq block'; g.appendChild(d); continue; }
    const ls = letterAt(r,c);
    const clash = ls.length>1 && ls.some(x => x!==ls[0]);
    d.className='sq fill'+(clash?' clash':'');
    d.textContent = ls.length ? ls[0] : '';
    g.appendChild(d);
  }
  // refresh selector values (auto-solve changes them)
  const sels = document.querySelectorAll('#slots select');
  sels.forEach((sel,i) => sel.value = choice[ORDER[i]]);
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

// A fill is valid iff every slot has a word and no crossing square clashes.
function valid(assign){
  for(const s of ORDER) if(!assign[s]) return false;
  for(let r=0;r<3;r++)for(let c=0;c<3;c++){
    if(!CELLS.has(key(r,c))) continue;
    const ls=[];
    for(const s of ORDER){ const w=assign[s]; SLOTS[s].cells.forEach(([cr,cc],i)=>{ if(cr===r&&cc===c) ls.push(w[i]); }); }
    if(ls.length>1 && ls.some(x=>x!==ls[0])) return false;
  }
  return true;
}
// Partial check: do the slots already chosen agree on shared cells?
function consistent(assign){
  for(let r=0;r<3;r++)for(let c=0;c<3;c++){
    if(!CELLS.has(key(r,c))) continue;
    const ls=[];
    for(const s of ORDER){ const w=assign[s]; if(!w) continue; SLOTS[s].cells.forEach(([cr,cc],i)=>{ if(cr===r&&cc===c) ls.push(w[i]); }); }
    if(ls.length>1 && ls.some(x=>x!==ls[0])) return false;
  }
  return true;
}

function check(){
  if(valid(choice)) setStatus('✓ Every crossing agrees — valid crossword!','ok');
  else setStatus('✗ A slot is empty or two letters clash. Keep fitting.','bad');
}

// Backtracking search: assign words slot by slot, pruning the moment a crossing clashes.
function solve(){
  let nodes=0; const assign={};
  function bt(i){
    if(i===ORDER.length) return consistent(assign) && Object.keys(assign).length===ORDER.length;
    const s=ORDER[i];
    for(const w of WORDS){ nodes++; assign[s]=w;
      if(consistent(assign)){ if(bt(i+1)) return true; } }
    delete assign[s]; return false;
  }
  if(bt(0)){ ORDER.forEach(s=>choice[s]=assign[s]); render();
    setStatus(fmt('Solved by backtracking after %nodes% word placements.', { nodes: nodes }),'ok');
    console.log('Solution:', ORDER.map(s=>s+'='+choice[s]).join(' '), '| placements', nodes); }
  else { setStatus('No fill exists for this grid and word list.','bad'); }
}

document.getElementById('check').addEventListener('click',check);
document.getElementById('solve').addEventListener('click',solve);
document.getElementById('reset').addEventListener('click',()=>{ ORDER.forEach(s=>choice[s]=''); render(); setStatus('Choose a word for every slot.',''); });
buildSelectors(); render();
Result
Console

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.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/crossword-construction/Content licensed under CC BY-NC 4.0.