ペンシルパズルにおける「解き筋」の概念の提案

情報処理学会

書誌事項

タイトル別名
  • A Proposal of the Concept "Solution Path" for Pencilpuzzle

説明

パズルは探索問題としての見地からその性質が考えられてきた.しかし数独やカックロなどのペンシルパズルでは,探索経路が一本道であり、探索問題として考えるのは意味がない.効率的な解法のためには数字を入れる図中の箇所を選ぶ順序が重要である. 本研究ではこの点に着目して新しい概念を提起し,理論化する.ペンシルパズルにおいて一般的に存在している,制約による解答の順序構造を問題の「解き筋」として定義した.解き筋を問題から抽出することで,問題の難易度や良し悪しの判定をするために使用する.効率的に解き筋を抽出するために,解き筋の中でも重複した部分を取り除いた有用な解き筋のみを得るアルゴリズムを設計する.ラテン方陣問題による実験を行い,その解き筋を得た.得られた解き筋から問題の特徴を考察する.

Puzzle problems are usually considered as examples of tree search. Problems of "Pencil Puzzles" such as sudoku and kakkuro have only one search path without branch. So dealing with them as search problem has no meaning. It is important to determine the ordering of the position where a number is fixed. We propose the new concept "solution path". It defined structure by restriction of the order of solution. It is used to get the value of problem difficulty. Additionally, an algorithm to remove redundant path is designed. We experiment about solution path in Latin magic square problems and consider feature of problems.

収録刊行物

詳細情報 詳細情報について

問題の指摘

ページトップへ