Hexagonal Tortoise Problem Solving using Constraint Programming

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 solutiosn 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 serach 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.