본 포스트는 기본적으로 이 포스트와 위키피디아 문서 등을 바탕으로 공부한 내용을 최대한 쉽게 풀어서 개인적으로 정리해보고자 작성되었습니다. 충분한 알고리즘 지식이 있다면 앞서 명시된 포스트를 참고하시는 게 더 빠를 수 있습니다! 개요 Knuth's Algorithm X는 Exact Cover 문제를 해결하기 위해 Donald E. Knuth가 제시한 알고리즘이다. Dancing Links 테크닉을 사용하여 구현한 Algorithm X를 DLX라고 한다. Exact Cover 집합 U = {1, 2, 3, 4, 5, 6, 7}이고, U의 부분집합 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}