A Total Solver of Dissection/Put-Together Shape Puzzles

IPSJ

Bibliographic Information

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

Description

ペントミノやヘキソミノのような箱詰めパズルの全解探索問題において、探索量の削減が大きな課題となっている。同一の解が回転や反転などによって複数現れてしまうと、出力される解の数が数倍になり、それに応じて探索量も倍加する。そこで本研究では、裁ち合わせパズルの全解を重複解が出ないように求める。裁ち合わせパズルとは、異なる二つの図形(図形1、図形2)に対し、図形1を任意数に分割し、分割したピースによって図形2を構成するパズルである。本稿では、図形1を重複なくすべての可能性で分割し、分割したピースを用いて図形2に重複なく箱詰めする手法を述べる。本システムにおいて、いくつかの裁ち合わせパズル問題に対して重複なく全解を求められることを示す。

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.

Journal

Details 詳細情報について

Report a problem

Back to top