스도쿠가 가질 수 있는 최소 힌트 수는 무엇인가요?
마지막 업데이트
유효한 스도쿠 - 정확히 하나의 해를 가진 것 - 적어도 17개의 주어진 숫자가 필요합니다. 이것은 입증된 수학적 결과입니다. 16개 이하의 단서를 가진 퍼즐은 여러 해를 가지거나 전혀 해가 없습니다.
2012년 증명
2012년, University College Dublin의 Gary McGuire, Bastian Tugemann, Gilles Civario는 유효한 16-클루 스도쿠가 존재하지 않는다는 증명을 발표했습니다. 그들의 작업은 주로 계산적이었습니다. 가능한 모든 16-클루 그리드의 전체 공간을 검색하여 그 중 어느 것도 유일한 해결책을 생성하지 않음을 확인했습니다. 이 검색에는 약 7백만 코어-시간의 계산이 필요했습니다.
이전에는 17이 최소라고 널리 믿어졌으며 수천 개의 17-클루 퍼즐이 실험적으로 발견되었습니다. McGuire 팀은 16이 불가능하다는 최초의 엄격한 증명을 제공했습니다.
17-Clue 퍼즐의 모습
17-clue 퍼즐은 매우 드물다 - 81개의 셀에 17개의 주어진 숫자가 있고, 64개가 비어 있습니다. 이들은 풀기 가장 어려운 퍼즐 중 하나이며 일반적으로 advanced techniques이 필요합니다. 유효한 17-clue 퍼즐을 찾는 것 자체가 수십 년의 계산 노력이 필요했습니다. 글을 쓰는 시점에서, 49,000개 이상의 본질적으로 다른 17-clue Sudoku 퍼즐이 알려져 있습니다.
이것이 퍼즐 디자인에 의미하는 바
인간 해결사를 대상으로 한 출판된 퍼즐은 거의 22 클루 미만으로 내려가지 않습니다. Expert 및 Master 난이도 퍼즐은 일반적으로 22-27개의 주어진 숫자를 사용하는 반면, 쉬운 퍼즐은 36-45개를 사용합니다. 17-클루 최소값은 이론적 한계입니다. 실제로는 좋은 기술과 즐거운 해결 경로가 클루 수보다 훨씬 더 중요합니다.