情報処理学会 第78回全国大会講演要旨

多角形12変化問題とは、長さ12の糸を用いて面積が整数n (n＝1〜11)になる凸多角形を作るパズルである。ただし、凸多角形の全頂点は正方形状の格子点上にあるものとし、格子点間隔が最大となる図形を最適解とする。本パズルは頂点の数が増えるあるいは格子点間隔が短くなるにつれ解候補が爆発的に増加する。そのため、人間が直感的に解くことは困難であり、全探索により解くことも不可能である。現在パズルの最適解は求まっていない。本研究では、解候補の組み合わせ爆発に対処するアルゴリズムを提案する。解候補が最多となる面積11において、416(10^24)通りの解候補を2863万通りまで削減することに成功した。