Introduction

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.

Try the Jumps

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">Click a <b>peg</b>, then click the empty hole two steps away in a straight line — the peg jumped over is removed. Reduce the board to <b>one</b> surviving peg. Counting pegs at the end is instant; finding the right order of jumps is the hard part.</p>
<div id="board" class="board"></div>
<div class="status" id="status">Pegs left: 6. Pick a peg to jump.</div>
<div class="btns">
  <button id="solve" type="button">Auto-solve</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Peg solitaire "reachability": from a start position, is there a sequence of jumps that leaves a single peg? Checking a finished game is a quick count; deciding it in general is NP-complete (Uehara & Iwata, 2000). Here we search the move tree with backtracking on a small board where order matters.
const ROWS = 5, COLS = 5;
// Layout: 1 = hole that can hold a peg, 0 = not part of the board (gap).
// A small plus-ish shape with 7 holes; 6 start with a peg, 1 starts empty.
const SHAPE = [
  [0,0,1,0,0],
  [0,0,1,0,0],
  [1,1,1,1,1],
  [0,0,0,0,0],
  [0,0,0,0,0],
];
// START pegs: 'P' peg, '.' empty hole, ' ' not a cell.
const START = [
  "  P  ",
  "  P  ",
  "PP.PP",
  "     ",
  "     ",
];
const idx = (r,c) => r*COLS+c;
let pegs;      // Set of idx that hold a peg
let holes;     // Set of idx that are valid holes
let sel = null;

function load(){
  pegs = new Set(); holes = new Set();
  for(let r=0;r<ROWS;r++)for(let c=0;c<COLS;c++){
    if(SHAPE[r][c]===1){ holes.add(idx(r,c)); if(START[r][c]==='P') pegs.add(idx(r,c)); }
  }
  sel = null;
}
// The 4 orthogonal jump directions (over one peg, into an empty hole 2 away).
const DIRS = [[-1,0],[1,0],[0,-1],[0,1]];
function jumpsFrom(state, fromIdx){
  const r = Math.floor(fromIdx/COLS), c = fromIdx%COLS, out = [];
  for(const [dr,dc] of DIRS){
    const mr=r+dr, mc=c+dc, tr=r+2*dr, tc=c+2*dc;
    if(tr<0||tr>=ROWS||tc<0||tc>=COLS) continue;
    const mid=idx(mr,mc), tgt=idx(tr,tc);
    if(holes.has(tgt) && state.has(fromIdx) && state.has(mid) && !state.has(tgt))
      out.push({mid, tgt});
  }
  return out;
}
function allJumps(state){
  const list=[];
  for(const p of state) for(const j of jumpsFrom(state,p)) list.push({from:p, ...j});
  return list;
}
function applyJump(state, j){
  const s=new Set(state); s.delete(j.from); s.delete(j.mid); s.add(j.tgt); return s;
}
// Backtracking search: can `state` be reduced to a single peg? Returns the move sequence if so. This is the brute-force the NP-completeness is about.
function solve(state){
  if(state.size===1) return [];
  for(const j of allJumps(state)){
    const seq = solve(applyJump(state, j));
    if(seq) return [j, ...seq];
  }
  return null;
}

function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }
function render(){
  const b=document.getElementById('board'); b.innerHTML='';
  const targets = sel!==null ? new Set(jumpsFrom(pegs,sel).map(j=>j.tgt)) : new Set();
  for(let r=0;r<ROWS;r++)for(let c=0;c<COLS;c++){
    const d=document.createElement('div'); const i=idx(r,c);
    if(!holes.has(i)){ d.className='cell gap'; b.appendChild(d); continue; }
    d.className='cell hole'+(targets.has(i)?' target':'');
    if(pegs.has(i)){
      const p=document.createElement('div'); p.className='peg'+(sel===i?' sel':'');
      p.addEventListener('click',e=>{ e.stopPropagation(); sel=(sel===i?null:i); render(); });
      d.appendChild(p);
    } else if(targets.has(i)){
      d.addEventListener('click',()=>doJump(sel,i));
    }
    b.appendChild(d);
  }
}
function doJump(from, tgt){
  const j = jumpsFrom(pegs,from).find(x=>x.tgt===tgt); if(!j) return;
  pegs.delete(from); pegs.delete(j.mid); pegs.add(tgt); sel=null; render();
  const n=pegs.size;
  if(n===1) setStatus('✓ One peg left — solved!','ok');
  else if(allJumps(pegs).length===0) setStatus(fmt('✗ Dead end: %n% pegs and no legal jump. Reset and reorder.', { n: n }),'bad');
  else setStatus(fmt('Pegs left: %n%. Keep jumping.', { n: n }),'');
}
document.getElementById('solve').addEventListener('click',()=>{
  const seq=solve(pegs);
  if(!seq){ setStatus('No solution from here — already a dead end.','bad'); return; }
  for(const j of seq){ pegs.delete(j.from); pegs.delete(j.mid); pegs.add(j.tgt); }
  sel=null; render();
  setStatus(fmt('Solved by search in %length% jumps — down to one peg.', { length: seq.length }),'ok');
  console.log('Solution jumps (from->tgt):', seq.map(j=>j.from+'->'+j.tgt).join(', '));
});
document.getElementById('reset').addEventListener('click',()=>{ load(); render(); setStatus(fmt('Pegs left: %size%. Pick a peg to jump.', { size: pegs.size }),''); });
load(); render();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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

Conclusion

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.

Share this article

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

Comments

Loading comments...

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