지뢰찾기는 컴퓨터에 들어 있는 덤 게임으로 알려져 있지만, 수학과 컴퓨터 연구에서도 화제가 된 적이 있어요. 키워드는 ‘NP 완전’이에요.
지뢰찾기는 NP 완전
2000년쯤 수학자 리처드 케이가, 지뢰찾기와 관련된 다음 문제가 ‘NP 완전’이라 불리는 어려운 문제의 한 부류라는 것을 보였다고 알려져 있어요.
숫자가 적힌 보드가 있을 때, 그 숫자들과 모순되지 않는 지뢰 배치가 하나라도 있는지 없는지.
평소에 플레이하면서 생각하는 ‘이 칸은 안전할까’라는 문제도 이 문제와 깊이 이어져 있어요.
NP 완전이란
NP 완전을 쉽게 말하면 다음과 같은 성질을 가진 문제예요.
- 답이 맞는지 확인하기는 쉬워요: 지뢰 배치를 하나 보여 주면 모든 숫자와 맞는지 금방 확인할 수 있어요.
- 답을 찾기는 힘들어요(라고 여겨져요): 보드가 커지면 배치 후보가 갑자기 늘어나요. 지금 알려진 어떤 방법으로도 어떤 보드든 빨리 답을 찾아내는 방법은 발견되지 않았어요.
게다가 NP 완전 문제끼리는 서로 바꿔 말할 수 있다는 것이 알려져 있어요. 어느 하나라도 어떤 경우에든 빨리 푸는 방법이 발견되면, 다른 NP 완전 문제도 모두 빨리 풀 수 있게 돼요. 이 ‘빨리 푸는 방법이 있는지’는 ‘P≠NP 추측’이라는 유명한 미해결 문제로, 100만 달러의 현상금이 걸린 문제 중 하나로 알려져 있어요.
배치의 수는 금방 커져요
배치를 조사하기가 힘든 것은 후보의 수가 아주 커지기 때문이에요.
- 9×7 보드에 지뢰 8개를 놓는 방법은 63칸에서 8칸을 고르는 조합의 수로, 약 39억 가지예요.
- 26×15 보드에 지뢰 75개를 놓는 방법은 390칸에서 75칸을 고르는 조합의 수로, 80자리를 넘는 수가 돼요.
물론 실제로 플레이할 때는 전부 조사할 필요가 없어요. 숫자와 이어지지 않은 칸은 한데 묶어 생각할 수 있고, 대부분의 장면은 숫자 한두 개만 봐도 정해져요. 그래도 숫자가 복잡하게 얽힌 장면에서는 확실한 답을 내기가 힘들 때가 있어요.
앱은 사람의 추리로 풀 수 있는 보드만 골라요
앱 「지뢰찾기」는 보드를 만들 때, 사람이 쓰는 다음 세 가지 규칙만으로 처음부터 끝까지 풀 수 있는지를 확인해요.
- 숫자 하나로 알 수 있는 것
- 두 숫자를 조합해서 알 수 있는 것
- 보드 전체의 남은 지뢰 수로 알 수 있는 것
어느 규칙이든 살펴보는 범위가 작아서 빨리 조사할 수 있어요. 이 세 가지로 풀리지 않는 보드는 지뢰를 옮겨서 다시 만들어요. 그래서 플레이하는 사람도 모든 배치를 조사하는 무거운 생각을 하지 않아도 반드시 끝까지 풀 수 있어요.
이 사이트의 글 속에서 할 수 있는 보드도 같은 방식으로 만들었어요. 컴퓨터에서 ★5와 같은 크기의 보드를 만드는 시간을 재 보니, 한 판당 평균 몇 밀리초였어요.
퍼즐과 수학
스도쿠 같은 다른 많은 펜슬 퍼즐도 보드를 키운 일반적인 형태에서는 NP 완전이라고 알려져 있어요. 사람이 즐겁게 푸는 퍼즐은 ‘전부 조사하지 않아도 논리를 세워 풀 수 있게’ 만들어진 것이 많아요. 앱 「지뢰찾기」의 찍기 없는 보드도 그중 하나예요.
확률 계산은 지뢰찾기의 확률에서 소개하고 있어요.
