Introduction

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.

Place the Fleet

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">Each number on the right is the <b>ship cells in that row</b>; each number on the bottom is the <b>ship cells in that column</b>. Click cells to place ship segments (click again to clear) until <b>every</b> count matches. Checking a grid is instant — finding a valid placement is the hard part.</p>
<div id="wrap" class="wrap"></div>
<div class="status" id="status">Place ships, then check.</div>
<div class="btns">
  <button id="check" type="button">Check grid</button>
  <button id="solve" type="button">Solve it</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; }
.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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Solitaire Battleship "consistency": given the ship-cells-per-row and ship-cells-per-column counts, is there a placement of ships that hits every count exactly? Checking one grid is a quick scan of sums; finding one in general is NP-complete (Sevenster, 2004) — brute force tries 2^(cells).
const N = 5;
// A fixed target solution (1 = ship). The clues below are derived from it.
const SOLUTION = [
  [1,0,0,1,1],
  [0,0,0,0,0],
  [1,0,1,0,0],
  [1,0,0,0,1],
  [0,0,1,0,1],
];
const ROW = SOLUTION.map(r => r.reduce((a,b)=>a+b,0));
const COL = Array.from({length:N}, (_,c) => SOLUTION.reduce((a,r)=>a+r[c],0));
const TOTAL = ROW.reduce((a,b)=>a+b,0);

let grid = Array.from({length:N}, () => Array(N).fill(0)); // player's ships

function rowSum(g,r){ return g[r].reduce((a,b)=>a+b,0); }
function colSum(g,c){ let s=0; for(let r=0;r<g.length;r++) s+=g[r][c]; return s; }

function render(){
  const w = document.getElementById('wrap'); w.innerHTML='';
  for(let r=0;r<N;r++){
    const row = document.createElement('div'); row.className='row';
    for(let c=0;c<N;c++){
      const d = document.createElement('div');
      d.className = 'cell sea' + (grid[r][c] ? ' ship' : '');
      d.addEventListener('click', ()=>{ grid[r][c] = grid[r][c]?0:1; render();
        setStatus('Place ships, then check.',''); });
      row.appendChild(d);
    }
    // row count badge
    const rc = document.createElement('div');
    const s = rowSum(grid,r);
    rc.className = 'count' + (s===ROW[r] ? ' met' : (s>ROW[r] ? ' over' : ''));
    rc.textContent = ROW[r];
    row.appendChild(rc);
    w.appendChild(row);
  }
  // bottom column counts
  const bot = document.createElement('div'); bot.className='row';
  for(let c=0;c<N;c++){
    const cc = document.createElement('div');
    const s = colSum(grid,c);
    cc.className = 'count' + (s===COL[c] ? ' met' : (s>COL[c] ? ' over' : ''));
    cc.textContent = COL[c];
    bot.appendChild(cc);
  }
  w.appendChild(bot);
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

// A grid is valid iff every row sum and column sum equals its clue.
function valid(g){
  for(let r=0;r<N;r++) if(rowSum(g,r)!==ROW[r]) return false;
  for(let c=0;c<N;c++) if(colSum(g,c)!==COL[c]) return false;
  return true;
}
function check(){
  if(valid(grid)) setStatus('All counts match — valid fleet placement!','ok');
  else setStatus('Some row or column is off. Keep deducing.','bad');
}
// Brute-force search over every cell being ship/sea: 2^(N*N) in the worst case. We prune by row: skip placements whose row sum already breaks the clue.
function solve(){
  let steps = 0, sol = null;
  const g = Array.from({length:N}, () => Array(N).fill(0));
  function place(r){
    if(sol) return;
    if(r===N){ steps++; if(valid(g)) sol = g.map(row=>row.slice()); return; }
    // enumerate the 2^N patterns for this row, keep only those matching ROW[r]
    for(let mask=0; mask<(1<<N); mask++){
      let s=0; for(let c=0;c<N;c++) s += (mask>>c)&1;
      if(s!==ROW[r]) continue;
      for(let c=0;c<N;c++) g[r][c] = (mask>>c)&1;
      // prune: no column may already exceed its clue
      let ok=true; for(let c=0;c<N;c++) if(colSum(g.slice(0,r+1),c)>COL[c]){ ok=false; break; }
      if(ok) place(r+1);
      if(sol) return;
    }
    for(let c=0;c<N;c++) g[r][c]=0;
  }
  place(0);
  if(sol){ grid = sol; render();
    setStatus(fmt('Found a valid placement after %steps% full-grid checks.', { steps: steps }),'ok');
    console.log('Solution:', JSON.stringify(sol), '| checks', steps); }
  else setStatus('No placement satisfies these counts.','bad');
}
document.getElementById('check').addEventListener('click',check);
document.getElementById('solve').addEventListener('click',solve);
document.getElementById('reset').addEventListener('click',()=>{ grid=Array.from({length:N},()=>Array(N).fill(0)); render(); setStatus('Place ships, then check.',''); });
render();
Result
Console

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.

The Real Complexity

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

Where It Matters

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

Conclusion

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.

Share this article

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

Comments

Loading comments...

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