세계에서 가장 어려운 스도쿠를 힌트 엔진으로 풀어 봤어요

공식적으로 가장 어려운 스도쿠는 없어요. 어떻게 측정하느냐에 따라 달라져요. 저희는 스도쿠 앱의 힌트 엔진을 사용해, 사람이 풀듯이 매번 적용할 수 있는 가장 쉬운 기법으로 한 단계씩 풀어 보며 측정했어요.

측정 방법

힌트 엔진은 앱의 힌트와 같은 코드를 사용해요. 숫자를 채울 수 있는 가장 쉬운 기법을 찾아 숫자를 넣고, 격자가 완성될 때까지 다시 찾기를 반복해요. 포싱 체인은 마지막으로 시도하는 기법이에요. 그것으로도 풀리지 않으면 엔진은 들어갈 숫자는 알지만, 그 숫자를 설명할 풀이 단계는 없어요. 스도쿠 솔버에서 모든 단계를 직접 볼 수 있어요.

분석 결과

이 결과로 알 수 있는 것

• 처음 주어진 숫자가 적다고 퍼즐이 더 어려워지지는 않아요. 무차별 대입 풀이를 어렵게 만든 퍼즐에는 정답이 하나인 스도쿠에 필요한 최소 개수인 17개의 숫자가 주어져 있지만, 사람은 싱글만으로 풀 수 있어요. Inkala의 2012년 퍼즐에는 숫자가 21개 주어져 있는데도 숫자를 시험 삼아 넣어 보는 풀이가 필요해요.
• 컴퓨터에 어려운 퍼즐이 사람에게도 어려운 것은 아니에요. 모든 숫자를 차례로 넣어 보는 프로그램은 무차별 대입 풀이를 어렵게 만든 퍼즐에서 아주 많은 경우를 시도해야 하지만, 사람은 이 퍼즐을 풀 때 전혀 추측할 필요가 없어요.
• 앱의 가장 어려운 난이도에서도 숫자를 시험 삼아 넣어 볼 필요는 없어요. 앱의 퍼즐 60,000개 중 포싱 체인이 필요한 퍼즐은 하나도 없어요. ‘극한’ 난이도는 주로 ALS-XZ 기법으로 결정되며, ‘극한’ 퍼즐의 86.3%가 여기에 해당해요.

어떤 퍼즐이 가장 어려운지는 측정 기준에 따라 달라져요. SudokuWiki 자체 기준에서는 Inkala의 2012년 퍼즐이 David Filmer의 두 퍼즐에 이어 세 번째예요. SudokuWiki: Arto Inkala Sudoku