1. Algorithm X

Algorithm X는 백트래킹을 기반으로 한 비정형 알고리즘으로, 선택적인 제약 충족 문제를 해결하는 데 사용됩니다. 이는 사실 특정한 데이터 구조에 얽매이지 않으며, 다양한 문제를 해결할 수 있는 매우 일반적인 알고리즘입니다.

Algorithm X의 작동 원리:

1. 제약 조건의 표현:
   • 문제는 일반적으로 '0'과 '1'로 구성된 이진 행렬로 표현됩니다.
   • 이 행렬의 각 열은 하나의 제약 조건을 나타내며, 각 행은 가능한 선택지를 나타냅니다.
   • 예를 들어, 스도쿠에서 각 열은 행, 열, 3x3 박스 내의 숫자 배치 제약을 나타낼 수 있습니다. 각 행은 스도쿠의 가능한 숫자 배치를 나타냅니다.
2. 열 선택:
   • Algorithm X는 가능한 제약 조건(열) 중 하나를 선택하여 그 열에 해당하는 모든 행을 살펴봅니다.
   • 이 단계에서, 가장 적은 수의 '1'을 가진 열을 선택하는 것이 일반적입니다. 이는 검색 공간을 줄이는 데 도움이 됩니다.
3. 행 선택:
   • 선택한 열에서 '1'을 포함하는 행 중 하나를 선택합니다. 이 행은 문제의 가능한 솔루션의 일부가 됩니다.
   • 선택된 행은 해당 열(제약 조건)을 만족시키므로, 이 행과 관련된 모든 열을 추가적으로 고려합니다.
4. 열 제거:
   • 선택한 행이 포함된 모든 열은 이제 제거됩니다. 이는 이미 만족된 제약 조건을 나타내므로 더 이상 고려되지 않습니다.
5. 반복:
   • 남아 있는 행렬에 대해 동일한 과정을 반복합니다.
   • 만약 가능한 행이 더 이상 없다면, 이전 선택으로 돌아가서 다른 행을 시도하는 백트래킹을 수행합니다.
   • 모든 열이 제거되면, 현재 선택된 행들이 문제의 해답을 나타냅니다.