불평등 스도쿠 해결 전략?

Question

내가 최근 들어간 클래식 스도쿠 솔버의 비틀기는 각 상자에 불평등 조건이 추가 된 추가 스윙이있는 클래식 스도쿠 퍼즐 인 (다소 미친) inequality sudoku입니다.

이제는 일반용 스도쿠 솔버를 파이썬에서 (무차별 방식을 사용하여) 긁어 냈지만이 문제를 해결하기 위해 어떤 방법을 사용하는지 파악하는 데 어려움을 겪고 있습니다. 나는 그것을 overthinking 또는 이것은 훨씬 더 일반적인 퍼즐보다 복잡 한가?

Answer 1

이것은 단지 제약 조건 해결입니다. 당신은 스도쿠 보드가있는 경우

, 다음, 각 셀 (I, J) 당신은 이러한 제약이 있습니다 특정 세포에 대한

board[i, j] in [1, 2, 3, 4, 5, 6, 7, 8, 9] 
for each cell (a, j) where i != a: board[a, j] != board[i, j] 
for each cell (i, b) where j != b: board[i, b] != board[i, j] 

을, 당신은 이미 그 가치가 무엇인지 알고있다. 이는 실제로 다른 제약 조건입니다.

board[c1, c2] == 7 

그리고 그게 전부입니다. 브 루트 포스 체커 (brute force checker)는 보드 셀을 채울 수있는 모든 방법을 간단하게 실행할 수 있으며 (특히 첫 번째 제약 조건에주의를 기울여야 함) 이러한 제약 조건이 유지되는지 확인해야합니다. 그 모든 것들이 그 채워 넣기를 기다린다면, 그것은 보드를 출력 할 수 있습니다. 그렇지 않으면 계속됩니다.

특정 위치에 대해 부등식을 허용하면 똑같은 무차별 대항 알고리즘을 사용할 수 있습니다. 그것은 단지 새로운 보드를 말하기 전에 상관이 확인이 제대로 채워집니다 :

2 <= board[c3, c4] < 8 

---

그것은 무차별 쉽게, 그러나 그것은 또한 프롤로그 같은 논리 프로그래밍 언어를 아주 쉽게, 또는 여기 Numberjack

같은 제약 프로그래밍 라이브러리 (외관의 순서대로) 위의 모든 제약의 Numberjack 버전입니다 : 이것은 idioma이

board[i, j] = Variable(1, 9) 
# ... need to define all the board before you execute the following: 
for a in xrange(1, 10): 
    model.add(board[a, j] != board[i, j]) 
    model.add(board[i, a] != board[i, j]) 
model.add(board[c1, c2] == 7) 
    model.add(board[c3, c4] < 8) 
model.add(board[c3, c4] >= 2) 

아니다 제약 솔버의 실제 사용을위한 tic. 실생활에서는! = s를 개별적으로 지정하는 대신 "모두 다름"제약 조건, AllDiff 등을 사용합니다. 그러나 당신은 아이디어를 얻습니다.

Answer 2

Peter Norvig의 solver을 수정하여 이러한 제약 조건을 추가 할 수 있습니다.