이 글을 분류한다면 아마 예고로 들어갈 것 같네요. 이제 와서 새로운 전략을 발견할 줄은 몰랐습니다. 지뢰찾기 사이트에는 힌트라는 기능이 있는데 해를 찾고 확률을 계산해준다고 합니다. 어떤 플레이어가 올린 사진을 보니 지뢰가 있을 확률이 0으로 계산된 곳이 있었습니다.

지뢰찾기 매크로를 만들어본 입장에서 저 부분은 찾기 어려운 해입니다. 전 일정 부분까지는 계산으로 찾고 계산이 통하지 않을 때는 경우의 수를 트리로 그리는 식으로 구현을 했습니다. '계산으로 찾는 일정 부분'이 바로 까다로운 부분인데 다항시간 알고리즘으로는 모든 해를 계산하는 것이 사실상 불가능하기 때문입니다. (사실상인 이유는 P=NP의 가능성이 열려있기 때문입니다.) 매크로를 만들면서 나름 휴리스틱 알고리즘도 넣었었는데 아마 전혀 도움은 안 되었을 것입니다.

이 문제를 풀어보니 새로운 것이 보였습니다. 하단에 미지의 칸 다섯 개와 깃발 하나로 둘러싸인 3이 보이실 겁니다. 얘가 핵심입니다. 모든 커플링을 연결하고 있는 친구이지요. 근처 숫자들을 이용하더라도 겹치는 칸의 수도 적고, 완전히 포함되는 경우도 없기 때문에 추론을 하기가 어렵습니다. 하지만 주변의 숫자로 추론한 칸들을 합치면 3 주변의 칸을 모두 포함하는 것이 가능합니다. 자세한 건 이미지를 활용해야 설명이 될 것 같기 때문에 미루어두겠습니다. 또, 이 전략을 이해하려면 그 이전 단계의 전략들도 알아야 하기 때문에 쓸 내용이 많습니다.

그나저나 힌트 기능은 이번에 처음 발견을 했네요. 다음에 활용을 해봐야겠습니다.

지뢰찾기 사이트가 궁금하신 분은 여기로 가보십쇼.