Коротко
Сапёр на JavaScript — это массив клеток, в каждой из которых хранится мина, число мин у соседей, открыта ли клетка и стоит ли флажок, и несколько функций: расставить мины, открыть клетку, поставить флажок, сделать аккорд и проверить победу. Мины ставят тасованием Фишера — Йейтса и только после первого клика, вне этой клетки и её соседей, чтобы первый ход открыл область. Пустые клетки открывают заливкой через очередь, отмечая клетку в момент постановки в очередь, а не рекурсией. Игрок выиграл, когда открыты все клетки без мин, а флажки на победу не влияют.
Содержание
- Откуда взялся сапёр
- Из чего состоит игра в коде
- Поле, соседи и края
- Расстановка мин без повторов
- Заливка пустых клеток: очередь вместо рекурсии
- Первый ход без мины
- Флажки и аккорд
- Победа и проигрыш
- Код на JavaScript
- Проверка в Node.js
- Что показал прогон: шесть ловушек
- Где простой решатель застревает
- Что не подтвердилось
- Практический сценарий: сверить своего сапёра с контрольными числами
- Когда вам это не подойдёт
Откуда взялся сапёр
Кто придумал сапёра первым, источники спорят: по статье 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.
- Первый клик. Зерно 79, поле 9×9/10, клик (4,4): поле должно совпасть с разделом 1 вывода, и открыто должно быть 61 клетка. Если поле другое, у вас другой порядок вызовов генератора; сверьте сначала его.
- Края. У (0,0) — 3 соседа, у (4,0) — 5, у (4,4) — 8; у клетки (0,1) цифра 2. Если 3 — у вас соседи без проверки края.
- Мины. Посчитайте мины после расстановки на 1000 полях 30×16/99: на каждом должно быть ровно 99.
- Заливка. Посчитайте, сколько раз клетки достаются из очереди: на поле из пункта 1 должно быть 61 — столько же, сколько открыто. Больше — нет отметки «уже в очереди».
- Аккорд. Поле 6×4 из раздела 5: клик (0,3) открывает 10 клеток, флажки (0,0) и (2,1), аккорд на (1,1) открывает 2 клетки без проигрыша.
- Победа. Поставьте флажок на каждую закрытую клетку — победы быть не должно. Откройте все клетки без мин без единого флажка — победа должна быть.
Проверяемый итог: все шесть пунктов совпали с выводом прогона. Если совпали пункты 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.
Читайте также:
- Match-3 на JavaScript: поиск совпадений, падение и каскады
- Sokoban на JavaScript: ящики, цели и отмена хода
- Случайность без несправедливости: мешок без повторов, взвешенный выбор и гарантия редкого
- Поиск пути A* на тайловой сетке: от поиска в ширину до рабочего кода на JavaScript
- Циклы и ветвления в игровой логике: ранний выход и бюджет кадра