Introduction

You have probably met the Tents puzzle — sometimes called Tents and Trees — in a newspaper or a phone app. A grid is dotted with trees, and your job is to pitch a tent next to each one. The rules sound almost too gentle to matter:

  • Every tree gets exactly one tent, placed in an adjacent square (up, down, left or right).
  • Every tent belongs to exactly one tree, so tents and trees pair up one-to-one.
  • No two tents touch — not even diagonally.
  • The numbers along the edges say how many tents go in each row and column.

Most of the time you solve it by comfortable, local reasoning: this tree only has one free neighbor, so the tent must go there; this row already has its quota, so the rest is empty. But every so often the easy deductions run out and you are left guessing. That little gap — between what the rules force and what you must search for — is exactly the line that separates the easy problems from the hardest ones in all of computer science.

Pitch the Tents

Here is a small camp. The trees are fixed; the numbers count the tents in each row and column. Click the empty cells to pitch tents until every rule holds: one tent per tree, no two tents touching, and the counts all matching.

<p class="hint">Each <b>tree</b> 🌲 needs exactly one <b>tent</b> ⛺ pitched right beside it (up, down, left or right). Tents may never touch each other — not even diagonally. The numbers count the tents in each row and column. Click the empty cells to pitch tents until every rule holds. Checking a layout is instant — finding one is the hard part.</p>
<div id="grid" class="grid"></div>
<div class="status" id="status">Pitch the tents, then check.</div>
<div class="btns">
  <button id="check" type="button">Check layout</button>
  <button id="find" type="button">Find a valid layout</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(6, 44px); gap: 4px; margin: .4rem 0; }
.cell { width: 44px; height: 44px; display: flex; align-items: center; justify-content: center;
        font: 700 20px ui-monospace, monospace; border-radius: 8px; user-select: none; }
.clue { background: transparent; color: #1d3557; font-weight: 800; }
.tree { background: #d6ead9; border: 1px solid #b6d4ba; }
.field { background: #e8e2d2; border: 1px solid #d3cab2; cursor: pointer; transition: all .1s; }
.field:hover { background: #ded6c1; }
.field.tent { background: #f4a259; border-color: #e08b3c; }
.field.tent::after { content: "⛺"; }
.tree::after { content: "🌲"; }
.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] ?? ''));
// The Tents puzzle: pitch one tent next to each tree so that (1) tents and trees pair up one-to-one with orthogonal adjacency, (2) no two tents touch (even diagonally), and (3) each row/column has its given number of tents. Checking a finished layout is a quick scan; finding one is NP-complete (the decision version is as hard as SAT). Brute force here tries 2^(empty cells).
const N = 5;
const TREES = [[0,1],[1,3],[2,0],[3,2],[4,4]];
const ROW = [2,0,1,1,1];   // tents per row
const COL = [1,1,1,1,1];   // tents per column
const key = (r,c) => r + ',' + c;
const isTree = (r,c) => TREES.some(([a,b]) => a===r && b===c);
const CAND = [];
for (let r=0;r<N;r++) for (let c=0;c<N;c++) if (!isTree(r,c)) CAND.push([r,c]);

const placed = new Set(); // player's tents

function render(){
  const g = document.getElementById('grid'); g.innerHTML='';
  // top-left corner blank
  const corner = document.createElement('div'); corner.className='cell clue'; g.appendChild(corner);
  // column clues
  for (let c=0;c<N;c++){ const d=document.createElement('div'); d.className='cell clue'; d.textContent=COL[c]; g.appendChild(d); }
  for (let r=0;r<N;r++){
    const rc=document.createElement('div'); rc.className='cell clue'; rc.textContent=ROW[r]; g.appendChild(rc);
    for (let c=0;c<N;c++){
      const d=document.createElement('div'); const k=key(r,c);
      if (isTree(r,c)){ d.className='cell tree'; }
      else { d.className='cell field'+(placed.has(k)?' tent':'');
        d.addEventListener('click',()=>{ placed.has(k)?placed.delete(k):placed.add(k); render(); setStatus('Pitch the tents, then check.',''); }); }
      g.appendChild(d);
    }
  }
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

// A layout is valid iff all three families of constraints hold.
function valid(tents){
  const list=[...tents].map(k=>k.split(',').map(Number));
  // (1) row/column counts
  const rc=new Array(N).fill(0), cc=new Array(N).fill(0);
  for (const [r,c] of list){ rc[r]++; cc[c]++; }
  for (let i=0;i<N;i++) if (rc[i]!==ROW[i] || cc[i]!==COL[i]) return false;
  // (2) no two tents touch (8-neighborhood)
  for (let i=0;i<list.length;i++) for (let j=i+1;j<list.length;j++){
    const [a,b]=list[i], [x,y]=list[j];
    if (Math.abs(a-x)<=1 && Math.abs(b-y)<=1) return false;
  }
  // (3) tents pair one-to-one with trees via orthogonal adjacency (bipartite matching)
  if (list.length!==TREES.length) return false;
  const adj=TREES.map(([tr,tc])=>{ const l=[]; list.forEach(([er,ec],i)=>{ if(Math.abs(tr-er)+Math.abs(tc-ec)===1) l.push(i); }); return l; });
  const m=new Array(list.length).fill(-1);
  const tryK=(u,seen)=>{ for(const v of adj[u]){ if(!seen[v]){ seen[v]=true; if(m[v]<0||tryK(m[v],seen)){ m[v]=u; return true; } } } return false; };
  let cnt=0; for(let u=0;u<TREES.length;u++){ if(tryK(u,new Array(list.length).fill(false))) cnt++; }
  return cnt===TREES.length;
}
function check(){
  if (valid(placed)) setStatus('✓ Every rule holds — valid camp!','ok');
  else setStatus('✗ A rule is broken. Keep deducing.','bad');
}
function find(){
  let steps=0, sol=null;
  for (let mask=0; mask<(1<<CAND.length); mask++){ steps++;
    const t=new Set(); CAND.forEach(([r,c],i)=>{ if(mask&(1<<i)) t.add(key(r,c)); });
    if (valid(t)){ sol=t; break; } }
  if (sol){ placed.clear(); sol.forEach(k=>placed.add(k)); render();
    setStatus(fmt('Found a valid camp after checking %steps% layouts.', { steps: steps }),'ok');
    console.log('Tents:', [...sol].join(' '), '| checked', steps, 'of', (1<<CAND.length)); }
  else setStatus('No layout satisfies these clues.','bad');
}
document.getElementById('check').addEventListener('click',check);
document.getElementById('find').addEventListener('click',find);
document.getElementById('reset').addEventListener('click',()=>{ placed.clear(); render(); setStatus('Pitch the tents, then check.',''); });
render();
Result
Console

Notice the asymmetry. Checking a finished camp is effortless: confirm each tree has its tent, no two tents touch, and the edge numbers add up. Finding a layout that satisfies everything at once is the hard part — press Find a valid layout and the computer simply tries every combination of tents on the empty cells. With twenty empty cells that is over a million possibilities; add a few more and the count doubles each time.

The Real Complexity

How hard is the Tents puzzle, really? Not the playing — the reasoning.

  • Checking a candidate camp is trivial: verify the one-tent-per-tree pairing, the no-touching rule, and the row and column totals.
  • Brute force tries every way to place tents on the empty cells — 2n2^{n} layouts, hopeless once there are more than a few dozen unknowns.
  • It's NP-complete. Deciding whether a given Tents board has any valid solution is as hard as any problem in NP. The puzzle's local rules — "this tent must sit beside a tree," "these two squares can't both hold tents," "this line needs exactly k tents" — are precisely the building blocks of SAT clauses, so any logical satisfiability question can be reshaped into a Tents board. This kind of hardness has been established for the broad family of Nikoli-style pencil puzzles (Tents, Slitherlink, Nurikabe and friends), with the general framework laid out by researchers such as Demaine and collaborators.
  • So deciding even is-this-board-solvable is equivalent to the whole NP-complete family — and asking whether one particular square is guaranteed to hold a tent is just as hard.

That is the punchline: the moment a position can't be settled by quick local logic, you are staring at a genuine instance of the same problem behind P vs NP. The guesses the puzzle forces on you are not laziness on your part — they are intractability made cozy.

Where It Matters

"Satisfy all these local constraints at once" is one of the most common shapes a real problem can take, and the Tents puzzle is its friendly face:

  • Pairing and assignment: matching each tree to a distinct neighboring tent is the same idea as assigning workers to jobs or students to rooms — one-to-one with adjacency rules.
  • Resource placement: "spread these antennas, sensors or facilities so none crowd each other, while hitting per-region quotas" is a placement-with-spacing problem, exactly the no-touching-plus-counts core of Tents.
  • Logic and SAT solving: because the rules translate into clauses, the very same solvers that crack hardware-verification and planning problems can solve Tents instances directly.
  • Teaching complexity: cozy puzzles like this are some of the clearest on-ramps to what NP-completeness even means.

Learn why the Tents puzzle is hard and you've met constraint satisfaction — the engine under SAT, graph coloring and countless scheduling problems.

Conclusion

The Tents puzzle hides a beautiful secret: the same gentle rules that let you pitch tents one by one can be wired into logic clauses, and through them into any problem in NP. Checking a finished camp stays instant; deciding whether a camp is even possible is as hard as anything in computer science.

So the next time a Tents board leaves you with no forced move and a fork in the road, take comfort — you haven't lost your touch. You've simply run into P vs NP hiding under a row of little tents, and there may be no clever way around the search 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/tents-puzzle/Content licensed under CC BY-NC 4.0.