세상에서 가장 어려운 스도쿠를 ' 어떻게 해결하나요?

심도 우선 검색에서 단일 값 추측 차선책입니다.

여기에 폭 우선 가설 / 반증 방법에 기반한 추론 체인이 있습니다 (제 의붓 아들은 마지 못해 “교육 된 추측”이라고 부름).

모순을 포함하여 체인을 따라 가기 만하면됩니다. 23 개의 스도쿠 변형을 풀기 위해 컴퓨터 지원 솔버와 함께 사용하는 것이 가장 좋습니다. 그러나이를 따르기 위해 멋진 알고리즘이 필요하지 않습니다. (저는 집에서 개발 한 최적화되지 않은 Python 프로그램을 사용하므로 실제 컴퓨팅이 없습니다. 둘 중 하나를 포함합니다.

표기법은 스프레드 시트 규칙 (열 = 문자, 행 = 숫자) (또는 원하는 경우 체스)을 따릅니다.

STA Original Sudoku G8: 3,9 HYP # I8: 3,9 DIS # I8: 3,9 # B1: 1,2 => CTR => B1: 6 STA # I8: 3,9 + B1: 6 DIS # I8: 3,9 + B1: 6 # A2: 1,2 => CTR => A2: 5,9 STA # I8: 3,9 + B1: 6 + A2: 5,9 DIS # I8: 3,9 + B1: 6 + A2: 5,9 # B5: 1,2 => CTR => B5: 3,8 DIS # I8: 3,9 + B1: 6 + A2: 5,9 + B5: 3,8 => CTR => I8: 2,7 STA I8: 2,7 HYP I8: 2,7 # G7: 5 DIS I8: 2,7 # G7: 5 # G4: 6 => CTR => G4: 1,8 STA I8: 2,7 # G7: 5 + G4: 1,8 DIS I8: 2,7 # G7: 5 + G4: 1,8 # C5: 2,9 => CTR => C5: 6 STA I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 DIS I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 # H3: 4,5 => CTR => H3: 8 DIS I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 + H3: 8 => CTR => G7: 3,9 STA I8: 2,7 + G7: 3,9 HYP I8: 2,7 + G7: 3,9 # A8: 3,4,6 DIS I8: 2,7 + G7: 3,9 # A8: 3,4,6 # A9: 3 => CTR => A9: 6,7 STA I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 DIS I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 # D7: 2,7 => CTR => D7: 4,9 STA I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9 PRF I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9 => SOL 

World “s Hardest Sudoku 에 단계 스크린 샷과 방법에 대한 간단한 설명을 올렸습니다. 저는 “교육 된 추측”으로 어려운 퍼즐을 푸는 데에만 관심이 있기 때문에이 스도쿠가 실제로 광고 된 것만 큼 어렵지 않다는 것을 발견했습니다 (가설 1 단계 + 예견 1 단계 = 가설 2 단계). 사실 저는 아직 2 단계 이상의 가설과 1 개의 예견 (= 3 단계의 가설)이 필요한 스도쿠를 찾지 못했습니다.

댓글

• 솔버가 17 개 항목이있는 스도쿠 ‘와 얼마나 잘 맞습니까? 예 : theconversation.com/ …
• @SimonStreicher 17 개의 단서 스도쿠입니다. 어렵지만 내 알고리즘의 맥락에서 가장 어려운 스도쿠 중 하나는 아닙니다. 일반적으로 단서의 수와 스도쿠의 경도 사이에는 상관 관계가 없습니다. 분석 한 스도쿠에 대한 일부 통계 를 올렸습니다.
• @SimonStreicher 상위 95 개 스도쿠 목록 (즉, 95 개 어려운 퍼즐 )을 분석했습니다. 레벨이 hard 인 5 개의 suduko가 있습니다 (2 단계의 가설이 필요함). 여전히 101 개의 가장 어려운 스도쿠 보다 낮은 2 단계입니다. 찾았습니다.
• 정보 감사합니다. ‘ 아직도이 모든 것을 이해하려고 노력하고 있습니다. 다행히 귀하의 웹 사이트는 매우 철저합니다.
• @SimonStreicher 핵심은 단일 값 활성화에서 쉽게 인식 할 수있는 패턴 (쌍)으로 검색 공간을 줄이는 것입니다. 가능성. 예 :cell1은 2 개의 가능한 값 v1 및 v2를 허용하고, cell2는 동일한 가능한 값을 허용하지만 추가로 하나 이상의 다른 가능성 v3, v4, v5를 허용합니다. 따라서 cell1과 cell2는 쌍 (둘 다 v1과 v2 포함)이거나 셀 2는 v3, v4, v5 중 하나만 될 수 있습니다. 그런 다음이 가설을 확인합니다.

이 퍼즐의 경우 하나의 솔루션 만 있지만 약간 더 지능적인 추측과 확인 외에는 알려진 패턴이 작동하지 않습니다. 단서를 줄이기 위해 앞을 내다 봐야하는 단계의 수는 여기에서 측정 기준이며,이 퍼즐은 해결 가능한 상태에 도달하기 위해 9 개의 순차적 추측이 필요합니다.

스도쿠 위키의 솔버는 자바 스크립트에서 너무 오래 걸리고 숫자를 추측하도록 프로그래밍되어 있지 않기 때문에 “스도쿠 위키”를 얻을 수 없습니다.

해결책은 제곱의 값을 가정 한 다음 더 많은 가정이 필요한지 확인하기 위해 퍼즐을 줄여야합니다. 그렇다면 다른 가정을 만들고 계속하십시오. 본질적으로 가능한 솔루션에 대한 깊이 우선 검색입니다. sudoku-solutions 의 솔버가이 퍼즐에 대한 해결책을 제시하지만 단계를 제공하라는 요청을 받으면 다음과 같이 선언합니다.

이 솔버는 논리로 퍼즐을 완전히 풀 수 없습니다. 그렇다고 논리적 인 해결책이 없다는 의미는 아닙니다.

그런 다음 문제를 해결하는 데 사용한 단계 일부 를 즉시 나열하지 못합니다. 이것은 솔버가 솔루션을 찾기 위해 무차별 대입 분기 추측을 사용해야하는 경우에만 발생합니다.

결과적으로 나 자신이 “이 퍼즐을 해결하는 방법”에 대한 답을 합리적으로 제공 할 수있는 방법은 없습니다. 따라서 이러한 특정 체인을 찾고 다른 방대한 양의 체인이 작동하지 않는 이유를 설명하는 것이 포함됩니다.

하지만 그것이 여러분이하는 방법입니다. 사각형은 숫자, 다른 것, 다른 것, “아직 의미가 있고 퍼즐을 풀 수있는 순서에 도달 할 때까지 계속 확인하십시오. 또는 모순에 도달하여 백업하고 다시 시도해야합니다. 이것이이 질문에 대한 최선의 답변이라고 생각합니다.

수수께끼에 대한 해결책을 요청 했으므로 제가 제공 할 수 있습니다 (스포일러 블록에 마우스를 올려 놓으세요).

댓글

• 좋은 재귀입니다.
• 재귀 깊이는 최대 2 개 추측으로 해결했습니다. ” Naked Singles ” 전략은 총 61812 회를 실행했습니다 (실행 횟수가 수백만이되지 않고 더 높은 수준에서 캐싱을 수행 한 후). ” 숨겨진 싱글 ” 전략 32892 회 (캐시에서 제공되는 또 다른 28920 회 포함) 깊이가 1 인 검색이 256 회 실행되었습니다. 캐시에서 15 번 추가로 제공되었습니다 (각 시점에서 한 번의 추측 만 수행되었지만 실제로는 이러한 실행의 대부분이 실제로 다음 실행 내에서 발생했다고 생각합니다). 2 단계 검색 (‘ 2 개의 추측을 수행함)은 한 번만 실행하여 얻었습니다.
• (또한 이것이 실패한 유일한 퍼즐입니다 ‘ 한 수준의 추측만으로 내 프로그램을 깨뜨리지 마십시오)

싱가포르의 스도쿠 솔버 총리 를 다운로드하고이 퍼즐을 먹이세요 (정말 막혀있는 경우에만). 믿거 나 말거나, 그 총리는 꽤 강력한 프로그램을 만들었고 잠시 동안 멈춰있는 것처럼 보이지만 결국 다음과 같은 해결책이 나왔습니다.

862 || 751 || 349
943 || 628 || 157
571 || 493 || 286
============
159 || 387 || 624
386 || 245 || 791
724 || 169 || 835
============
217 || 934 || 568
438 || 576 || 912
695 || 812 || 473

이 퍼즐을 발명 한 사람에 따르면 분명히 논리로 풀 수 있습니다. 해결하는 데 24 시간이 걸렸습니다.

참고 :이 퍼즐은 질문과 다른 위치에있는 7 번째 줄의 1을 가지고 있습니다.이 퍼즐에는 여러 해가 있습니다.

참고 : em>

댓글

• 이 원본 퍼즐에 여러 가지 해결책이있는 것 같지 않습니다 (함축 된 경우). PM에 대한 귀하의 의견 ‘의 솔버가 잘못되었을 수 있습니다. 행 3, 열 7은 ” 1 “로 입력으로 제공됩니다. ” 7 ” (관찰 중 하나)가 아닙니다. exe에 대한 올바른 입력이 주어지면 알려진 솔루션을 출력합니다.
• @SimonStreicher 잘못된 입력은 7 행 3 열에 있으며 7은 1이어야합니다.
• 5 초 이상 멈춰 있습니까? 저의 아주 간단한 솔버는 그것에 대해 알아낼 수 있습니다. 시간의 양.

다른 컴퓨터 기반 솔루션을 추가 한 다음 MiniZinc 모델링 언어 는 다음 프로그램을 작성할 수 있습니다.

int: n; array[1..n, 1..n] of 0..n: initial_grid; int: reg; array[1..n, 1..n] of 1..reg: regions; array[1..n, 1..n] of var 1..n: final_grid; include "alldifferent.mzn"; constraint forall(r, c in 1..n)(initial_grid[r, c] = 0 \/ initial_grid[r, c] = final_grid[r, c]); constraint forall(r in 1..n)(alldifferent([ final_grid[r, c] | c in 1..n ])); constraint forall(c in 1..n)(alldifferent([ final_grid[r, c] | r in 1..n ])); constraint forall(region in 1..reg)(alldifferent([ final_grid[r, c] | r, c in 1..n where regions[r, c] = region ])); solve satisfy; output [ show_int(1, final_grid[r, c]) ++ if c = n then ("\n" ++ if (r mod 3 = 0 /\ r < n) then "---------------------\n" else "" endif ) elseif c mod 3 = 0 then " | " else " " endif | r, c in 1..n ]; 

적절한 데이터와 함께 file :

n = 9; reg = 9; regions = array2d(1..9, 1..9, [ 3 * (row div 3) + col div 3 + 1 | row, col in 0..8 ]); initial_grid = [| 8, 0, 0, 0, 0, 0, 0, 0, 0, | 0, 0, 3, 6, 0, 0, 0, 0, 0, | 0, 7, 0, 0, 9, 0, 2, 0, 0, | 0, 5, 0, 0, 0, 7, 0, 0, 0, | 0, 0, 0, 0, 4, 5, 7, 0, 0, | 0, 0, 0, 1, 0, 0, 0, 3, 0, | 0, 0, 1, 0, 0, 0, 0, 6, 8, | 0, 0, 8, 5, 0, 0, 0, 1, 0, | 0, 9, 0, 0, 0, 0, 4, 0, 0 |] ; 

그리고 상당히 표준적인 랩톱에서 기본 솔버를 사용하면 솔루션이 100ms 내에 나옵니다. 이는 PM Lee의 C ++ 구현을 상당히 능가합니다. 여백.

댓글

• 이 알고리즘은 선형 계획법을 기반으로합니까?
• 그것 ‘ s in the same realm-솔버는 제약 조건 프로그래밍 솔버입니다. 문제가 실제로 선형이 아니지만 ‘ 잘 작동하지만 제약 조건이 많습니다. 몇 가지 매우 기본적인 검색 방법으로 가능한 솔루션의 공간을 줄이기위한 휴리스틱의 조합입니다.
• 저는 ‘ 감동했습니다. 제 매뉴얼은 매우 간단합니다. Kotlin의 lver는 최대 2의 검색 깊이를 사용하여 랩톱에서 약 5 초만에 이깁니다.