Сапёр на JavaScript: заливка пустых клеток и первый ход без мины

Коротко

Сапёр на JavaScript — это массив клеток, в каждой из которых хранится мина, число мин у соседей, открыта ли клетка и стоит ли флажок, и несколько функций: расставить мины, открыть клетку, поставить флажок, сделать аккорд и проверить победу. Мины ставят тасованием Фишера — Йейтса и только после первого клика, вне этой клетки и её соседей, чтобы первый ход открыл область. Пустые клетки открывают заливкой через очередь, отмечая клетку в момент постановки в очередь, а не рекурсией. Игрок выиграл, когда открыты все клетки без мин, а флажки на победу не влияют.

Содержание

  1. Откуда взялся сапёр
  2. Из чего состоит игра в коде
  3. Поле, соседи и края
  4. Расстановка мин без повторов
  5. Заливка пустых клеток: очередь вместо рекурсии
  6. Первый ход без мины
  7. Флажки и аккорд
  8. Победа и проигрыш
  9. Код на JavaScript
  10. Проверка в Node.js
  11. Что показал прогон: шесть ловушек
  12. Где простой решатель застревает
  13. Что не подтвердилось
  14. Практический сценарий: сверить своего сапёра с контрольными числами
  15. Когда вам это не подойдёт

Откуда взялся сапёр

Кто придумал сапёра первым, источники спорят: по статье Wikipedia о жанре, TechRadar называет первой версией Microsoft Minesweeper 1990 года, а Eurogamer — игру Mined-Out (1983) Иэна Эндрю для ZX Spectrum. Там же упомянута игра Mines для SunOS 1987 года, автор — Том Андерсон.

Версия Microsoft, по той же статье, впервые вышла в 1990 году в Windows Entertainment Pack. Дальше источники расходятся в деталях. Статья о жанре пишет, что игру написали Роберт Доннер и Курт Джонсон, а Entertainment Pack входил в Windows 3.11. Статья Wikipedia о самой Microsoft Minesweeper уточняет: Курт Джонсон сделал игру для OS/2, Роберт Доннер перенёс её на Windows, а в стандартную установку она попала с Windows 3.1 в 1992 году. В Windows игра входила до Windows 8 (2012), после этого её стали скачивать из Microsoft Store.

Размеры полей тоже описаны по-разному. По статье о жанре, «Новичок» — обычно 8×8 или 9×9 с 10 минами, «Любитель» — 16×16 с 40 минами, «Профессионал» — 30×16 с 99 минами. Сайт minesweepergame.com пишет про «Новичка» 8×8 в Windows Minesweeper, а статья о Microsoft Minesweeper — что в версии для Windows 10 есть режимы Classic 8×8 и Easy 9×9. Мы берём 9×9/10, 16×16/40 и 30×16/99.

Правило первого хода в оригинале описывает minesweepergame.com: Windows Minesweeper делает первый клик безопасным, перенося мину в первую свободную клетку верхней строки, начиная с левого угла, а с Windows Vista первый клик гарантированно открывает область. Это правило мы проверим прогоном в разделе про первый ход. Головоломки на сетке, где всё поле видно сразу, мы разбирали в статье про головоломки на сетке; у сапёра поле скрыто, и дальше — только его код.

Из чего состоит игра в коде

Игра в нашем примере — объект поля и десяток небольших функций, каждая делает одну вещь. Отрисовки и мыши нет: ядро работает с данными, а браузерная обвязка рисует клетки и передаёт номер клетки, по которой щёлкнул игрок.

ЧастьФункцияЧто делает
ГенераторmakeRngслучайные числа из зерна
ПолеmakeBoard, neighbors, countAllклетки, соседи, цифры
МиныplaceMinesчестная расстановка без повторов
Открытиеrevealклетка или заливка пустой области
Первый ходfirstClickмины после клика, без мины рядом
ФлажкиtoggleFlag, mineCounterфлажок и счётчик мин
Аккордchordоткрыть соседей цифры
ИтогisWonвсе безопасные клетки открыты

Для ловушек в файле есть функции с ошибками: neighborsNoEdge, placeMinesSkip, revealNoMark, revealRecursive, wonAllMinesFlagged и wonFlagCount. Их нет в настоящей игре, они нужны, чтобы прогон показал, что именно ломается.

Поле, соседи и края

Поле — это одномерный массив клеток: номер клетки i = y × w + x, где x — столбец слева, y — строка сверху, оба с нуля, а w — ширина поля. Для каждой клетки хранятся четыре массива: mine (1 — мина), count (сколько мин среди соседей), open (открыта) и flag (стоит флажок).

Соседи клетки — до 8 клеток вокруг, и у каждого соседа проверяют, что он внутри поля по обеим осям:

для dy от −1 до 1, для dx от −1 до 1, кроме (0, 0):
  nx = x + dx, ny = y + dy
  если 0 ≤ nx < w и 0 ≤ ny < h: сосед — клетка ny × w + nx

Так у угловой клетки 3 соседа, у клетки на краю 5, в середине 8 — в разделе 1 вывода это видно на клетках (0,0), (4,0) и (4,4). Списки соседей считаются один раз на размер поля и потом только читаются.

Частая ошибка — искать соседей по номеру клетки как i − 1, i + 1, i − w − 1 и так далее, проверяя только, что номер не вышел за массив. Тогда у клетки в левом столбце «соседом слева» оказывается последняя клетка предыдущей строки: край поля заворачивается. Это ловушка 2, её цифры — ниже.

Расстановка мин без повторов

Мины честно расставляют так: собирают список клеток, куда мину ставить можно, перемешивают его тасованием Фишера — Йейтса и берут первые N клеток. Повторов не бывает, потому что каждая клетка в списке одна, а мин ставится ровно столько, сколько нужно.

pool = все клетки, кроме запрещённых
для k от 0 до N − 1:
  j = случайное от k до длины pool − 1
  обменять pool[k] и pool[j]
  в клетку pool[k] — мину

Перемешивать весь список не нужно: после k-го шага первые k клеток уже случайны. По Wikipedia, алгоритм описали Рональд Фишер и Фрэнк Йейтс в 1938 году, версию для компьютера предложил Ричард Дурстенфельд в 1964 году, и каждая перестановка у него получается с одинаковой вероятностью. В прогоне на 50000 полях 9×9/10 доля полей с миной в отдельной клетке была от 11,9 % до 12,8 % при ожидании 12,3 %: ни одна клетка не выделяется. Почему честная случайность важна и как устроен «мешок без повторов», мы разбирали в статье про случайность без несправедливости.

Случайность берётся не из Math.random, а из генератора с зерном на Math.imul — 32-битном умножении «как в C», по MDN. Одно и то же зерно даёт одно и то же поле, поэтому прогон повторяется байт в байт, а поле, на котором игрок нашёл ошибку, можно воспроизвести. Как одинаковые входные данные дают одинаковую игру, рассказано в статье про повтор прохождения.

Заливка пустых клеток: очередь вместо рекурсии

Если игрок открыл клетку, рядом с которой нет мин, игра сама открывает всех её соседей, а для пустых соседей — их соседей, пока область не упрётся в цифры. Делают это очередью: клетку отмечают открытой в момент, когда ставят в очередь, и больше её туда не ставят.

открыть(start):
  если мина → проигрыш
  очередь = [start], start открыта
  пока очередь не пуста:
    i = взять из начала очереди
    если у i цифра больше 0 → дальше не идём
    для каждого соседа j: если j закрыт и без флажка:
      j открыта (отметка «уже в очереди»), поставить j в конец очереди

Это поиск в ширину, тот же, с которого начинается поиск пути A*. По Wikipedia, перенос заливки из рекурсии в очередь или стек защищает от переполнения стека.

Почему не рекурсия

Рекурсивная заливка — функция, которая вызывает саму себя для каждого закрытого соседа, — короче, но каждый вложенный вызов ждёт, пока закончатся все следующие. Глубина вызовов растёт вместе с размером пустой области, а стек вызовов ограничен. По MDN, при переполнении Chrome и Safari бросают RangeError: Maximum call stack size exceeded, а Firefox — InternalError: too much recursion; предел зависит от движка, поэтому код, который полагается на «пока не падает», в другом браузере может упасть.

Чтобы вывод не зависел от предела стека, мы считаем глубину в функции recursionDepth: та же рекурсия, но вызовы хранятся в своём массиве. На стандартных полях она совпала с настоящей рекурсией на всех 3000 полях — это проверка, что счёт честный.

Почему отметка «уже в очереди»

Если отмечать клетку открытой не при постановке в очередь, а когда её достали, одна и та же клетка попадает в очередь от нескольких соседей. Насколько это дорого, зависит от второй проверки: пропускаем ли мы при выборке клетку, которая уже открыта. Обе ошибки — ловушки 3 и 4.

Первый ход без мины

Первый ход без мины делают так: мины не ставят при создании поля, а ставят после первого клика и не ставят в клетку клика и в её соседей. Тогда первая клетка пустая, рядом нет мин, и заливка сразу открывает область.

СпособЧто делаетЧто получает игрок
noneмины стоят заранееможно проиграть первым кликом
shiftмину из клетки клика переносят в первую свободную клетку верхней строкипервый клик безопасен, угол чаще заминирован
cellмины после клика, кроме этой клеткибезопасно, но часто открыта одна цифра
areaмины после клика, кроме клетки и 8 соседейбезопасно и всегда открыта область

Способ shift — то самое правило Windows Minesweeper из описания minesweepergame.com. Wikipedia о жанре пишет, что в одних вариантах игры безопасен только первый клик, а в других безопасны и соседние клетки. Что это меняет в цифрах — ловушка 5.

Флажки и аккорд

Флажок — пометка игрока «здесь мина»: его ставят и снимают на закрытой клетке, а клетку с флажком нельзя открыть случайным кликом. Игре флажки нужны только для счётчика мин: мин всего минус флажков. По Wikipedia, счётчик может уйти в минус, если флажков больше, чем мин; в разделе 5 вывода он показывает −11.

Аккорд — открытие всех соседей цифры одним действием, если флажков вокруг ровно столько, сколько показывает цифра. По Wikipedia, в некоторых версиях его делают, нажимая обе кнопки мыши.

аккорд(i):
  если i закрыта или цифра 0 → ничего
  если флажков вокруг ≠ цифре → ничего
  иначе открыть каждого закрытого соседа без флажка

Если флажок стоит неверно, аккорд открывает мину и игрок проигрывает — это честно, так работает и правило. В разделе 5 вывода цифра 2 в клетке (1,1): без флажков и с одним флажком аккорд не срабатывает, с двумя верными открывает 2 клетки, а с одним неверным — мину.

Победа и проигрыш

Игрок проиграл, если открыл клетку с миной, и выиграл, когда открыты все клетки без мин: открыто клеток = всего клеток − мин. Так правило описывает Wikipedia, а в Microsoft Minesweeper, по статье о ней, после победы оставшиеся мины помечаются флажками автоматически. Флажки в проверке победы не участвуют: игрок, который их вообще не ставит, тоже может выиграть. Чем опасна проверка «по флажкам» — ловушка 6.

Код на JavaScript

Пример — два файла: minesweeper.mjs с ядром игры и test.mjs, который прогоняет опыты по разделам и печатает итог. Нужен Node.js 24 и папка с этими файлами; запуск — node test.mjs. Случайность только из генератора с зерном, поэтому вывод повторяется байт в байт.

// minesweeper.mjs — ядро сапёра на чистом JavaScript; случайность только из генератора с зерном
// Линейный конгруэнтный генератор: одно и то же зерно даёт одно и то же поле
export function makeRng(seed) {
  let s = seed >>> 0;
  const next = () => {
    s = (Math.imul(s, 1664525) + 1013904223) >>> 0;
    return s / 4294967296;
  };
  return { next, int: (n) => Math.floor(next() * n) };
}

// Поле: клетка i = y * w + x; у каждой клетки мина, число соседей-мин, открыта ли, стоит ли флажок
export function makeBoard(w, h, mines) {
  const n = w * h;
  return { w, h, n, mines, mine: new Uint8Array(n), count: new Uint8Array(n),
    open: new Uint8Array(n), flag: new Uint8Array(n), opened: 0, flags: 0, lost: false, near: nearTable(w, h) };
}

// Соседи с проверкой краёв: у угловой клетки 3 соседа, у клетки на краю 5, в середине 8.
// Списки считаем один раз на размер поля и храним в b.near
const tables = new Map();
function nearTable(w, h) {
  const key = w + "x" + h;
  if (tables.has(key)) return tables.get(key);
  const table = [];
  for (let k = 0; k < w * h; k++) {
    const x = k % w;
    const y = Math.floor(k / w);
    const list = [];
    for (let dy = -1; dy <= 1; dy++) {
      for (let dx = -1; dx <= 1; dx++) {
        const nx = x + dx;
        const ny = y + dy;
        if ((dx !== 0 || dy !== 0) && nx >= 0 && nx < w && ny >= 0 && ny < h) list.push(ny * w + nx);
      }
    }
    table.push(list);
  }
  tables.set(key, table);
  return table;
}
export const neighbors = (b, i) => b.near[i];

// Ошибка для ловушки: соседи через i ± 1 и i ± w без проверки столбца — край строки «заворачивается»
export function neighborsNoEdge(b, i) {
  const list = [];
  for (const d of [-b.w - 1, -b.w, -b.w + 1, -1, 1, b.w - 1, b.w, b.w + 1]) {
    if (i + d >= 0 && i + d < b.n) list.push(i + d);
  }
  return list;
}

export function countAll(b, near = neighbors) {
  for (let i = 0; i < b.n; i++) {
    let c = 0;
    for (const j of near(b, i)) c += b.mine[j];
    b.count[i] = c;
  }
}

// Честная расстановка: тасование Фишера — Йейтса по разрешённым клеткам, берём первые mines
export function placeMines(b, rng, banned = []) {
  const ban = new Uint8Array(b.n);
  for (const i of banned) ban[i] = 1;
  const pool = [];
  for (let i = 0; i < b.n; i++) if (!ban[i]) pool.push(i);
  if (pool.length < b.mines) throw new Error("мин больше, чем свободных клеток");
  b.mine.fill(0);
  for (let k = 0; k < b.mines; k++) {
    const j = k + rng.int(pool.length - k);
    const v = pool[k];
    pool[k] = pool[j];
    pool[j] = v;
    b.mine[pool[k]] = 1;
  }
  countAll(b);
}

// Ошибка для ловушки: mines раз берём случайную клетку, а если там уже мина — пропускаем
export function placeMinesSkip(b, rng) {
  b.mine.fill(0);
  for (let k = 0; k < b.mines; k++) b.mine[rng.int(b.n)] = 1;
  countAll(b);
  return b.mine.reduce((s, v) => s + v, 0);
}

// Первый ход. none — мины стоят заранее, защиты нет; shift — мину из клетки клика переносим
// в первую свободную клетку верхней строки слева; cell — мины ставим после клика, кроме этой клетки;
// area — мины ставим после клика, кроме этой клетки и её соседей
export function firstClick(b, i, mode, rng) {
  if (mode === "cell") placeMines(b, rng, [i]);
  if (mode === "area") placeMines(b, rng, [i, ...neighbors(b, i)]);
  if (mode === "shift" && b.mine[i]) {
    let j = 0;
    while (b.mine[j] || j === i) j += 1;
    b.mine[i] = 0;
    b.mine[j] = 1;
    countAll(b);
  }
  return reveal(b, i);
}

// Открыть клетку. Пустую (0 мин рядом) заливаем очередью: клетку отмечаем, когда ставим в очередь
export function reveal(b, start) {
  const res = { opened: 0, work: 0, longestQueue: 0 };
  if (b.open[start] || b.flag[start] || b.lost) return res;
  if (b.mine[start]) { b.lost = true; return res; }
  const queue = [start];
  b.open[start] = 1;
  for (let head = 0; head < queue.length; head++) {
    const i = queue[head];
    res.work += 1;
    res.opened += 1;
    if (b.count[i] !== 0) continue;
    for (const j of neighbors(b, i)) {
      if (b.open[j] || b.flag[j]) continue;
      b.open[j] = 1;
      queue.push(j);
    }
    res.longestQueue = Math.max(res.longestQueue, queue.length - head - 1);
  }
  b.opened += res.opened;
  return res;
}

// Ошибка для ловушки: клетку отмечаем только при выборке из очереди — одна клетка попадает туда много раз.
// skipOpened — полумера: повторную выборку уже открытой клетки пропускаем, но в очередь она всё равно попадает.
// limit — предохранитель: после стольких выборок останавливаемся, иначе очередь не помещается в память
export function revealNoMark(b, start, opts = {}) {
  const limit = opts.limit || 1000000;
  const res = { opened: 0, work: 0, stopped: false };
  if (b.mine[start]) { b.lost = true; return res; }
  const queue = [start];
  for (let head = 0; head < queue.length; head++) {
    const i = queue[head];
    res.work += 1;
    if (res.work > limit) { res.stopped = true; break; }
    if (b.open[i] && opts.skipOpened) continue;
    if (!b.open[i]) { b.open[i] = 1; res.opened += 1; }
    if (b.count[i] !== 0) continue;
    for (const j of neighbors(b, i)) if (!b.open[j] && !b.flag[j]) queue.push(j);
  }
  b.opened += res.opened;
  return res;
}

// Рекурсивная заливка: функция вызывает сама себя для каждого закрытого соседа пустой клетки
export function revealRecursive(b, i, depth = 1, res = { opened: 0, deepest: 0 }) {
  b.open[i] = 1;
  res.opened += 1;
  res.deepest = Math.max(res.deepest, depth);
  if (b.count[i] === 0) {
    for (const j of neighbors(b, i)) {
      if (!b.open[j] && !b.flag[j]) revealRecursive(b, j, depth + 1, res);
    }
  }
  return res;
}

// Та же рекурсия, но вызовы лежат в своём массиве: глубину считаем, а стек движка не растёт
export function recursionDepth(b, start) {
  const frames = [{ i: start, k: 0 }];
  b.open[start] = 1;
  let opened = 1;
  let deepest = 1;
  while (frames.length > 0) {
    const top = frames[frames.length - 1];
    const near = neighbors(b, top.i);
    if (b.count[top.i] !== 0 || top.k >= near.length) { frames.pop(); continue; }
    const j = near[top.k];
    top.k += 1;
    if (b.open[j] || b.flag[j]) continue;
    b.open[j] = 1;
    opened += 1;
    frames.push({ i: j, k: 0 });
    deepest = Math.max(deepest, frames.length);
  }
  return { opened, deepest };
}

// Флажок: на закрытой клетке ставим или снимаем; limit — не больше флажков, чем мин
export function toggleFlag(b, i, limit = false) {
  if (b.open[i]) return false;
  if (!b.flag[i] && limit && b.flags >= b.mines) return false;
  b.flag[i] ^= 1;
  b.flags += b.flag[i] ? 1 : -1;
  return true;
}

// Счётчик мин для игрока: мин минус флажков, может уйти в минус
export const mineCounter = (b) => b.mines - b.flags;

// Аккорд: если флажков вокруг открытой цифры столько же, сколько мин, открыть остальных соседей
export function chord(b, i) {
  if (!b.open[i] || b.count[i] === 0) return { done: false, opened: 0 };
  const near = neighbors(b, i);
  const flagged = near.filter((j) => b.flag[j]).length;
  if (flagged !== b.count[i]) return { done: false, opened: 0 };
  let opened = 0;
  for (const j of near) if (!b.open[j] && !b.flag[j]) opened += reveal(b, j).opened;
  return { done: true, opened };
}

// Победа: открыты все клетки без мин; флажки на это не влияют
export const isWon = (b) => !b.lost && b.opened === b.n - b.mines;

// Ошибки для ловушки: «все мины под флажками» и «флажков столько же, сколько мин»
export function wonAllMinesFlagged(b) {
  for (let i = 0; i < b.n; i++) if (b.mine[i] && !b.flag[i]) return false;
  return true;
}
export const wonFlagCount = (b) => b.flags === b.mines;

// Простой решатель на двух правилах. Правило 1: закрытых соседей столько, сколько мин, — все они мины.
// Правило 2: флажков вокруг столько, сколько мин, — остальные соседи безопасны. Это не полный решатель
export function solveSimple(b) {
  let changed = true;
  let steps = 0;
  while (changed && !b.lost) {
    changed = false;
    for (let i = 0; i < b.n; i++) {
      if (!b.open[i] || b.count[i] === 0) continue;
      const near = neighbors(b, i);
      const closed = near.filter((j) => !b.open[j]);
      const flagged = closed.filter((j) => b.flag[j]).length;
      if (closed.length === flagged) continue;
      if (closed.length === b.count[i]) {
        for (const j of closed) if (!b.flag[j]) toggleFlag(b, j);
        changed = true;
        steps += 1;
      } else if (flagged === b.count[i]) {
        chord(b, i);
        changed = true;
        steps += 1;
      }
    }
  }
  return { won: isWon(b), stuck: !isWon(b) && !b.lost, steps };
}

// Поле из строк: * — мина, . — пусто; для собранных вручную примеров
export function parseBoard(lines) {
  const b = makeBoard(lines[0].length, lines.length, 0);
  lines.join("").split("").forEach((ch, i) => { if (ch === "*") { b.mine[i] = 1; b.mines += 1; } });
  countAll(b);
  return b;
}

// Поле для вывода: закрытая — #, флажок — F, мина после проигрыша — *, открытая — цифра или точка
export function show(b, all = false) {
  const rows = [];
  for (let y = 0; y < b.h; y++) {
    let s = "";
    for (let x = 0; x < b.w; x++) {
      const i = y * b.w + x;
      if (b.flag[i] && !all) s += "F";
      else if (!b.open[i] && !all) s += "#";
      else if (b.mine[i]) s += "*";
      else s += b.count[i] === 0 ? "." : String(b.count[i]);
    }
    rows.push(s);
  }
  return rows;
}
// test.mjs — node test.mjs; вывод детерминирован: зёрна заданы, Math.random не используется
import { makeRng, makeBoard, neighbors, neighborsNoEdge, countAll, placeMines, placeMinesSkip, firstClick,
  reveal, revealNoMark, revealRecursive, recursionDepth, toggleFlag, mineCounter, chord, isWon,
  wonAllMinesFlagged, wonFlagCount, solveSimple, parseBoard, show } from "./minesweeper.mjs";

const out = [];
const say = (s) => out.push(s);
const num = (x, d) => x.toFixed(d).replace(".", ",");
const pct = (a, b) => num((a / b) * 100, 1) + " %";
const SIZES = [[9, 9, 10], [16, 16, 40], [30, 16, 99]];
const label = ([w, h, m]) => w + "×" + h + "/" + m;
const FIELDS = 1000;
const GAMES = 10000;
const SEED = 79;
const board = (b, all) => { for (const line of show(b, all)) say("  " + line); };
const cell = (b, i) => "(" + (i % b.w) + "," + Math.floor(i / b.w) + ")";
const fresh = (size, seed, mode = "area") => {
  const rng = makeRng(seed);
  const b = makeBoard(size[0], size[1], size[2]);
  const click = rng.int(b.n);
  if (mode === "none" || mode === "shift") placeMines(b, rng);
  return { b, rng, click };
};

say("# 0. Модель");
say("поля " + SIZES.map(label).join(", ") + " (ширина×высота/мин); клетка (x,y) с нуля, x — столбец слева, y — строка сверху");
say("генератор с зерном на Math.imul; на каждый размер " + FIELDS + " полей, в опытах с первым ходом " + GAMES + " партий");

say("");
say("# 1. Поле 9×9/10, зерно " + SEED + ", первый клик (4,4), мины ставятся после клика");
{
  const rng = makeRng(SEED);
  const b = makeBoard(9, 9, 10);
  const r = firstClick(b, 4 * 9 + 4, "area", rng);
  board(b, true);
  say("после клика открыто клеток: " + r.opened);
  board(b);
  say("соседей у (0,0): " + neighbors(b, 0).length + ", у (4,0): " + neighbors(b, 4).length + ", у (4,4): " + neighbors(b, 40).length);
  const c = makeBoard(9, 9, 10);
  c.mine.set(b.mine);
  countAll(c, neighborsNoEdge);
  let wrong = 0;
  for (let i = 0; i < b.n; i++) if (!b.mine[i] && c.count[i] !== b.count[i]) wrong += 1;
  say("соседи без проверки края: неверных цифр на этом поле " + wrong + "; у (0,1) " + c.count[9] + " вместо " + b.count[9]);
}
for (const size of SIZES) {
  let bad = 0;
  let wrong = 0;
  const rng = makeRng(1000 + size[0]);
  for (let f = 0; f < FIELDS; f++) {
    const b = makeBoard(...size);
    placeMines(b, rng);
    const c = makeBoard(...size);
    c.mine.set(b.mine);
    countAll(c, neighborsNoEdge);
    let w = 0;
    for (let i = 0; i < b.n; i++) if (!b.mine[i] && c.count[i] !== b.count[i]) w += 1;
    wrong += w;
    if (w > 0) bad += 1;
  }
  say(label(size) + ": без проверки края полей с неверными цифрами " + bad + " из " + FIELDS + ", неверных цифр в среднем " + num(wrong / FIELDS, 1));
}

say("");
say("# 2. Расстановка мин: «пропустить занятую» против тасования Фишера — Йейтса");
for (const size of SIZES) {
  const rng = makeRng(2000 + size[0]);
  let short = 0;
  let sum = 0;
  let least = Infinity;
  let exact = 0;
  for (let f = 0; f < FIELDS; f++) {
    const b = makeBoard(...size);
    const got = placeMinesSkip(b, rng);
    if (got < size[2]) short += 1;
    sum += got;
    least = Math.min(least, got);
    const fy = makeBoard(...size);
    placeMines(fy, rng);
    if (fy.mine.reduce((s, v) => s + v, 0) === size[2]) exact += 1;
  }
  say(label(size) + ": с пропуском полей с недостачей " + short + " из " + FIELDS + ", мин в среднем " + num(sum / FIELDS, 1) +
    ", меньше всего " + least + "; Фишер — Йейтс: ровно " + size[2] + " мин на " + exact + " полях");
}
{
  const rng = makeRng(2100);
  const hits = new Array(81).fill(0);
  for (let g = 0; g < GAMES * 5; g++) {
    const b = makeBoard(9, 9, 10);
    placeMines(b, rng);
    for (let i = 0; i < 81; i++) hits[i] += b.mine[i];
  }
  const share = hits.map((v) => v / (GAMES * 5));
  say("Фишер — Йейтс, 9×9/10, " + GAMES * 5 + " полей: мина в клетке от " + pct(Math.min(...share), 1) + " до " +
    pct(Math.max(...share), 1) + " полей, ожидание " + pct(10, 81));
}

say("");
say("# 3. Заливка пустых клеток: первый клик, мины после клика вне клетки и соседей");
const copyOf = (b) => { const c = makeBoard(b.w, b.h, b.mines); c.mine.set(b.mine); c.count.set(b.count); return c; };
for (const size of [...SIZES, [100, 100, 100], [300, 300, 90]]) {
  const big = size[0] >= 100;
  const fields = big ? 5 : FIELDS;
  const t = { work: 0, half: 0, none: 0, worstHalf: 0, worstNone: 0, stopped: 0, deepest: 0, longest: 0, same: 0 };
  for (let f = 0; f < fields; f++) {
    const a = fresh(size, 3000 + f * 7 + size[0]);
    const r = firstClick(a.b, a.click, "area", a.rng);
    const h = revealNoMark(copyOf(a.b), a.click, { skipOpened: true });
    const n = revealNoMark(copyOf(a.b), a.click);
    t.work += r.work;
    t.half += h.work;
    t.worstHalf = Math.max(t.worstHalf, h.work / r.work);
    if (n.stopped) t.stopped += 1;
    else { t.none += n.work; t.worstNone = Math.max(t.worstNone, n.work / r.work); }
    t.longest = Math.max(t.longest, r.longestQueue);
    const d = recursionDepth(copyOf(a.b), a.click);
    t.deepest = Math.max(t.deepest, d.deepest);
    if (!big) {
      const rr = revealRecursive(copyOf(a.b), a.click);
      if (rr.deepest === d.deepest && rr.opened === d.opened && d.opened === r.opened) t.same += 1;
    }
  }
  say(label(size) + ", полей " + fields + ": открыто за клик в среднем " + num(t.work / fields, 1) + ", глубина рекурсии до " + t.deepest +
    " вызовов, очередь до " + t.longest + " клеток");
  say("  без отметки «в очереди», но с пропуском открытых: выборок в " + num(t.half / t.work, 2) + " раза больше (хуже всего в " + num(t.worstHalf, 2) + ")");
  say("  без отметки и без пропуска: " + (t.stopped === fields ? "предохранитель на 1000000 выборок сработал на всех полях" :
    "выборок в " + num(t.none / t.work, 2) + " раза больше (хуже всего в " + num(t.worstNone, 2) + "), предохранитель сработал " + t.stopped + " раз"));
  if (!big) say("  настоящая рекурсия и счёт глубины без стека совпали на " + t.same + " полях из " + fields);
}

say("");
say("# 4. Первый ход: " + GAMES + " партий на размер, клик в случайную клетку");
for (const size of SIZES) {
  const n = size[0] * size[1];
  const res = {};
  for (const mode of ["none", "shift", "cell", "area"]) {
    const t = { lost: 0, corner: 0, single: 0, opened: 0 };
    for (let g = 0; g < GAMES; g++) {
      const { b, rng, click } = fresh(size, 4000 + g, mode);
      const r = firstClick(b, click, mode, rng);
      if (b.lost) t.lost += 1;
      else { t.opened += r.opened; if (r.opened === 1) t.single += 1; }
      t.corner += b.mine[0];
    }
    res[mode] = t;
  }
  const expect = size[2] / n;
  say(label(size) + ": без защиты проигрыш на первом клике " + res.none.lost + " из " + GAMES + " (" + pct(res.none.lost, GAMES) + ", ожидание " + pct(size[2], n) + ")");
  say("  перенос мины в первую свободную клетку верхней строки: мина в (0,0) в " + pct(res.shift.corner, GAMES) +
    " партий — в " + num(res.shift.corner / GAMES / expect, 2) + " раза чаще средней клетки (" + pct(size[2], n) + "); без защиты — " + pct(res.none.corner, GAMES));
  say("  защищена только клетка: открылась одна цифра в " + res.cell.single + " из " + GAMES + " (" + pct(res.cell.single, GAMES) +
    "), открыто в среднем " + num(res.cell.opened / GAMES, 1) + "; мина в (0,0) в " + pct(res.cell.corner, GAMES));
  say("  защищены клетка и соседи: одна цифра " + res.area.single + " из " + GAMES + ", открыто в среднем " + num(res.area.opened / GAMES, 1));
}

say("");
say("# 5. Флажки и аккорд на поле 6×4");
{
  const lines = ["*.....", "..*...", "......", "....*."];
  const b = parseBoard(lines);
  board(b, true);
  reveal(b, 6 * 3 + 0);
  say("клик (0,3): открыто " + b.opened);
  board(b);
  const one = 6 * 1 + 1;
  say("аккорд на (1,1) с цифрой " + b.count[one] + " без флажков: открыто " + chord(b, one).opened);
  toggleFlag(b, 0);
  say("флажок на (0,0), аккорд на (1,1): " + (chord(b, one).done ? "сработал" : "не сработал") + " — флажков 1, а цифра " + b.count[one]);
  toggleFlag(b, 6 * 1 + 2);
  const r = chord(b, one);
  say("флажок на (2,1), аккорд на (1,1): открыто " + r.opened + ", проигрыш " + (b.lost ? "да" : "нет"));
  board(b);
  const c = parseBoard(lines);
  reveal(c, 6 * 3 + 0);
  toggleFlag(c, 0);
  toggleFlag(c, 1);
  const w = chord(c, one);
  say("флажки на (0,0) и (1,0), второй ошибочный: аккорд на (1,1) " + (w.done ? "сработал" : "не сработал") + ", проигрыш " + (c.lost ? "да" : "нет"));
  const d = parseBoard(lines);
  reveal(d, 6 * 3 + 0);
  for (let i = 0; i < d.n; i++) toggleFlag(d, i);
  say("флажки на всех " + d.flags + " закрытых клетках: счётчик мин " + mineCounter(d));
}

say("");
say("# 6. Победа: открыть все безопасные клетки, а не пометить все мины");
{
  const rng = makeRng(SEED);
  const b = makeBoard(9, 9, 10);
  firstClick(b, 40, "area", rng);
  for (let i = 0; i < b.n; i++) toggleFlag(b, i);
  say("флажки на всех закрытых клетках без лимита: флажков " + b.flags + ", «все мины под флажками» — " + (wonAllMinesFlagged(b) ? "победа" : "нет") +
    ", «флажков столько, сколько мин» — " + (wonFlagCount(b) ? "победа" : "нет") + ", правильная проверка — " + (isWon(b) ? "победа" : "нет"));
  const c = makeBoard(9, 9, 10);
  firstClick(c, 40, "area", makeRng(SEED));
  for (let i = 0; i < c.n && c.flags < c.mines; i++) toggleFlag(c, i, true);
  say("10 флажков по порядку с лимитом: «флажков столько, сколько мин» — " + (wonFlagCount(c) ? "победа" : "нет") +
    ", «все мины под флажками» — " + (wonAllMinesFlagged(c) ? "победа" : "нет") + ", правильная проверка — " + (isWon(c) ? "победа" : "нет"));
  const d = makeBoard(9, 9, 10);
  firstClick(d, 40, "area", makeRng(SEED));
  for (let i = 0; i < d.n; i++) if (!d.mine[i]) reveal(d, i);
  say("открыты все безопасные клетки, флажков 0: «все мины под флажками» — " + (wonAllMinesFlagged(d) ? "победа" : "нет") +
    ", правильная проверка — " + (isWon(d) ? "победа" : "нет"));
}
for (const size of SIZES) {
  let fake = 0;
  for (let f = 0; f < FIELDS; f++) {
    const { b, rng, click } = fresh(size, 6000 + f);
    firstClick(b, click, "area", rng);
    for (let i = 0; i < b.n; i++) toggleFlag(b, i);
    if (wonAllMinesFlagged(b) && !isWon(b)) fake += 1;
  }
  say(label(size) + ": «победа» флажками везде на " + fake + " полях из " + FIELDS);
}

say("");
say("# 7. Простой решатель на двух правилах после первого клика");
for (const size of SIZES) {
  const line = [];
  for (const mode of ["area", "cell"]) {
    let won = 0;
    let stuck = 0;
    let lost = 0;
    for (let f = 0; f < FIELDS; f++) {
      const { b, rng, click } = fresh(size, 7000 + f, mode);
      firstClick(b, click, mode, rng);
      const r = solveSimple(b);
      if (r.won) won += 1;
      if (r.stuck) stuck += 1;
      if (b.lost) lost += 1;
    }
    line.push((mode === "area" ? "клетка и соседи" : "только клетка") + ": решено без угадывания " + won + ", застрял " + stuck + " (" + pct(stuck, FIELDS) + "), подрывов " + lost);
  }
  say(label(size) + ", полей " + FIELDS + " — " + line.join("; "));
}

process.stdout.write(out.join("\n") + "\n");

Проверка в Node.js

Ниже — полный вывод node test.mjs на Node.js 24.22.1; мы запускали его 25 раз подряд, вывод совпадал байт в байт, а один прогон шёл около 2,5 секунды. Клетки записаны как (x,y): столбец, потом строка, с нуля. В поле с открытыми минами * — мина, точка — пустая клетка, цифра — число мин рядом; в поле глазами игрока # — закрытая клетка, F — флажок.

Вывод прогона:

# 0. Модель
поля 9×9/10, 16×16/40, 30×16/99 (ширина×высота/мин); клетка (x,y) с нуля, x — столбец слева, y — строка сверху
генератор с зерном на Math.imul; на каждый размер 1000 полей, в опытах с первым ходом 10000 партий

# 1. Поле 9×9/10, зерно 79, первый клик (4,4), мины ставятся после клика
  1*1..1*3*
  222..12*2
  1*1...122
  111....1*
  ......122
  .....13*2
  .....1**2
  .111.1221
  .1*1.....
после клика открыто клеток: 61
  ##1..1###
  ##2..12##
  ##1...12#
  111....1#
  ......12#
  .....13##
  .....1###
  .111.1221
  .1#1.....
соседей у (0,0): 3, у (4,0): 5, у (4,4): 8
соседи без проверки края: неверных цифр на этом поле 6; у (0,1) 3 вместо 2
9×9/10: без проверки края полей с неверными цифрами 936 из 1000, неверных цифр в среднем 4,6
16×16/40: без проверки края полей с неверными цифрами 998 из 1000, неверных цифр в среднем 10,2
30×16/99: без проверки края полей с неверными цифрами 1000 из 1000, неверных цифр в среднем 12,0

# 2. Расстановка мин: «пропустить занятую» против тасования Фишера — Йейтса
9×9/10: с пропуском полей с недостачей 438 из 1000, мин в среднем 9,5, меньше всего 7; Фишер — Йейтс: ровно 10 мин на 1000 полях
16×16/40: с пропуском полей с недостачей 959 из 1000, мин в среднем 37,1, меньше всего 30; Фишер — Йейтс: ровно 40 мин на 1000 полях
30×16/99: с пропуском полей с недостачей 1000 из 1000, мин в среднем 89,4, меньше всего 80; Фишер — Йейтс: ровно 99 мин на 1000 полях
Фишер — Йейтс, 9×9/10, 50000 полей: мина в клетке от 11,9 % до 12,8 % полей, ожидание 12,3 %

# 3. Заливка пустых клеток: первый клик, мины после клика вне клетки и соседей
9×9/10, полей 1000: открыто за клик в среднем 37,0, глубина рекурсии до 41 вызовов, очередь до 23 клеток
  без отметки «в очереди», но с пропуском открытых: выборок в 1,99 раза больше (хуже всего в 2,81)
  без отметки и без пропуска: выборок в 10,47 раза больше (хуже всего в 163,72), предохранитель сработал 0 раз
  настоящая рекурсия и счёт глубины без стека совпали на 1000 полях из 1000
16×16/40, полей 1000: открыто за клик в среднем 48,9, глубина рекурсии до 74 вызовов, очередь до 34 клеток
  без отметки «в очереди», но с пропуском открытых: выборок в 1,93 раза больше (хуже всего в 2,67)
  без отметки и без пропуска: выборок в 42,61 раза больше (хуже всего в 2937,07), предохранитель сработал 1 раз
  настоящая рекурсия и счёт глубины без стека совпали на 1000 полях из 1000
30×16/99, полей 1000: открыто за клик в среднем 32,7, глубина рекурсии до 49 вызовов, очередь до 23 клеток
  без отметки «в очереди», но с пропуском открытых: выборок в 1,75 раза больше (хуже всего в 2,76)
  без отметки и без пропуска: выборок в 13,65 раза больше (хуже всего в 813,76), предохранитель сработал 0 раз
  настоящая рекурсия и счёт глубины без стека совпали на 1000 полях из 1000
100×100/100, полей 5: открыто за клик в среднем 9888,8, глубина рекурсии до 9016 вызовов, очередь до 347 клеток
  без отметки «в очереди», но с пропуском открытых: выборок в 3,67 раза больше (хуже всего в 3,67)
  без отметки и без пропуска: предохранитель на 1000000 выборок сработал на всех полях
300×300/90, полей 5: открыто за клик в среднем 89908,6, глубина рекурсии до 89067 вызовов, очередь до 1166 клеток
  без отметки «в очереди», но с пропуском открытых: выборок в 3,95 раза больше (хуже всего в 3,95)
  без отметки и без пропуска: предохранитель на 1000000 выборок сработал на всех полях

# 4. Первый ход: 10000 партий на размер, клик в случайную клетку
9×9/10: без защиты проигрыш на первом клике 1241 из 10000 (12,4 %, ожидание 12,3 %)
  перенос мины в первую свободную клетку верхней строки: мина в (0,0) в 23,1 % партий — в 1,87 раза чаще средней клетки (12,3 %); без защиты — 12,6 %
  защищена только клетка: открылась одна цифра в 5916 из 10000 (59,2 %), открыто в среднем 15,3; мина в (0,0) в 12,4 %
  защищены клетка и соседи: одна цифра 0 из 10000, открыто в среднем 37,3
16×16/40: без защиты проигрыш на первом клике 1563 из 10000 (15,6 %, ожидание 15,6 %)
  перенос мины в первую свободную клетку верхней строки: мина в (0,0) в 28,8 % партий — в 1,84 раза чаще средней клетки (15,6 %); без защиты — 15,8 %
  защищена только клетка: открылась одна цифра в 7009 из 10000 (70,1 %), открыто в среднем 15,0; мина в (0,0) в 15,6 %
  защищены клетка и соседи: одна цифра 0 из 10000, открыто в среднем 49,1
30×16/99: без защиты проигрыш на первом клике 2081 из 10000 (20,8 %, ожидание 20,6 %)
  перенос мины в первую свободную клетку верхней строки: мина в (0,0) в 36,9 % партий — в 1,79 раза чаще средней клетки (20,6 %); без защиты — 20,2 %
  защищена только клетка: открылась одна цифра в 8187 из 10000 (81,9 %), открыто в среднем 6,4; мина в (0,0) в 20,6 %
  защищены клетка и соседи: одна цифра 0 из 10000, открыто в среднем 33,4

# 5. Флажки и аккорд на поле 6×4
  *211..
  12*1..
  .11211
  ...1*1
клик (0,3): открыто 10
  ######
  12####
  .112##
  ...1##
аккорд на (1,1) с цифрой 2 без флажков: открыто 0
флажок на (0,0), аккорд на (1,1): не сработал — флажков 1, а цифра 2
флажок на (2,1), аккорд на (1,1): открыто 2, проигрыш нет
  F21###
  12F###
  .112##
  ...1##
флажки на (0,0) и (1,0), второй ошибочный: аккорд на (1,1) сработал, проигрыш да
флажки на всех 14 закрытых клетках: счётчик мин -11

# 6. Победа: открыть все безопасные клетки, а не пометить все мины
флажки на всех закрытых клетках без лимита: флажков 20, «все мины под флажками» — победа, «флажков столько, сколько мин» — нет, правильная проверка — нет
10 флажков по порядку с лимитом: «флажков столько, сколько мин» — победа, «все мины под флажками» — нет, правильная проверка — нет
открыты все безопасные клетки, флажков 0: «все мины под флажками» — нет, правильная проверка — победа
9×9/10: «победа» флажками везде на 1000 полях из 1000
16×16/40: «победа» флажками везде на 1000 полях из 1000
30×16/99: «победа» флажками везде на 1000 полях из 1000

# 7. Простой решатель на двух правилах после первого клика
9×9/10, полей 1000 — клетка и соседи: решено без угадывания 551, застрял 449 (44,9 %), подрывов 0; только клетка: решено без угадывания 247, застрял 753 (75,3 %), подрывов 0
16×16/40, полей 1000 — клетка и соседи: решено без угадывания 229, застрял 771 (77,1 %), подрывов 0; только клетка: решено без угадывания 74, застрял 926 (92,6 %), подрывов 0
30×16/99, полей 1000 — клетка и соседи: решено без угадывания 2, застрял 998 (99,8 %), подрывов 0; только клетка: решено без угадывания 1, застрял 999 (99,9 %), подрывов 0

Что показал прогон: шесть ловушек

Шесть ловушек воспроизвелись прогоном: ловушка 1 — раздел 2 вывода, ловушка 2 — раздел 1, ловушки 3 и 4 — раздел 3, ловушка 5 — раздел 4, ловушка 6 — разделы 5 и 6.

Ловушка 1: «случайная клетка, а если занята — пропустить»

Если N раз брать случайную клетку и ставить туда мину, а занятую пропускать, мин на поле получается меньше N. В разделе 2 вывода недостача была на 438 полях 9×9/10 из 1000, на 959 полях 16×16/40 и на всех 1000 полях 30×16/99. На поле эксперта в среднем стояло 89,4 мины вместо 99, а меньше всего — 80. Игрок этого не видит, но счётчик мин на эксперте врёт в среднем на 9,6 мины, а в худшем случае — на 19, и рассуждать по нему нельзя. Тасование Фишера — Йейтса на тех же полях поставило ровно столько мин, сколько нужно, на всех 3000 полях.

Ловушка 2: соседи без проверки края

Если искать соседей через i ± 1 и i ± w без проверки столбца, у клеток в левом и правом столбцах неверные цифры. В разделе 1 вывода на поле с зерном 79 таких цифр 6, и у клетки (0,1) стоит 3 вместо 2: игра посчитала мину с правого края предыдущей строки. На 1000 полях ошибка была на 936 полях 9×9, на 998 полях 16×16 и на всех 1000 полях 30×16 — в среднем 4,6, 10,2 и 12,0 неверных цифр на поле.

Ловушка 3: рекурсивная заливка на большом поле

Рекурсия на стандартных полях не опасна, но на большом поле с малым числом мин глубина вызовов растёт вместе с областью. В разделе 3 вывода самая глубокая рекурсия на 1000 полях была 41 вызов на 9×9, 74 — на 16×16 и 49 — на 30×16. На поле 100×100 со 100 минами первый клик открыл в среднем 9888,8 клетки, и глубина дошла до 9016 вызовов; на поле 300×300 с 90 минами — 89908,6 клетки и 89067 вызовов. Очередь в тех же заливках держала не больше 347 и 1166 клеток.

Отдельно, вне test.mjs, мы запустили настоящую рекурсию на одном поле каждого из этих размеров в Node.js 24.22.1 с настройками по умолчанию: оба раза она упала с RangeError: Maximum call stack size exceeded. Это число не стоит переносить на другие среды — по MDN, предел стека зависит от движка, — поэтому в прогоне мы считаем глубину, а не ловим падение.

Ловушка 4: заливка без отметки «уже в очереди»

Если отмечать клетку открытой только тогда, когда её достали из очереди, одна клетка попадает в очередь много раз, и работы становится в разы больше. Есть два варианта этой ошибки.

  • С пропуском уже открытых при выборке. Повторы только лежат в очереди: выборок в 1,99 раза больше на 9×9, в 1,93 — на 16×16 и в 1,75 — на 30×16, хуже всего в 2,81 раза. На полях 100×100 и 300×300 — в 3,67 и 3,95 раза.
  • Без пропуска. Каждая повторная выборка пустой клетки снова ставит в очередь её закрытых соседей, и очередь растёт лавиной: в среднем в 10,47 раза больше работы на 9×9, в 42,61 — на 16×16 и в 13,65 — на 30×16. Хуже всего — в 2937,07 раза на одном поле 16×16, а ещё на одном поле 16×16 сработал наш предохранитель на 1000000 выборок. На полях 100×100 и 300×300 он сработал на всех полях: без предохранителя очередь не помещалась в память — в первой версии кода, ещё без предохранителя, прогон упал с RangeError: Invalid array length: очередь не поместилась в массив.

Игрок увидит то же поле, что и при правильной заливке, — ошибка заметна только по времени клика, поэтому её легко пропустить.

Ловушка 5: первый ход

Без защиты первый клик проигрывает примерно в доле мин на поле: в разделе 4 вывода 12,4 % партий на 9×9/10, 15,6 % — на 16×16/40 и 20,8 % — на 30×16/99, при ожидании 12,3 %, 15,6 % и 20,6 %. Каждый пятый эксперт заканчивался, не начавшись.

Перенос мины в первую свободную клетку верхней строки делает первый клик безопасным, но угол (0,0) заминирован в 23,1 % партий на 9×9, в 28,8 % — на 16×16 и в 36,9 % — на 30×16: в 1,87, 1,84 и 1,79 раза чаще средней клетки. Игрок, который знает правило, может этим пользоваться.

Защита только клетки клика не даёт проиграть, но в 59,2 % партий на 9×9, в 70,1 % — на 16×16 и в 81,9 % — на 30×16 первый клик открывал одну цифру: игроку не за что зацепиться, и следующий клик — угадывание. Защита клетки и соседей ни разу не открыла одну цифру и открывала в среднем 37,3, 49,1 и 33,4 клетки.

Ловушка 6: победа по флажкам

Проверка «все мины под флажками» объявляет победу, если поставить флажок на каждую закрытую клетку: в разделе 6 вывода это случилось на всех 1000 полях каждого размера, хотя ни одной новой клетки игрок не открыл. Проверка «флажков столько же, сколько мин» ломается ещё проще: 10 флажков подряд с первых закрытых клеток дали «победу» на поле 9×9, даже с лимитом флажков. А игрок, который открыл все безопасные клетки без единого флажка, по проверке флажками не выигрывает. Правильная проверка — открыты все клетки без мин — во всех трёх случаях ответила верно.

Где простой решатель застревает

Простой решатель на двух правилах после первого клика доводит до конца без угадывания 551 поле 9×9/10 из 1000, 229 полей 16×16/40 и только 2 поля 30×16/99. Правила такие:

правило 1: закрытых соседей у цифры столько же, сколько цифра → все они мины, ставим флажки
правило 2: флажков у цифры столько же, сколько цифра → остальные соседи безопасны, аккорд
повторять, пока хоть одно правило сработало

Это не полный решатель: он смотрит на одну цифру за раз и не сравнивает соседние цифры между собой, поэтому часть полей, где он застрял, человек или решатель посильнее дорешает без угадывания. Число «застрял» — верхняя граница полей с угадыванием, а не точная доля. Заметно другое: при защите только клетки решатель застревал чаще — 75,3 % полей 9×9 против 44,9 % и 92,6 % полей 16×16 против 77,1 %. Подрывов не было ни разу: оба правила никогда не ошибаются. По Wikipedia, когда мины занимают больше 25 % клеток, решение поля начинает требовать угадывания; на нашем эксперте их 20,6 %, и простому решателю этого уже хватает, чтобы застрять почти всегда.

Что не подтвердилось

Четыре ожидания прогон не подтвердил или подтвердил слабее, чем мы думали:

  • «Рекурсивная заливка переполнит стек на обычном поле». Нет: на стандартных полях глубина была не больше 74 вызовов, и настоящая рекурсия прошла на всех 3000 полях. Опасна она только на больших полях с малым числом мин — от 100×100 со 100 минами в нашем запуске.
  • «Пропуск занятой клетки на маленьком поле незаметен». Нет: на 9×9 с 10 минами недостача была на 438 полях из 1000, почти на каждом втором.
  • «Без отметки „уже в очереди“ работа вырастет не больше чем в 8 раз — по числу соседей». Это верно только для варианта с пропуском открытых (не больше 3,95 раза в среднем). Без пропуска рост не ограничен соседями: до 2937,07 раза на поле 16×16.
  • «Перенос мины при первом клике меняет долю проигрышей в начале игры». Проигрышей первым кликом при переносе нет, а перекос оказался в другом месте — в углу (0,0), который заминирован в 1,79–1,87 раза чаще. Насколько это меняет дальнейшую игру, мы не измеряли.

Практический сценарий: сверить своего сапёра с контрольными числами

Задача: вы написали сапёра — свои имена функций, может быть, двумерный массив вместо одномерного — и хотите проверить, что в нём нет шести ошибок. Входные данные — наш генератор с зерном, размеры полей из раздела 0 и способ первого хода area.

  1. Первый клик. Зерно 79, поле 9×9/10, клик (4,4): поле должно совпасть с разделом 1 вывода, и открыто должно быть 61 клетка. Если поле другое, у вас другой порядок вызовов генератора; сверьте сначала его.
  2. Края. У (0,0) — 3 соседа, у (4,0) — 5, у (4,4) — 8; у клетки (0,1) цифра 2. Если 3 — у вас соседи без проверки края.
  3. Мины. Посчитайте мины после расстановки на 1000 полях 30×16/99: на каждом должно быть ровно 99.
  4. Заливка. Посчитайте, сколько раз клетки достаются из очереди: на поле из пункта 1 должно быть 61 — столько же, сколько открыто. Больше — нет отметки «уже в очереди».
  5. Аккорд. Поле 6×4 из раздела 5: клик (0,3) открывает 10 клеток, флажки (0,0) и (2,1), аккорд на (1,1) открывает 2 клетки без проигрыша.
  6. Победа. Поставьте флажок на каждую закрытую клетку — победы быть не должно. Откройте все клетки без мин без единого флажка — победа должна быть.

Проверяемый итог: все шесть пунктов совпали с выводом прогона. Если совпали пункты 1–5, а победа объявляется без открытых клеток, проверка победы смотрит на флажки.

Когда вам это не подойдёт

Наше ядро рассчитано на прямоугольное поле с квадратными клетками и одним игроком; вот где его мало:

  • Поля без угадывания. Если вы хотите гарантировать, что каждое поле решается логикой, простого решателя не хватит: нужен полный, а по Wikipedia, проверка согласованности поля сапёра — NP-полная задача (доказательство Кея, 2000). Один из способов — генерировать поле и проверять его решателем, пока не получится подходящее; на эксперте простой решатель из нашего прогона пропустил бы 2 поля из 1000.
  • Шестиугольные и треугольные клетки. У них другое число соседей; функцию neighbors придётся переписать, а остальное ядро останется.
  • Очень большие и бесконечные поля. Массив на всё поле и заливка всей области за один клик перестают работать; поле делят на куски и создают их, когда игрок до них дошёл.
  • Сапёр для нескольких игроков. Если поле считает браузер игрока, расстановку мин можно прочитать из памяти; поле нужно хранить там, где игрок его не видит.
  • Сенсорный экран. Правой кнопки мыши нет, поэтому флажок ставят отдельным режимом или долгим нажатием — по статье о Microsoft Minesweeper, режим флажков в версии для Windows 10 нужен именно для сенсорного экрана.

Как устроена другая головоломка на сетке, где всё видно сразу и нужна отмена хода, — в статье про Sokoban на JavaScript; где поле само перестраивается после хода — в match-3 на JavaScript. А зачем заливке без отметки понадобился предохранитель на число выборок, объяснено в статье про циклы и ветвления.

Мы разрабатываем J2DRU — браузерный 2D игровой движок, где логика собирается из событий, условий и действий, а проект можно углублять на TypeScript. Движок в разработке и публично пока не открыт, заявку можно оставить на странице раннего доступа (подача заявки не гарантирует приглашение).

Источники (проверено: 12.11.2026, все страницы открываются с HTTP 200): Wikipedia — Minesweeper (video game) (Mined-Out 1983 и спор TechRadar и Eurogamer о первой версии; Mines для SunOS 1987; Microsoft 1990, Windows Entertainment Pack; Доннер и Джонсон; в Windows до Windows 8 (2012); размеры 8×8 или 9×9/10, 16×16/40, 30×16/99; безопасный первый клик в одних вариантах и безопасные соседи в других; аккорд; счётчик мин может быть отрицательным; победа — открыть все клетки без мин; NP-полнота, Кей 2000; порог 25 % мин); Wikipedia — Microsoft Minesweeper (Джонсон для OS/2, Доннер перенёс на Windows; Entertainment Pack 1 в 1990, Windows 3.1 в 1992; оставшиеся мины помечаются флажками после победы; режимы Windows 10, в том числе Classic 8×8 и Easy 9×9; режим флажков для сенсорного экрана); minesweepergame.com — The First Click (Windows Minesweeper переносит мину в первую свободную клетку верхней строки от левого угла; с Windows Vista первый клик открывает область; «Новичок» 8×8); Wikipedia — Fisher–Yates shuffle (Фишер и Йейтс, 1938; Дурстенфельд, 1964; все перестановки равновероятны); Wikipedia — Flood fill (заливка очередью или стеком вместо рекурсии защищает от переполнения стека); MDN — InternalError: too much recursion (RangeError в Chrome и Safari, InternalError в Firefox); MDN — Math.imul() (32-битное умножение «как в C»). Поля, зёрна, решатель и все числа прогона — наш пример и наш прогон в Node.js 24.22.1.

Читайте также:

Частые вопросы

Как сделать, чтобы первый клик в сапёре не попадал на мину?

Ставить мины не при создании поля, а после первого клика и не ставить их в эту клетку и в её 8 соседей. Тогда первая клетка пустая, рядом с ней нет мин, и игра сразу открывает область. В нашем прогоне на 10000 партиях каждого размера такой первый ход ни разу не открыл одну цифру, а защита одной только клетки открывала одну цифру в 59,2 % партий на поле 9×9 и в 81,9 % — на поле 30×16.

Почему рекурсивная заливка в сапёре может упасть?

Каждый рекурсивный вызов занимает место в стеке вызовов, а он ограничен. На стандартных полях глубина небольшая: в нашем прогоне до 74 вызовов. Но на поле 300×300 с 90 минами рекурсия ушла на 89067 вызовов в глубину, и Node.js 24 остановил её ошибкой RangeError: Maximum call stack size exceeded. Предел зависит от браузера и движка, поэтому надёжнее заливка очередью: она хранит клетки в обычном массиве.

Как честно расставить мины на поле?

Собрать список всех клеток, куда можно ставить мину, перемешать его тасованием Фишера — Йейтса и взять первые N клеток. Повторов не будет, и каждая клетка получает мину с одинаковой вероятностью. Способ «взять случайную клетку, а если там уже мина — пропустить» ставит меньше мин: на поле 30×16 с 99 минами в нашем прогоне на всех 1000 полях мин было меньше, в среднем 89,4.

Когда игрок в сапёре выиграл?

Когда открыты все клетки без мин. Флажки на победу не влияют: игрок может вообще их не ставить. Проверка «все мины под флажками» ломается: если поставить флажок на каждую закрытую клетку, она объявляет победу — в нашем прогоне на всех 1000 полях каждого размера.