스도쿠 17개의 단서 전문가

스도쿠 17개의 단서 플레이 방법

스도쿠는 논리 기반의 숫자 배치 퍼즐입니다. 목표는 9x9 격자를 1-9의 숫자로 채워서 각 행, 열, 3x3 하위 격자에 9개의 숫자가 모두 정확히 한 번만 포함되도록 하는 것입니다.

2009년에 게리 맥과이어(Gary McGuire)와 그의 팀은 16개의 단서가 있는 스도쿠 퍼즐에는 적어도 두 개의 해결책이 있어야 한다는 것을 증명했습니다. 그들은 '데드 패턴'이라는 기술을 사용하여 이를 수행했습니다.

데드 패턴은 두 개 이상의 가능한 솔루션이 있는 스도쿠 구성입니다. McGuire와 그의 팀은 16개의 단서가 있는 스도쿠 퍼즐에는 최소한 하나의 데드 패턴이 포함되어 있어야 한다는 사실을 발견했습니다. 따라서 이 퍼즐에는 적어도 두 가지 해결책이 있어야 합니다.

이 결과는 여러 가지 의미를 갖습니다. 첫째, 독특한 해법을 지닌 16개의 단서 스도쿠 퍼즐은 없다는 뜻입니다. 둘째, 16개의 단서가 있는 스도쿠 퍼즐은 다양한 방법으로 풀 수 있다는 의미입니다. 셋째, 16개의 단서가 있는 스도쿠 퍼즐이 무한히 많다는 뜻입니다.

다음은 스도쿠 퍼즐이 고유한 해결책을 찾기 위해 최소한 17개의 단서를 가지고 있어야 한다는 증명에 대한 좀 더 기술적인 설명입니다:

증명은 16개의 단서가 있는 스도쿠 퍼즐을 고려하는 것으로 시작됩니다. 이 퍼즐은 빈 사각형에 들어갈 수 있는 숫자에 대한 제약 세트로 생각할 수 있습니다.

그런 다음 "역추적"이라는 기술을 사용하여 퍼즐에 대한 해결책을 찾을 수 있습니다. 역추적은 답을 찾을 때까지 빈 사각형에 있는 가능한 모든 숫자 조합을 시도하는 재귀 알고리즘입니다.

퍼즐에 대한 고유한 솔루션이 있는 경우 역추적을 통해 결국에는 이를 찾을 수 있습니다. 그러나 해결 방법이 여러 개인 경우 역추적을 통해 해결 방법을 찾지 못할 수도 있습니다.

McGuire와 그의 팀은 역추적을 사용하여 고유한 해결책이 있는 16개의 단서가 있는 스도쿠 퍼즐이 있는 경우 항상 해결책을 찾는 방식으로 역추적 알고리즘을 시작할 수 있는 방법이 있음을 보여주었습니다.
그런 다음 그들은 이것이 불가능하다는 것을 보여주었습니다. 그들은 죽은 패턴으로 이어지는 16개의 단서 세트를 구축함으로써 이를 수행했습니다. 이 데드 패턴은 퍼즐에 두 가지 가능한 솔루션이 있으며 항상 동일한 솔루션을 찾는 방식으로 역추적 알고리즘을 시작할 방법이 없음을 의미합니다.
이 결과는 16개의 단서가 있는 스도쿠 퍼즐에는 적어도 2개의 답이 있어야 함을 보여줍니다.