Peg Solitaire

You have probably seen the board in a café or on a grandparent's shelf: a wooden cross studded with holes, every hole but one filled with a peg. The rules are tiny. A peg may jump over an adjacent peg into an empty hole, and the peg it jumped over is removed. The goal is to keep jumping until a single peg survives.

It feels gentle. Yet every jump removes a piece you can never bring back, so the order of your moves matters enormously. A choice that looks fine early on can strand pegs in isolated corners with no legal jump left — and you only discover the dead end many moves later.

That gap between "this looks playable" and "this can actually be finished" is not a quirk of one wooden toy. It is the same line that separates the easy problems from the hardest ones in all of computer science.

Here is a small peg solitaire board. Click a peg, then click the empty hole two steps away in a straight line — the peg in between is removed. Try to reduce the board to one surviving peg.

<p class="hint">{{hint}}</p>
<div id="board" class="board"></div>
<div class="status" id="status">{{pegs_left_pre}} 6{{pick_peg}}</div>
<div class="btns">
  <button id="solve" type="button">{{btn_autosolve}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</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; }
.board { display: grid; grid-template-columns: repeat(5, 50px); gap: 5px; margin: .4rem 0; }
.cell { width: 50px; height: 50px; border-radius: 8px; }
.cell.hole { display: flex; align-items: center; justify-content: center;
             background: #e8eef3; border: 1px solid #cdd9e3; }
.cell.gap { background: transparent; border: none; }
.peg { width: 32px; height: 32px; border-radius: 50%; background: #1d3557;
       border: 2px solid #122340; cursor: pointer; transition: transform .08s; }
.peg:hover { transform: scale(1.08); }
.peg.sel { background: #e63946; border-color: #c92f3c; box-shadow: 0 0 0 3px #f6c9cd; }
.cell.hole.target { cursor: pointer; box-shadow: inset 0 0 0 2px #0a7d33; }
.cell.hole.target::after { content: "+"; color: #0a7d33; font-weight: 800; }
.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 game is effortless: just count the pegs left on the board. Finding the right sequence of jumps is the hard part — press Auto-solve and the computer searches move orders until one leaves a single peg. A short greedy run often strands you with two or three pegs frozen apart, even though a full solution was sitting one different jump away.

How hard is peg solitaire, really? Not on the classic 33-hole cross — that single board is small enough to solve once and remember. The hard question is the general one: given any arrangement of pegs on an arbitrarily large board, can it be reduced to a single survivor?

• Checking a finished game is trivial: count the pegs and see whether exactly one remains.
• Brute force explores the tree of move orders — and that tree branches viciously, because each jump opens and closes possibilities for every later jump.
• It's NP-complete. In 2000, Ryuhei Uehara and Shigeki Iwata proved that deciding whether a general peg solitaire position can be reduced to one peg is NP-complete. They encoded the clauses and variables of a SAT formula directly as patterns of pegs, so that a winning sequence of jumps exists exactly when the formula is satisfiable.
• So deciding even can-this-be-solved is equivalent to the whole NP-complete family — no shortcut is known that beats searching the move orders.

That is the punchline: the moment the board grows past what you can brute-force, you are staring at a genuine instance of the same problem behind P vs NP. The dead ends that ruin your run are not clumsiness — they are intractability made playable.

"Find a sequence of irreversible moves that reaches a goal state" is one of the most common shapes a real problem can take, and peg solitaire is its friendly face:

• Planning and scheduling: an AI planner that fires actions whose effects can't be undone is solving exactly this kind of reachability search.
• Motion and robotics: clearing pieces off a crowded board mirrors planning moves that block or free later ones.
• Combinatorial chemistry and games: many one-player elimination puzzles share the same "removing a piece changes everything downstream" structure.
• Teaching complexity: because the rules fit on a coaster, peg solitaire is a clear on-ramp to why searching move orders can be intractable.

Learn why peg solitaire is hard and you've met state-space search — the engine under SAT, AI planning and countless puzzles like the Fifteen puzzle.

Peg solitaire hides a beautiful secret: the same jumps that empty a wooden cross can be wired into the clauses of a logic formula, and through them into any problem in NP. Counting the pegs at the end stays instant; deciding whether a general board can be cleared to one peg is as hard as anything in computer science.

So the next time three pegs sit frozen apart with no legal jump between them, take comfort — you haven't played badly. You've simply run into P vs NP hiding under a row of wooden pegs, and on a big enough board there may be no clever way to know in advance.