지뢰찾기(minesweeper) 게임과 수학
지뢰찾기(minesweeper) 게임란 $m \times n$ 크기의 격자에 주어진 숫자를 바탕으로 각 격자에 숨어 있는 지뢰를 모두 찾는 게임이다. 이 때, 각 격자에 주어지는 숫자는 그 격자에 인접한 8개의 격자에 위치한 지뢰의 개수를 나타낸다. 지뢰찾기 게임에도 다양한 수학적 사실이 숨겨져 있는데, 이번 글에서는 그 중 하나를 살펴보도록 하자. 이제 어떤 $m \times n$ 크기의 지뢰찾기 게임이 주어졌다고 하자. 이 게임에서 지뢰가 숨겨져 있는 모든 격자의 지뢰를 없애고, 반대로 지뢰가 숨겨져 있지 않은 모든 격자에 지뢰를 숨기면 새로운 지뢰찾기 게임을 얻게 된다. 이렇게 얻은 게임을 주어진 지뢰찾기 게임의 쌍대(dual)하고 하자. 예를 들어 아래 두 지뢰찾기 게임은 서로 쌍대 관계이다. 위..