찍지 않아도 끝까지 풀리는 지뢰찾기 판

2026년 10월 26일 · 게임 디자인

지뢰찾기에서 가장 허탈한 순간은 거의 다 풀었는데 남은 두 칸 중 하나가 지뢰인 판이다. 어느 칸이 안전한지 알려 주는 숫자가 어디에도 없어서, 확률 반반으로 찍는 수밖에 없다. 우리 지뢰찾기는 첫 칸만 안전하게 해 주고 나머지 지뢰는 무작위로 깔았기 때문에 이런 판이 끝에 남을 수 있었다. 판이 클수록 자주 생겼고 고급(16×16)에서 특히 그랬다. 그래서 추리만으로 끝까지 풀리는 판만 나오게 바꿨다.

방법은 세 가지를 따져 봤다. 하나는 지뢰를 깔고 풀어 보다가 막히는 곳이 생기면 그곳의 지뢰를 옮겨서 풀리게 고치는 방식이다. 지뢰찾기 퍼즐 모음으로 알려진 Simon Tatham 의 구현이 이 방식이다. 풀리는 판을 만들 수 있지만 코드가 길고, 지뢰가 어느 한쪽에 몰리는 버릇이 생길 수 있다. 두 번째는 플레이어가 찍을 때 판을 몰래 바꿔서 봐주는 방식인데, 판이 누르는 대로 달라져서 모두가 같은 판을 받는 오늘의 도전과 맞지 않는다. 세 번째가 이 글에서 고른 다시 깔기다. 무작위로 지뢰를 깔고, 풀이기로 시작 칸부터 추리만으로 풀어 본다. 막히면 지뢰를 새로 깔고, 풀리는 판이 나올 때까지 반복한다. 판이 커 봐야 16×16 이라 여러 번 다시 깔아도 충분히 빠르다. 가장 단순해서 고르기로 했다.

이 방식은 풀이기가 사람이 하는 것과 똑같이 추리해야 한다는 조건이 붙는다. 풀이기가 쓰는 추리는 쉬운 것부터 세 단계다. 첫째는 숫자 하나만 보는 것이다. 숫자 둘레의 지뢰를 이미 다 찾았으면 나머지 닫힌 칸은 모두 안전하고, 닫힌 칸 수가 남은 지뢰 수와 같으면 모두 지뢰다. 둘째는 두 숫자를 비교하는 것이다. A 숫자의 닫힌 칸이 B 숫자의 닫힌 칸 안에 다 들어 있으면, B 에만 있는 칸에는 지뢰가 B 에서 A 를 뺀 개수만큼 있다. 사람들이 1-2-1 무늬라고 부르는 상황이 이것이다.

셋째는 경계 전체를 한꺼번에 따지는 것이다. 숫자와 닿은 닫힌 칸들을 서로 이어진 묶음으로 나누고, 묶음마다 숫자와 맞는 지뢰 배치를 모두 세어 본다. 이런 방식을 되추적(백트래킹)이라 부른다. 판 전체에 남은 지뢰 수까지 맞는 조합만 남기고, 모든 경우에 안전하거나 모든 경우에 지뢰인 칸을 찾는다. 경계 밖의 칸도 이 계산으로 판단한다. 배치를 세는 데 20만 번이라는 한도를 두고, 넘으면 그 판은 풀이기가 감당하지 못하는 판으로 보고 버린다.

오늘의 도전은 날짜로 정한 시드 난수를 쓴다. 풀리지 않으면 같은 시드 난수로 이어서 다시 깔기 때문에, 모두가 같은 판에 도착한다. 같은 시드로 두 번 만들어 같은 판이 나오는지 확인했다.

// plant mines, then try to solve from the start cell using logic only
for (let tries = 1; tries <= 300; tries++) {
  const board = plant(startCell, rng);
  if (solvable(board, startCell)) return { board, tries, ok: true };
}
return { board: lastBoard, tries: 300, ok: false }; // give up and use the last one

설명을 위해 줄인 예시다. 풀이 함수는 게임 등록 객체에 함수로 바로 두었다. 숫자 값으로 두면 홈 목록용 catalog.js 에 섞여 들어가는데, 함수는 이 파일에서 빠진다는 빌드 규칙을 이용했다.

시험은 Node 로 난이도마다 300판씩 만들어 봤다. 다시 깐 횟수는 평균 1.1회(초급)에서 1.6회(중급)였고 최대 7회였다. 판 하나를 만드는 데 2ms 미만이 걸렸고, 300번 넘게 다시 깔아도 안 되는 실패는 한 번도 없었다. 풀이기가 맞는지는 작은 판(5×5 등) 150개에서 모든 지뢰 배치를 하나하나 따져 보는 완전한 풀이와 판정을 비교했고, 150개 모두 같았다.

게임 안내에는 "모든 판은 찍지 않고 추리만으로 풀 수 있습니다"라는 한 줄을 넣었다.

참고한 문서

• Simon Tatham's Portable Puzzle Collection: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/
• Wikipedia, Minesweeper (video game): https://en.wikipedia.org/wiki/Minesweeper_(video_game))
• Wikipedia, Backtracking: https://en.wikipedia.org/wiki/Backtracking

이 글과 관련된 게임

지뢰찾기숫자 힌트로 숨은 지뢰를 피해 모든 칸을 여세요. 해 보기