だまし絵迷路生成に関する複数のハミルトン閉路構成法の比較評価

摘要

本稿では，白黒2値画像の黒地部分が解となる絵画的迷路を発展させ，2つの2値画像（ダミー画像と解画像）に対し求解前はダミー画像が浮き出て見え，解画像と対応する解を持つ迷路（だまし絵迷路と呼ぶ）の生成を試みる.絵画的迷路生成に用いられる全域木に基づくハミルトン閉路構成法やSATソルバによるハミルトン閉路構成法などを組み合わせただまし絵迷路生成法を設計し，構成法ごとの計算時間や生成される迷路の品質評価および構成法の組み合わせにより生成された複数のだまし絵迷路の品質評価を行う.%This report proposes a new type of maze generation as a generalization of the picturesque maze generation problem, which outputs a maze in which the solution path fills up black pixels of an input black-and-white raster image. The picturesque mazes generation problem with illusory images has two input binary images, which are called a solution image and a dummy image, and outputs a picturesque maze, which has a solution corresponding to the solution image but looks like the dummy image before solving. In this report, we propose a method generating picturesque mazes with illusory images by combining two constructions of Hamiltonian circuits, of which one is a method based on spanning trees and the other is a SAT encoding method. And, the proposed method is evaluated by using the formula based on feature quantity of mazes.