5K-01
動的計画法を用いた確率計算によるNonogram解法の提案
○齊藤敏人,奥出真理子(茨城高専)
Nonogramとは,行と列の数字をヒントにマス目を塗りつぶして絵を完成させるパズルゲームである.NP完全問題に分類され,パズルのサイズが大きくなると計算量が膨大になることが知られている.本研究では,動的計画法を用いた場合の数の数え上げによってライン内で各マスが塗られる確率をO(n^2)で算出するアルゴリズムを提案する.提案アルゴリズムによるソルバーを開発し,webpbnのパズルを用いて既存ソルバーの中で最速といわれるpbnsolveとの計算量を比較した.その結果,ラインソルブのみでは解けない単一解を持つ35個のパズルのうち25個においてpbnsolveより少ない計算量で解けることを確認した.