« 열빙어 | Main | 선거 »

Sudoku에 감추어진 수학

Scientific American 6월호에 "The Science Behind Sudoku"라는 글이 실렸다. 잠깐 관심을 갖고 보았는데 9x9 Sudoku로 만들 수 있는 퍼즐의 숫자에 대한 이야기가 나온다.

몇 개의 퍼즐을 만들 수 있을까? 정확히 5,472,730,538란다.

또 하나. 각각의 퍼즐들의 정답이 항상 단 1개만 존재할까? 예를 들면 아래와 같은 경우는 해법이 2개가 나오는데 이런 경우가 몇개나 될까?

Sudoku

77개란다. 이론적으론 77개라는 답은 알지만 아직까지 77개 모두 찾지를 못했다. 이걸 다 찾을려면 컴퓨터로 1초에 하나씩 풀어 검증을 한다고 해도 173년.