裁ち合わせパズルの重複解なし全解探索システム

• Item type: Symposium(1)
• 公開日: 2006-11-10
• タイトル: 裁ち合わせパズルの重複解なし全解探索システム
• タイトル / 言語: en
• タイトル: A Total Solver of Dissection/Put-Together Shape Puzzles
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 東京農工大学
• 著者所属: 東京農工大学
• 著者所属: 東京農工大学
• 著者所属(英): en
• 著者所属(英): Tokyo University of Agriculture and Technology
• 著者所属(英): en
• 著者所属(英): Tokyo University of Agriculture and Technology
• 著者所属(英): en
• 著者所属(英): Tokyo University of Agriculture and Technology
• 著者名: 五十嵐, 力; 但馬, 康宏; 小谷, 善行
• 著者名(英): Igarashi, Chikara; Tajima, Yasuhiro; Kotani, Yoshiyuki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ペントミノやヘキソミノのような箱詰めパズルの全解探索問題において、探索量の削減が大きな課題となっている。同一の解が回転や反転などによって複数現れてしまうと、出力される解の数が数倍になり、それに応じて探索量も倍加する。そこで本研究では、裁ち合わせパズルの全解を重複解が出ないように求める。裁ち合わせパズルとは、異なる二つの図形(図形1、図形2)に対し、図形1を任意数に分割し、分割したピースによって図形2を構成するパズルである。本稿では、図形1を重複なくすべての可能性で分割し、分割したピースを用いて図形2に重複なく箱詰めする手法を述べる。本システムにおいて、いくつかの裁ち合わせパズル問題に対して重複なく全解を求められることを示す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Decreasing amount of search is a big problem for a total solver of puzzle such as pentomino,hexomino and so on. The number of results that system output and the amount of search becomes several times when the system calculates overlapping solutions. In this paper, we propose a method of a total solver of dissection/put-together shape puzzles. Dissection/put-together shape puzzle is a puzzle that composes another figure by dividing an arbitrary figure. We show that this system doesn't output overlapping solutions and all solutions are outputs for any dissection/put-together shape puzzle problems.
• 書誌情報: ゲームプログラミングワークショップ2006論文集; 巻 2006, p. 40-47, 発行日 2006-11-10
• 出版者 / 言語: ja
• 出版者: 情報処理学会