문제 한 줄 요약) 어떤 스도쿠던지 0.1초 내에 해결할 수 있는 코드를 작성해라.

사전 지식

춤추는 링크 (Dancing links) 테크닉을 이용해 구현한 크누스 X 알고리즘(DLX라고도 합니다)에 대해 알고 있어야 합니다.

저는 https://velog.io/@jaehyeoksong0/Knuths-Algorithm-X ← 이 블로그를 정말 많이 참고했습니다.

지금 시간이 2시 반이라 좀 대충 쓴 감이 있는데, 나중에 좀 더 자세하게 써볼게요

Exact Cover

자연수의 집합 $U$와, 자연수의 집합의 집합 $S$에 대해,

• $S'$를 구성하는 원소들끼리의 교집합 $=\emptyset$
• $S'$를 구성하는 원소들끼리의 합집합 $= U$

인 $S$의 부분집합 $S'$를 구하는 문제를 Exact Cover라고 한다.

예를 들어,

$U=\{1,2,3,4,5,6,7\},S=\{A,B,C,D,E,F\}$이고,

• $A=\{1, 4, 7\}$
• $B=\{1, 4\}$
• $C=\{4,5,7\}$
• $D=\{3,5,6\}$
• $E=\{2,3,6, 7\}$
• $F=\{2, 7\}$