정확한 덮개(알고리즘 X) 계산기

«겹쳐도 되는가»가 다릅니다. 집합덮개는 최소 개수로 덮기만 하면 되고 겹쳐도 상관없지만, 정확한 덮개는 개수를 묻지 않는 대신 모든 원소가 «정확히 한 번» 덮여야 합니다. {1,2}와 {2,3}은 {1,2,3}의 집합덮개지만 2가 두 번 덮이므로 정확한 덮개는 아닙니다.

남은 1이 가장 적은 열을 고르면(MRV) 탐색 나무가 극적으로 줄기 때문입니다. 1이 하나뿐인 열은 선택의 여지가 없어 바로 확정되고, 0개면 그 가지가 즉시 죽습니다. 무작위 행렬 300개로 재어 보면 MRV가 한 번도 지지 않고 많게는 열 배 넘게 노드를 줄입니다 — 이 계산기가 두 전략을 나란히 세는 이유입니다.

아닙니다. 알고리즘 자체는 그대로 알고리즘 X이고, DLX는 «지운 것을 되돌리기가 공짜인» 이중연결 리스트 구현 기법일 뿐입니다. 노드를 리스트에서 뺄 때 자기 자리의 포인터를 그대로 남겨 두면 되돌릴 때 그 포인터로 다시 끼워 넣을 수 있다는 것이 요점입니다. 이 계산기는 문제 크기가 작아 비트마스크로 구현했습니다.

바뀝니다. 스도쿠는 «칸 하나가 채워짐», «어느 행에 어느 숫자», «어느 열에 어느 숫자», «어느 상자에 어느 숫자» 네 종류의 열을 두고, 각 행이 «어느 칸에 어느 숫자를 넣는가» 하나가 됩니다. N퀸은 행·열이 필수 열이고 대각선은 «두 번 덮이면 안 되지만 안 덮여도 되는» 선택적 열이 되는데, 이 계산기는 필수 열만 다룹니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서만 이뤄지고, 입력값은 이 기기의 저장소에만 남습니다.