댄스 링크를이 CSP에 적용 할 수 있습니까?

Question

Knuth의 알고리즘 X의 Dancing Links 구현을 사용하여 this CSP을 해결할 수 있습니까? 이 게임에서 첫 번째와 마지막 번호는 항상 보드에 있으며, 각 공식화 된 문제에 대한 유일한 해결책은 있다고 믿습니다.

Answer 1

번호

제약 조건 솔버는 확실히 이런 종류의 문제를 해결할 수 있지만, 그것을 할 수있는 가장 빠른 방법이 될 가능성이 보인다. Offhand에서는 솔버에게 "경로 자체가 교차 할 수 없다"는 것을 말하는 것이 어려울 것 같은데 이는 유용한 힌트입니다.

Answer 2

예. A, B, C, D,

이

+---+ +---+ 
| | | 6 | 
+---+---+---+ 
| | | 
+---+---+ 
| 1 | | 
+---+---+ 

최초의이 편지와 빈 셀에 이름을 보자 : 우리는 3 종류의 표현 할 필요가

+---+ +---+ 
| d | | 6 | 
+---+---+---+ 
| b | c | 
+---+---+ 
| 1 | a | 
+---+---+ 

을

생각에는 우리는이 Hidato를 해결하려면 X Algorithm 각 용액 라인 제약 : 숫자 사용

• (동일한 번호가 사용되지 않도록 회)
• 셀이 사용됩니다 (동일한 셀이 두 번 사용되지 않도록)
• 다음 셀은 제약을받습니다 (인접한 셀 중에서 다음 셀만 선택할 수 있도록). 이 마지막 제한 조건은 정확한 커버를 요구하지 않으므로 보조 열DLX 용어로만 사용해야합니다.

생성 문제 행렬은 다음이다 : 예를 들어, (제목 라인을 계산하지 않고) 두 번째 행과 같이 판독 될 수

1 2 3 4 5 6 a b c d 2a 2b 2c 2d  3a 3b 3c 3d  4a 4b 4c 4d  5a 5b 5c 5d 
1        1 
    1   1   1    1  1 
    1   1   1    1 
    1    1   1    1 
    1    1   1  1  1 
    1  1       1    1  1 
    1   1       1    1 
    1   1       1    1 
    1    1       1  1  1 
     1  1           1    1  1 
     1  1           1    1 
     1   1           1    1 
     1   1           1  1  1 
     1 1               1 
     1  1               1 
     1 1  1               1 
     1   1               1 

이 줄 수 2 (제 1 설정) a (초 1). 또한 조명 제한으로 2a 제한됩니다. 그리고 그들은 또한 3a과 3d이 아니며, 이것들은 셀 a에 인접하지 않기 때문에 3을 제한합니다.

• 숫자 만 2에 제약을 말한다 첫 번째 줄 :

  모든 라인을 제외하고,이 방법을 참조하십시오.

• 라인 (마지막 4 개) 또한 에 인접한 제약 조건을 포함합니다. 구현은 독자들에게 연습 문제로 남겨

...