퍼즐 이야기
잘 만든 스도쿠는 왜 정답이 딱 하나일까
스도쿠를 풀 때 우리는 정답이 하나 기다리고 있다고 믿어요. 그 약속은 우연이 아니라, 잘 만든 퍼즐마다 설계되어 있는 거예요.
찍기 게임이 아니라 퍼즐
판의 정답이 둘이라면, 언젠가 논리로는 둘 중 하나를 고를 수 없는 순간이 와요. 그러면 찍어야 해요. 출제자들은 그런 판을 고장 난 퍼즐로 봐요. 제대로 된 스도쿠는 정답이 딱 하나라서 모든 단계를 추리로 갈 수 있어요.
출제자는 어떻게 확인할까
요즘 퍼즐은 대부분 컴퓨터의 도움을 받아 만들어요. 흔한 방법은 완성된 판에서 숫자를 하나씩 지우는 거예요. 하나를 지울 때마다 풀이 프로그램이 정답이 여전히 하나인지 확인해요. 지웠을 때 정답이 둘이 되는 숫자는 남겨 둬요.
완성된 판은 몇 개나 될까
2005년 수학자 베르트람 펠겐하우어와 프레이저 자비스가 가능한 9×9 스도쿠 완성판의 수를 계산했어요. 약 66억 7천만의 1조 배, 22자리 숫자예요. 그중 상당수는 돌리거나 뒤집거나 숫자 이름만 바꾼 같은 판이라, 정말로 다른 판만 세면 약 54억 7천만 개예요.
마법의 숫자 17
힌트를 몇 개까지 줄여도 정답이 하나로 남을까요? 힌트 17개짜리 퍼즐은 오래전에 발견됐지만, 16개짜리는 아무도 찾지 못했어요. 2012년 개리 맥과이어, 바스티안 투게만, 질 시바리오가 거대한 컴퓨터 탐색 끝에 답을 발표했어요. 힌트 16개짜리 스도쿠는 없다. 17개가 최소예요. 이 논문은 2014년에 정식으로 실렸어요.
그래서 우리에게 좋은 점
잘 만든 스도쿠는 정답이 하나라서 운이 필요 없어요. 막혔다고 느낄 때, 퍼즐은 "아직 못 찾은 패턴이 있어"라고 말하고 있는 거예요. 그래서 끝냈을 때 그렇게 뿌듯해요.
자료
- Felgenhauer & Jarvis, "Enumerating possible Sudoku grids" (2005)
- McGuire, Tugemann & Civario, "There Is No 16-Clue Sudoku", Experimental Mathematics (2014)
- Mathematics of Sudoku – Wikipedia