Battleship Puzzle

You have probably met Solitaire Battleship in a newspaper or puzzle book. A square grid hides a whole fleet — a battleship, a couple of cruisers, some destroyers, a scatter of single-cell submarines. Around the edges sit numbers: each row and each column tells you how many ship cells it contains. Your job is to place every ship so that all the counts come out exactly right, with no two ships touching, not even diagonally.

Most of the time you reason it out: a row that needs zero ships clears a whole strip, a column that's already full blocks the rest. Step by step the fleet falls into place.

But that comfortable feeling of "the numbers force it" has a limit. When the easy deductions run out, you are left searching — and that search is exactly where the puzzle stops being a pastime and becomes one of the hardest kinds of problem in all of computer science.

Here is a small 5×5 grid. The numbers on the right give the ship cells per row; the numbers on the bottom give the ship cells per column. Click cells to place ship segments (click again to clear) until every count on the edges matches exactly.

<p class="hint">{{hint}}</p>
<div id="wrap" class="wrap"></div>
<div class="status" id="status">{{place_then_check}}</div>
<div class="btns">
  <button id="check" type="button">{{btn_check}}</button>
  <button id="solve" type="button">{{btn_solve}}</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; }
.wrap { display: inline-grid; gap: 4px; margin: .4rem 0; }
.row { display: flex; gap: 4px; align-items: center; }
.cell { width: 44px; height: 44px; display: flex; align-items: center; justify-content: center;
        border-radius: 8px; user-select: none; }
.sea { background: #c9ccd1; border: 1px solid #adb1b8; cursor: pointer; transition: all .1s; }
.sea:hover { background: #bcc0c6; }
.sea.ship { background: #1d3557; border-color: #14253e; }
.sea.ship::after { content: ""; width: 20px; height: 20px; border-radius: 50%; background: #cfe1f5; }
.count { width: 44px; height: 44px; display: flex; align-items: center; justify-content: center;
         font: 700 18px ui-monospace, monospace; color: #1d3557; }
.count.met { color: #0a7d33; }
.count.over { color: #c92f3c; }
.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 grid is effortless: add up each row and column and compare to the clue. Finding a placement that hits every count at once is the hard part — press Solve it and the computer simply tries every way to fill the cells. With a handful of cells that's already dozens of combinations; widen the grid and the count doubles with every new cell. That doubling is the whole story.

How hard is the Battleship puzzle, really? Not the relaxing part — the reasoning.

• Checking a finished grid is trivial: sum each row and column, confirm the fleet is the right shape, and verify no two ships touch.
• Brute force tries every way to mark cells as ship or sea — $2^{n}$ grids for n cells, hopeless once the board grows past a few dozen squares.
• It's NP-complete. In 2004 Merlijn Sevenster proved that deciding whether a Solitaire Battleship instance has any valid solution is NP-complete. The edge counts plus the no-touching rule are expressive enough to encode arbitrary hard constraints, so the puzzle inherits the full difficulty of NP.
• So even "does this puzzle have a solution at all?" is as hard as the whole NP-complete family — and pinning down whether a single cell must be a ship is just as hard.

That is the punchline: the moment a position can't be settled by quick local counting, you are staring at a genuine instance of the same problem behind P vs NP. The search the puzzle forces on you isn't a flaw in the design — it is intractability made playable, the same wall you hit with SAT and graph coloring.

"Fit these objects so every row and column count comes out right" is a shape that real problems take constantly, and the Battleship puzzle is its friendly face:

• Discrete tomography: reconstructing an image from row and column sums of projections is the same counting puzzle, used in scanning materials and crystals.
• Packing and layout: fitting parts onto a sheet or chips onto a die without overlap is exactly "place objects subject to capacity limits."
• Scheduling and configuration: timetables and resource grids are "find an assignment that meets every per-row and per-column quota."
• Teaching complexity: because the rules fit in two sentences, Battleship is a clean on-ramp to what NP-completeness even means.

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

The Battleship puzzle hides a beautiful secret: the same row and column numbers that guide a relaxing solve can encode arbitrary hard constraints, and through them any problem in NP. Checking a finished grid stays instant; deciding whether a grid can be solved at all is as hard as anything in computer science — Sevenster proved it NP-complete in 2004.

So the next time the clues run dry and you're reduced to trying placements one by one, take comfort — you haven't lost the thread. You've simply run into P vs NP hiding behind a grid of little gray ships, and there may be no clever shortcut around the search at all.