지수귀문도는 18세기 조선 학자 최석정이 고안한 조합 퍼즐이다. 마방진처럼 특정 부분의 합이 같도록 숫자를 배열하는 문제이지만, 배열 모양이 육각형 형태이다. 특정 형태의 지수귀문도는 풀이법이 알려져 있지만, 일반적인 형태의 해는 찾기가 어렵다. 그래서 조합 검색 기법을 시험하는 데 좋은 문제이다. 이 논문은 제약 프로그래밍 기법을 이용하여 지금까지 알려진 것보다 훨씬 큰 지수귀문도의 해를 찾아내는 방법을 소개한다. 그리고 순수 제약 프로그래밍만으로는 한계에 부딪칠 수 밖에 없는 이유를 논의하고, 여기에 기계 학습법을 조합하는 연구 방향을 제시한다.
The hexagonal tortoise (jisuguimundo) is an 18th century Korean combinatorial problem. As in magic square problems, it requires allocating numbers to a tiling, in such a way that specific sums are conserved. Unlike magic squares, however, the tiling is hexagonal. While general solutions for some very specific shapes of tilings are known, in general they are difficult to find, so that the problem becomes a useful playground for combinatorial search methods. We present constraint programming methods which have been able to find solutions an order of magnitude larger than previous methods. We discuss why it will be difficult to extend pure constraint programming methods much further, and propose a research direction combining constraint programming and learning methods.
