찍기 없는 지뢰찾기

보통 지뢰찾기가 찍게 만드는 이유

클래식 지뢰찾기에서는 지뢰를 무작위로 놓습니다. 무작위 배치는 실력이 아무리 좋아도 풀 수 없는 상황을 자주 만듭니다. 닫힌 칸 두 개, 그 사이에 지뢰 하나, 그리고 한쪽에 닿은 숫자는 모두 다른 쪽에도 똑같이 닿아 있는 상황. 어느 쪽을 열어도 질 확률이 50%입니다. 플레이어들은 이걸 50대50, 혹은 그냥 「찍기」라고 부릅니다.

얼마나 자주 일어날까요? 저희는 첫 클릭만 안전하게 한 평범한 무작위 판을 만들어 솔버로 풀어 봤습니다. 우연히 찍지 않고 풀린 판은 초급 약 91%, 중급 약 65%, 고급은 고작 약 14%였습니다. 즉 고급에서는 무작위 판 대부분이 적어도 한 번은 찍기를 요구하고, 그것도 몇 분 동안 신중하게 풀어 온 막바지에 나오는 일이 많습니다.

• 닫힌 칸
• ✓열어도 안전
• ⚑반드시 지뢰
• ⚑깃발 꽂은 지뢰
• 1여기를 보세요
• ?찍을 수밖에 없는 칸

판은 이렇게 만들어집니다

여러분이 클릭하기 전까지 지뢰는 하나도 놓이지 않습니다. 첫 칸과 그 주변 8칸에는 지뢰를 두지 않고, 나머지 지뢰를 무작위로 흩뿌립니다. 그런 다음 솔버가 여러분의 칸에서 출발해 신중한 플레이어처럼 판을 풀어 나갑니다. 솔버는 지뢰가 실제로 어디 있는지 절대 들여다보지 않습니다.

솔버가 어떤 칸도 안전하다거나 지뢰라고 증명할 수 없는 상황에 이르면, 그 판은 찍기가 필요하다는 뜻입니다. 그때 판을 통째로 버리지 않고, 아직 결정되지 않은 칸들 사이에서 지뢰 하나를 옮깁니다. 솔버가 이미 추리를 끝낸 칸의 지뢰는 건드리지 않습니다. 그리고 솔버가 이어서 풀어 나갑니다. 이미 열린 칸과 이미 증명된 지뢰는 그대로 두므로, 지금까지 추리한 내용은 모두 여전히 참입니다. 솔버가 안전한 칸을 모두 열 수 있을 때까지 이 과정을 반복합니다.

마지막으로 완성된 판을 여러분의 첫 클릭부터 처음부터 한 번 더 풀어서, 정말로 찍기가 필요 없는지 확인합니다. 그제야 판이 화면에 나옵니다. 이 모든 과정은 몇 밀리초면 끝납니다. 노트북에서 고급 판도 평균 약 3ms(about 3 ms)라서, 클릭하는 순간 판이 나타납니다.

솔버가 알아도 되는 것

솔버는 여러분이 볼 수 있는 것만 씁니다. 열린 칸의 숫자, 이미 지뢰로 증명한 칸, 그리고 전체 지뢰 수입니다. 추리는 세 단계로 이뤄집니다. 첫째, 숫자 하나. 지뢰를 다 찾은 숫자라면 나머지 주변 칸은 안전하고, 닫힌 주변 칸 수가 부족한 지뢰 수와 같다면 그 칸은 모두 지뢰입니다. 둘째, 숫자 둘. 겹치는 두 숫자를 비교하는 방법으로, 1-2-1이나 1-2-2-1 같은 패턴이 이렇게 풀립니다. 셋째, 전수 조사. 경계의 이어진 구간마다 가능한 지뢰 배치를 모두 시험하고 남은 지뢰 수와도 맞춰 본 뒤, 모든 배치에서 성립하는 결론만 받아들입니다.

이 마지막 단계는 빈틈이 없습니다. 여기서도 어떤 칸도 정하지 못한다면, 그 상황은 정말로 찍기가 필요한 것입니다. 솔버가 틀린 결론을 내리지 않도록 자동 테스트로도 확인합니다. 무작위로 만든 작은 상황 400개에서 솔버의 답을, 가능한 지뢰 배치를 모두 따져 보는 무차별 대입 검사와 칸 하나하나 비교했고, 매번 모두 일치했습니다.

실력은 그대로, 동전 던지기만 없다

찍기가 없다는 건 쉽다는 뜻이 아닙니다. 판은 클래식 크기와 지뢰 수를 그대로 유지하고, 솔버는 깊은 추리도 쓸 수 있어서, 다음 수를 찾으려면 여러 숫자를 비교하거나 남은 지뢰를 세야 할 수도 있습니다. 달라지는 건 패배의 의미입니다. 지는 이유는 언제나 숫자를 잘못 읽었거나 손이 미끄러졌기 때문이지, 운이 나빠서가 아닙니다. 그리고 50대50처럼 보이는 상황이 있어도 실제로는 아닙니다. 판 어딘가에 아직 찾지 못한 추리가 기다리고 있습니다.

자주 묻는 질문