The Nine-Dart Leg Is a Coin-Change Problem

Nobody has ever finished a leg of 501 in eight darts. The record is nine, and I wanted to know why nine was the floor before I trusted it — not because a commentator said so, but because I could count it.

Here is the reframing that made it obvious. A dartboard isn’t twenty numbers, it’s a purse of coins. Every single throw is worth one of 62 values: the singles 1–20, their doubles and trebles, plus the 25 and the bullseye at 50. You owe 501. The question “what’s the fewest darts to go out?” is exactly “what’s the fewest coins to make 501?” — the coin-change problem, which Richard Bellman’s people were already grinding through by the mid-1950s under the name dynamic programming.

The trick is you don’t guess a sequence. You compute the answer for every score from 1 up to 501, and each new answer reuses the ones below it. To score s, try each coin v, and you can’t do better than one dart plus whatever it cost to make s − v.

const board: number[] = [];
for (let n = 1; n <= 20; n++) board.push(n, 2 * n, 3 * n);
board.push(25, 50);

const darts = Array(502).fill(Infinity);
darts[0] = 0;
for (let score = 1; score <= 501; score++)
  for (const v of board)
    if (v <= score) darts[score] = Math.min(darts[score], darts[score - v] + 1);

console.log(darts[501]); // 9

The same table, filled the same direction, in OCaml:

let board =
  let b = ref [25; 50] in
  for n = 1 to 20 do b := n :: (2*n) :: (3*n) :: !b done; !b

let () =
  let darts = Array.make 502 max_int in
  darts.(0) <- 0;
  for score = 1 to 501 do
    List.iter (fun v ->
      if v <= score && darts.(score - v) + 1 < darts.(score)
      then darts.(score) <- darts.(score - v) + 1) board
  done;
  Printf.printf "%d\n" darts.(501)  (* 9 *)

Both print 9. Eight treble-20s is 480; the ninth dart has to cover the last 21 in a single value, and 21 exists as treble-7. There’s your floor.

What the DP quietly ignores is the rule that actually ruined my evening: you must finish on a double. Add that and the last coin isn’t free to choose — the 501-to-2 path has to land on an even leaf. That constraint is the whole checkout tree I lost every leg to, and it’s tomorrow’s array.