The Tents Puzzle

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.

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">{{hint}}</p>
<div id="grid" class="grid"></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="check" type="button">{{btn_check}}</button>
  <button id="find" type="button">{{btn_find}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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 — $2^{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.

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

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.