情報処理学会論文誌

Vol.56 No.6 1507–1516 (June 2015)

複数の正答を持つ単位正方形の組合せパズルに関する研究
山本 陽平1

金森 由博2

三谷 純2,a)

受付日 2014年10月1日, 採録日 2015年3月4日

概要：本論文では，両面に色の付いた単位正方形をピースとする組合せパズルについて議論する．ピース
は両面に色を付けることができ，すべてのピースを過不足なく使用してあらかじめ指定された色模様（「正答」と呼ぶ）を復元することを目的とする．正答が 2 つ以下であれば，ピースの各面に適切に色を割り当てることで，必ずすべての正答を再構成できる．正答が 3 つ以上ある場合には，正答間で共通する色をう
まく再利用する必要があり，場合によってはすべての正答を実現するピースの集合が存在しないこともあ
るため，パズルの問題を作成するときには注意が必要となる．そこで，複数の正答が入力として与えられたときに，その正答を実現できるピースの集合が存在するか否かを判定するための条件式と，存在する場
合にはピースの生成を行う手法を提案する．そうでない場合には，正答の色合いを調整して，ピースを生成可能にする手法の提案も行う．いくつかの例題で提案手法の実験を行い，実際にパズルを試作したので報告する．
キーワード：ゲーム・パズルの数理的基礎，モノミノ，パズル設計支援

A Study on Square-tile Puzzle with Multiple Answers
Youhei Yamamoto1

Yoshihiro Kanamori2

Jun Mitani2,a)Received: October 1, 2014, Accepted: March 4, 2015

Abstract: We discuss about a new tile puzzle whose pieces are single-unit squares with colored front andback faces. The goal is to reconstruct given colored grid patterns with the pieces with nothing left. It is
obvious that any two answer patterns are able to be reconstructed by simply assigning an appropriate color
to each face of a piece. However, we have to reuse faces of pieces between diﬀerent answer patterns if thenumber of answer patterns is more than two. Because this reuse may fail if too many colors are used in
the answers, we have to pay careful attention to the design of answer patterns. We found the condition ofanswer patterns for the existence of a set of pieces which is able to reconstruct all of them. We propose amethod for generating pieces from input answer patterns. Our method reduces the number of colors used in
the answer patterns if there is no set of pieces that satisﬁes the answer patterns. We tested our method withseveral examples, and we made a prototype puzzle.
Keywords: mathematical foundations of games and puzzles, monomino, puzzle design support

1. はじめにズルの一種に，ポリオミノをピースに用いるものがこれまでに数多く考案されている．ポリオミノとは，単位正方形

ゲームやパズルを対象とした研究は，情報科学の分野にの辺と辺を平面上でつなぎ合わせて作られる多角形の総称

おける探索技術の発展などに大きく貢献している．図形パであり，ポリオミノをピースに用いたパズル（以降ではポリオミノパズルと呼ぶ）は，1953 年に Golomb により考案

1

2

a)

筑波大学大学院システム情報工学研究科
Graduate School of Systems and Information Engineering,
University of Tsukuba, Tsukuba, Ibaraki 305–8573, Japan筑波大学大学院システム情報系
Information and Systems, University of Tsukuba, Tsukuba,
Ibaraki 305–8573, Japanmitani@cs.tsukuba.ac.jp

c 2015 Information Processing Society of Japan

された [6], [7]．その後，ポリオミノパズルには多くのバリ
エーションが作り出されている．たとえばピースを 5 つの正方形をつなげたものに限定したパズルはペントミノと呼ばれ世界中で広く親しまれている．また単位正方形に色を割当て，敷き詰めたときに市松模様が再現されるよう配置

1507

情報処理学会論文誌

Vol.56 No.6 1507–1516 (June 2015)

れた Polyomino Solver [5]，Andreas によって開発された

BurrTools [15] などがあり，一般に公開されている．
ポリオミノパズルに関する研究には，西岡によるタイリ
ング可能なポリオミノの列挙を行う研究 [14] や，是川らの本論文で提案するパズルの例．両面に色の付いた単位正方形

ポリオミノパズルを作る研究 [11]，Erickson による NP 完のピース 64 個（左）から構成される 3 つの正答を持つ

全なドミノの敷き詰め問題に関する研究 [3] があげられる．

Fig. 1 An example of the puzzle we propose in this paper. This

是川らは，ポリオミノのセルごとに付与された模様を，ラテ

example has three answers reconstructed with 64 unit

ン方陣を描くように配置する問題を扱っている．ポリオミ

図 1squares (left) with colored front and back faces.

ノパズルを解くことは，村井らの研究 [13] が集積回路の設計に用いることを前提としているように，あるものを敷き詰に制限を与えるなど，正答と判断する条件に制約を与える

める分野に役立つことがある．安倍らは計算ブロックパズ

ことで，パズルとしての面白味や難易度に変化を与える試

ルを対象とした研究 [2] を行っている．計算ブロックパズル

みがなされている．

は見方を変えると，1, 2, . . . , n までの数値が割り振られた n

本論文で対象とするパズルでは，各ピースは 1 つの正方枚のモノミノを扱うパズルと見ることができる．色の付い形からなる（モノミノと呼ぶ）．各ピースの裏と表の両面にたピースを用いて，複数の異なる絵柄を復元するパズルに色を付け，正答のための制約を格子に色を付けた「色模様」

は，株式会社テンヨーの商品である JIGAZO PUZZLE [17]で指定する（図 1）．正答を構成するセルの数はピースのがある．このパズルは，各ピースの色の濃淡の違いを利用数と同一であり，ピースは過不足なく使用する．見えていし，並び順を変えることで様々な絵柄を作り出している．

る面で正答を構成することが目的であり，完成時に見えな

近年の 3D プリンタの普及とともに，3 次元物体の表面

い面の状態は問わない．このようなパズルでは，正答が 1を，歪みを許容したポリオミノの集合に分割にする研究 [12]つであれば，正答となる色模様を分割するだけでピースをや，モデルの内部で互いに固定し合うピース（lock 構造を作れる．また正答が 2 つであれば，ピースの裏面に第 2 の持つピース）に分解する研究 [16], [18] など，立体構造を持

正答を構成する色を割り当てればよい．しかしながら，正つ組合せパズルに関する研究も行われている．

答が 3 つ以上である場合の話は簡単でない．正答間で共通異なる複数の正答を共通のピース集合から復元するパズ

する色を使いまわさないと，すべての正答を実現するピー

ルとして，「裁ち合わせパズル」があげられる．本研究で対ス集合を作れないことがあり，またそもそも，そのような象とするパズルは色に注目するが，裁ち合わせパズルは幾ピース集合が存在し得ないこともある．ここで，興味深い

何的な形に注目する．2 種類以上の面積の等しい図形が与問題が提起できる．複数の正答が与えられたときに，それえられたときに，一方の図形を複数の部品に分割して並べらを実現できるピース集合が存在するかどうか，どのよう替え，他方の図形を復元することを目的とする．一方を有に判定できるだろうか．また，存在すると判定された場合

限個の部品に分割して他方の図形を復元できることは，ボには，各ピースの表面と裏面に割り当てる色はどのようにヤイの定理として知られているため，パズルとしては部品決めるべきだろうか．さらに，存在しないと判定された場数が最小のものを考える．このパズルは，小谷によるパズ

合には，正答の方を修正する必要があるが，どのように修ルの分類では，「紙面上で行う抽象的なパズル」のうちの図正すればよいだろうか．我々が調べた限り，このような問形を対象とする「図形パズル」に属する．図形パズルを対

いの解，および，問いそのものに言及した文献は見あたら象にした研究は，小谷らによる 1 枚のポリオミノ図形を，合なかった．本論文では，正答を実現できるピースの集合が同な 2 枚の図形に分割する研究 [9] などがあげられる．裁

存在するか否かを判定するための条件式と，存在する場合

ち合わせパズルを対象とした研究には，Czyzowicz らによにはピースの生成を行う手法を提案する．そうでない場合

る長方形を正方形に裁ち合わせるシステム [4] や，Abbottには，正答の色合いを調整して，ピースを生成可能にする

らによる多角形をヒンジでつながるピースで裁ち合わせる手法の提案も行う．また，いくつかの例題で提案手法の実研究 [1] があげられる．また，ポリオミノ図形を対象にし験を行い，実際にパズルを試作したので報告する．

た研究として，五十嵐らによる全解探索システム [8]，Zhou

2. 関連研究
小谷によって行われたパズルの分類 [10] によると，ポによる複数の図形を裁ち合わせる解を求める研究 [19] などもあげられる．近年では，3 次元の物体を同体積の立方体の形に裁ち合わせる研究も行われている [20]．

リオミノパズルとは，「実世界で与えられた物体を用いる

ここであげたように，ピースを組み合わせて形を作るパ

物体のパズル」のうち，与えられた物体から 1 つの物体

ズルに関して様々な研究が行われているが，本論文で扱うを復元する「合わせるパズル」に分類される．このパズル

ものと同等のパズルを対象にしたものは，我々が調べた限を解くためのソフトウェアには，Gerard によって開発さりでは存在しなかった．

c 2015 Information Processing Society of Japan

1508

情報処理学会論文誌

Vol.56 No.6 1507–1516 (June 2015)

表 1

3. 複数の正答を構成可能なピース集合

M = 3 のときの表記の例

Table 1 Example of notations whenM = 3.

3.1 用語の定義以降での議論を進めるために，まず用語の定義を行う．
本研究で対象とするパズルは N 個の単位正方形をしたピースで構成される．ピースをセルと呼ぶこととする．セルには表面と裏面があり，これをセル面と呼ぶ．セル面にはそれぞれに任意の色を割り当てることができる．すべてのセ
ルを過不足なく使用し，手前を向いたセル面が正答として与えられた色模様と一致している状態を作ることがパズルの目的である．
すべての正答の中で使用されている色の数を L とする．
異なる正答の数を M とし，i ∈ {1, 2, . . . , M } 番目の正答に含まれるセル面の集合を gi で表す．gi の要素となるセル面は，配置される位置および色の情報を持つ．正答はす
べてのセルを過不足なく用いるため |gi | = N である．

図 2

M = 3 におけるベン図と記号による領域の対応付け

Fig. 2 The Venn diagram of M = 3. The correspondences

gi に含まれるセル面の色を抽出した集合を，重複集合 gic

between areas are shown by the symbols.

と表記し，ある色 cj が何枚含まれているかを重複度関数

mgic (cj ) で示す．たとえば，g1 に含まれるセル面の数が 4 で，各セル面の色が {α, α, β, γ} である場合，g1c = {α, α, β, γ}，

mg1c (α) = 2，mg1c (β) = 1，mg1c (γ) = 1 である．また，g1c とg2c の積集合を A1,2 と表記する．たとえば，g1c が先ほどのとおりであり，g2c が {α, α, α, γ} である場合，A1,2 は {α, α, γ}である．さらに，g1c と g2c および g3c の積集合は A1,2,3 のように記す．このようにした場合，集合 A の添え字は自然
数 {1, 2, . . . , M } に対するべき集合 P({1, 2, . . . , M }) から空集合を除いたものと等しく，全部で 2M − 1 通り存在す
る．この集合を UM で表す．つまり，UM の要素 u ∈ UMを用いて，Au =ci∈u gi と定義できる（演算子  は重複集合に対する直積演算を表す）．

図 3

3 つの正答の色集合の例（左）．セル面振り分け問題の解となる例（中）．条件 2 を満たさないためにセル面振り分け問題の解とならない例（右）．

Fig. 3 An example of the sets of colors for three answers (left).
An example of a valid answer of the Venn diagraming problem (center). An example of an invalid answer(right).

さらに，自然数 i を含む集合のみを要素に持つ，UM の(i)部分集合を UM ，UM から要素 {1, 2, . . . , M } を取り除いた

2 は，図 2 に示すベン図で，同じ記号を付けた領域（たと
ものを UMと記し，{1, 2, . . . , M } \ u を ū と記すものとす

えば a1 と a2,3 ）に含まれるセル面の数が等しいことを意味る．これらの例を表 1 に示す．

する．より具体的な例を図 3 に示す．図 3 に示す 3 つの定義 M 集合のベン図へのセル面振り分け問題

正答 g1c ，g2c ，g3c は，そのセル面を 3 集合のベン図の領域に

M 個の集合のベン図の各領域に対して，次の 2 つの条割り振る方法が図中央や図右のように複数存在する．セル件を満たすようにセル面を割り振る問題を「M 集合のベン面の割振りとして a1 を例にあげると，図中央は a1 = {β}，図へのセル面振り分け問題」（以降では，単に「セル面振図右は a1 = {α, β} だが，どちらも A1 = {α, α, β, γ} の部

り分け問題」と記すこともある）と呼ぶこととする．ただ分集合である．そのなかに，セル面振り分け問題の条件をし，ベン図の領域 u に含まれる要素の集合を au とする．

満たす割り振り方（図中央）が存在するため，{gic } はセル∀i ∈ {1, 2, 3, . . . , M },



au = gic

条件 1

面振り分け問題の解を持つといえる．

(i)

u∈UM

∀u ∈ U  M , |au | = |aū |条件 2演算子  は重複集合に対する直和演算を表す．図 2 で3.2 本節の構成
前項では用語の定義を行った．以降では，まず次の定理

は，au とベン図の各領域の対応を示す．図から読み取れる

1 を証明する（3.3 項）．
定理 1 M 種類の正答を構成可能なピース集合の存在のように au は Au の部分集合である．条件 1 は，添え字に i

有無は「M 集合のベン図へのセル面振り分け問題」の解を含む au の集合から gic を復元できることを意味し，条件の有無と同値である．

c 2015 Information Processing Society of Japan

1509

情報処理学会論文誌

Vol.56 No.6 1507–1516 (June 2015)

続いて，M = 3 におけるセル面振り分け問題が解を持つがちょうど同じ数だけ存在する．ここで，u を記述したセための条件式を示す（3.4 項）．さらに，この条件式を判定

ル面と ū を記述したセル面を 1 対 1 で対応させて 1 枚のセ

し，解が存在する場合には，その解の生成を O(N ) で実現

ルを作成すると，作成された各セルは，表面と裏面に，同するアルゴリズムを示す（3.5 項）．最後に，セル面振り分

じ正答番号を割り当てずに済ますことができる．条件 1 よけ問題の結果から，実際の色付き図形パズルを作成する方

り，正答 gi を，数字 i を含むセル面から構成できる．

法について述べる（3.6 項）．

（証明終）以上より，M 種類の正答を構成可能なピース集合が存在

3.3 定理 1 の証明することと，セル面振り分け問題が解を持つことが同値で証明（十分条件）あることが示せたので，定理 1 を証明できた．

M 種類の正答が与えられたときに，そのすべての正答を構成可能な N 枚のセルの集合が存在するならば，セル面

3.4 M = 3 のセル面振り分け問題が解を持つための条
件式

振り分け問題は解を持つことを示す．
与えられた正答 gi に含まれるすべてのセル面に，数字定理 1 より，M 種類の正答を構成できるピース集合が存

i を記録する操作を行うものとする．たとえば，あるセル在するか否かは，セル面振り分け問題の解となる {au } がの表面が g1 と g2 で使用され，裏面が g3 で使用される場存在するか否かである．この判定を行うための単純なアプ合には，表面には数字の 1 と 2 が記録され，裏面には 3 がローチとして，取りうるすべての {au } について，それが記録される．各セル面に記録される数字の集まりは自然数

セル面振り分け問題の解となっているかどうかを調べる方{1, 2, . . . , M } のべき集合の要素である．たとえば M = 3法が考えられる．では，{au } の場合の数は何通りあるだろ3

であれば，セル面に記録される内容の種類は最大で 2 通りで，具体的には以下の 8 通りである．

うか．

au は重複集合 Au の部分集合であるから，au のとりう

φ, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}る場合の数は最大で 2|Au | だけ存在する．その全組合せは最大で

u∈UM 2|Au |だけある（ここでの演算子  は総乗

セル面に記録された数字の集合（べき集合の要素）を uを意味する）．|UM | は 2M である．|Au | の値を評価するのとし，そのセル面の色をベン図の au で表される領域に割は難しいが，セルの数 N に比例すると仮定すると，{au }り振る．セル面振り分け問題の条件 1 は，数字 i が記録さの場合の数は O(22れたセル面が含まれる au の直和集合は gic と等しい，とい

くなると，現実的な時間で判定することが困難になることうことを主張しているので，これは当然成り立つ．

が予想される．

MN) となり，N または M の値が大き1 枚のセルに着目すると，両面合わせて 1 から M までの

そこで，これよりも遥かに小さいオーダ O(N ) で，セル番号が必ず 1 つずつ割り当てられる．裏面と表面の両方に面振り分け問題が解を持つかを簡単に判定できる条件式を同じ数字が記録されることはないため，一方の面に割り当示す．なお，ここで示すのは M = 3 についてのみである．

てられた数字の集合を u とすると，他方の面に割り当てら

M = 1，2 の場合は解を持つことが自明であり，M > 3 にれた数字の集合は {1, 2, . . . , M } \ u である．正答数が 3 のついては本論文では未解決である．

ときを例にあげると，各セルの両面に割り当てられる数字

さて，一般性を失うことなく与えられた 3 つの正答のうには，表と裏を区別せずに次の 4 通りの組みが存在する．

ち，任意に選択した 2 正答を g1 ，g2 ，残りの正答を g3 と({1}, {2, 3}), ({2}, {1, 3}), ({3}, {1, 2}), (φ, {1, 2, 3})
定 義 よ り ，a{1,2,3,...,M }\u = aū で あ る か ら ，つ ね に|au | = |aū | を満たす（たとえば，{2} の出現回数と {1, 3}の出現回数は同じであることを意味する）．よって，セル
面振り分け問題の条件 2 が成り立つ．

（証明終）

証明（必要条件）
セル面振り分け問題の解となるようなセル面の割り振りする．ここで，3 つの正答に対するセル面振り分け問題が解を持つ条件は，次式で与えられる．

 (2)  (2) (2) N −  a1  a2  g3c  ≤ a1,2 (1)

右肩の添え字の (2) は，2 つの正答を対象としたセル面
振り分け問題で用いた集合であることを明示的に示すためのものであり，以降では正答数が 3 の場合の議論を進める．

 (2)(2) 

左辺の  a1  a2


(2)
(2)
 g3c  は，a1 または a2 に含まれるセを表す {au } が存在するならば，すべての正答を構成可能

ル面のうち，g3c で使用できる数（重複集合の演算であるこ

な N 枚のセルの集合が存在することを示す．

とに注意されたい．
）であり， a1  a2

 (2)

(2) 

 g3c = a1,3  a2,3

ベン図の各領域を，図 2 に示すような数字の集合によっを満たすよう a1,3 と a2,3 を割り当てられる．左辺全体でて区別する．各領域に含まれるすべてのセル面に，この数は，a1 または a2 に含まれない g3c のセル面の枚数を示

字の集合 u を記録した場合，セル面振り分け問題の条件 2

し，そのセル面を a3 に割り当てる．一方，右辺は a1,2 により，u = 1, 2, . . . , M 以外の場合は，ū を記述したセル面

割り当てられる最大のセル面の枚数，すなわち g3c のため

c 2015 Information Processing Society of Japan


(2)

(2)

1510

情報処理学会論文誌

Vol.56 No.6 1507–1516 (June 2015)

表 2 色 α の割り振り例

Table 2 Examples of allocations of color α.

に対して，(表, 裏) = (γ, α)，(β, δ)，(ε, α) のような色を割
り当てることで，3 つの正答を構築できる．
式 (2) の左辺が最大となるように各正答の色集合をベン図の領域に割り振るには，色ごとに次に示す方法を適用す
図 4 ある 3 つの正答（左）に対する色の集合と式 (2) 左辺の各項の関係を色 α の割当て方に着目して見た例（中，右）Fig. 4 A three answers set (left) and the illustration of therelation between the left-hand side of Eq. (2) and theVenn diagraming of color α (center, right).

ることで実現できる．具体例を表 2 に示す．

Case1 「g3c に含まれる色 α のセル面の数  g1c と g2c に含まれる色 α のセル面の数の和」である場合，すべて
(2)

(2)

a1 と a2 に配分し，できるだけ a1,3 と a2,3 に割り当てられる枚数を増やす．

に自由に割当てを調整できるセル面の枚数を示す．割り当(2)(2)
てられていない a1 と a2 のセル面をそれぞれ a1 ，a2 に(2)割り当てると，式 (1) の右辺が左辺と等しければ a1,2 を直接 a1,2 に，右辺が左辺より大きければ a3 と同じ大きさだ(2)
け a1,2 の要素を a1,2 に割り当て，その余りを a1 と a2 に分離して割り当てることで，M = 3 におけるセル面振り分

Case2 「g3c に含まれる色 α のセル面の数  g1c と g2c に含まれる色 α のセル面の数の差」である場合，できるだ(2)

け a1,2 に統合して自由に割当てを調整できるセル面
(2)

(2)

の枚数を増やし，a1 もしくは a2 に溢れたセル面を

a1,3 もしくは a2,3 に割り当てる．
Case3 「g1c と g2c に含まれる色 α のセル面の数の差 < g3c

け問題は解を持つことができる．

に含まれる色 α のセル面の数 < g1c と g2c に含まれる色

3.5 M = 3 における，セル面振り分け問題が解を持つた

うど a1,3 と a2,3 に割り当てられるような統合・分離を

α のセル面の数の和」である場合，上記の中間で，ちょ行う．具体的には mg3c (α) − |mg1c (α) − mg2c (α)| が不足めの条件式の判定と，解の導出
式 (1) の項を移動させて，次のように変形する．

 (2)   (2)a  +  a  a(2)  g3c  − N ≥ 0
1,2

1

2

分なので，この値を超えない範囲で最大の分離を行う．

(2)

(2)
(2)
図 4 に示すように，a1,2 の 1 枚のセル面を a1 および
 (2) (2)
a2 に割り振ると，a1,2  の値が 1 減少するが，割り振った
あとの 2 つのセル面が g3c に含まれるのであれば，第 2 項
 (2) a  a(2)  g3c  の値が 2 増える．つまり，左辺の値を 112(2)増やすことができる．左辺の値が最大になるのは，a1 お(2)
よび a2 に割り振った 2 つのセル面が g3c に含まれる限り，この割り振り操作を最大回数行ったときである．このようにして左辺の値を最大にしても 0 未満である場合は，セル
面振り分け問題は解を持つことができないと判定できる．
なお，上記の操作は色ごとに独立して行い，すべての色に以上をまとめると，g1 ，g2 に対するセル面振り分け問題

 (2) の解となる au(2)の a1,2 が含むべき色の枚数は，色ごとに次式で記述できる．なお，g1c ，g2c ，g3c に含まれる各色 cjの枚数を gi,j (= mgic (cj )) として記述する．

ma1.2 (cj )
(3)
⎧
⎪
0
(g1,j + g2,j ≤ g3,j )⎪⎪⎪⎪(g3,j ≤ |g1,j − g2,j |)⎨ min{g1,j , g2,j }=(g3,i − |g1,j − g2,j |)
⎪
,
g
}
−
min{g
1,j 2,j⎪⎪2⎪⎪⎩(|g1,j − g2,j | < g3,j < g1,j + g2,j )
(2)

(2)

この方法で得られる a1,2 を用いて，a1
(2)

(2)

= g1c \ a1,2 ，対して条件式を満たす場合のみ，セル面振り分け問題は解

a22 = g2c \ a1,2 を定義し，式 (1) が満たされるならば，セルを持つということができる．

面振り分け問題が解を持つ．

図 4 の例では，左側のベン図では，左辺が −1 となり，

この判定は前処理として，各正答に含まれる色の枚数をカ式 (2) の関係を満たさない．一方で，右側のベン図では左ウントする．これには O(N ) の計算量を必要とする．実際の辺が 0 となり式 (2) の関係を満たす．右側のベン図に示す

判定は，色の数 L だけ繰り返されるため O(L) である．色のようなセル面の割り振りを行った場合は，たとえば各セル数の最大値は 3N であるため，全体の計算量は O(N ) である．

c 2015 Information Processing Society of Japan

1511

情報処理学会論文誌

Vol.56 No.6 1507–1516 (June 2015)

3.6 セル面振り分け問題の解からセルを作成する方法

離は無限大とする．これはその 2 色を別の色に置き換えて

正答 {gi } の色の集合 {gic } から，セル面振り分け問題のも，セル面振り分け問題の結果が変わらないためである．

解である {au } が与えられたときに，N 個のセル（パズル

それ以外のときは 3 次元ベクトル間のユークリッド距離とのピース）は次の方法で作成する．まず，u ∈ U M の各 auと aū 間で要素の 1 対 1 の対応を任意にとり，この 2 つの色をセルの表と裏に割り当てる．a1,2,...,M に含まれるセル
面は，反対側の面を使用しないセルであるため，使用しなする．
中間色 c3 は以下の式で定める．

c3 =

|C1 |
|C2 |
c1 +
c2
|C1 | + |C2 ||C1 | + |C2 |(5)

い方の面には任意の色を適当に割り当てる．このようにし
このアルゴリズムの前処理として，色の値を類似度で並て，計 N 個のセルを得る．

び替えるのに O(L log L) かかるが，距離の近い 2 色を見つ

4. 色の調整

けるのに O(L)，ループの実行数を O(L) と仮定すると，全

本節では，セル面振り分け問題が解を持たないような正答が与えられた場合に，正答に含まれるセル面の色数を減らすことで，解が存在するように調整する手法を提案する．
次の定理 2 より，色数を減らすことで必ずセル面振り分け問題が解を持つようにできる．
定理 2 セル面振り分け問題が解を持たない場合には，正答に含まれる色を減らすことで，必ずセル面振り分け問

体で O(L2 ) の計算量である．データの持たせ方を工夫することでさらに計算量を減らすことが可能かもしれないが，
ここではこれ以上は議論しない．

5. 実験
5.1 セル面振り分け問題の全探索と提案手法の比較
入力として与えられた正答集合がセル面振り分け問題の解を持つか否かの判定を全探索で行うプログラムと，本論題が解を持つようにできる．
定理 2 が真であることは，正答に含まれる色の数がわず
か 2 色 {α, β} であれば，各セルの片面に α，反対の面に βを割り当てることで，すべての正答を構成できることから自明である．
与えられた {gic } がセル面振り分け問題の解を持たない場合は，できるだけ元の色を減らすことなく，セル面振り分け問題が解を持つ色の集合に調整することが望ましい．
そのため，1 色ずつ減色を行う方法として，以下のアルゴ
リズム 1 を提案する．

文で提案する手法で行うプログラムを作成し，計算時間を比較する実験をした．どちらのプログラムも，解を持たないと判定した場合は，4 章で述べた方法で色の調整を行う．
実験はメモリ 8 GB，Intel(R) Core(TM) i7-4700MQ CPU@ 2.40 GHz の PC 上で行った．OS は Windows 8.1 でプ
ログラムは Java 言語で開発した．
まず，入力とする正答として，次のようにセル数が 4 だ
けの簡単なものを 3 つ用いた．

g1c = {α, α, β, γ}, g2c = {δ, δ, ε, ζ}, g3c = {α, β, δ, η}

アルゴリズム 1 減色の方法

その結果，このままでは解を持たないと判定され，減色

WHILE セル面振り分け問題が解を持たない{gic } に含まれる色から，距離 d(c1 , c2 ) を最小にする
2 色 c1 ，c2 を見つける{gic } に含まれる c1 あるいは c2 の色を持つセル面集
合を，それぞれ C1 ，C2 とする

C1 と C2 に含まれる要素数を重みとして，新しい中間色 c3 を決定する処理が 1 回行われた．この処理を全探索では 48 ミリ秒，提案手法では 8 ミリ秒で終えた．提案手法の方が速いが，その差は僅かであったため，上記の 3 つの正答に対して，色の構成比率を保ったままでセル数を 3 倍の 12 とし，同じ実験を行った．その結果，全探索では 96,622 ミリ秒，提案手法では 8 ミリ秒を要した．全探索の時間が大幅に増えたのは，セルの数が 3 倍に増えただけでも，組合せの数がC1 と C2 に含まれるセル面の色を c3 とする

大きく増えたためと見られる．セル数をこれ以上に増やす

END WHILEと，全探索では現実的な時間で判定するのが困難になると色を RGB 色空間内のベクトル ci ∈ [0, 1] × [0, 1] × [0, 1]予想される．提案手法の処理時間がセル数を増やしても変と見なし，アルゴリズム 1 で用いられている距離関数 d をわらなかったのは，判定に要する計算量が色数のみに依存

以下のように定義する．

し，セル数には依存しないためである．

d(c1 , c2 )⎧⎪⎨infinity=⎪⎩
c1 − c2 (4)
c1 ，c2 が共通する正答ただ 1 つだけに含まれる場合続 い て ，前 述 の 3 つ の 正 答 に 対 し て ，新 し く g4c ={α, ζ, ζ, ι} を加えた 4 つの正答に対しての実験を行った．
提案手法は正答数が 3 の場合のみを対象としているため，

4 つの正答の判定は全探索のみで行った．セル数はわずか
それ以外

c1 ，c2 が共通する正答ただ 1 つのみ含まれる場合，距c 2015 Information Processing Society of Japan

4 であったが，処理に要した時間は 621,712 ミリ秒であった．その中で減色処理は 3 回行われ，その度に組合せ数が1512

情報処理学会論文誌

Vol.56 No.6 1507–1516 (June 2015)5.24 × 105 ，8.39 × 106 ，2.83 × 107 と増加することを確認した．これは，共通する色が多いほど，A1,2 などの，複数表 3

ユーザテストでの解答時間

Table 3 Time taken to complete a puzzle in our user test.

の正答の共通領域が大きくなり，組合せの数が大幅に増えたものと考えられる．この共通領域の大きさは，正答の状態によって大きく異なるため，一概にいうことはできない
が，正答を 4 つ持つ問題を扱うには，セルの数が十分に少なく，かつ共通する色の種類が少ない必要があると考えられる．

実験 4 はグラデーションをつけることで色数を増やした．
その結果，色数を増やした方が減色の影響を小さく抑えら

5.2 提案手法によるセル面振り分け問題の解法れることが確認できた．これは，減色処理は同じ色のセル

前項による実験で，全探索ではセル数が 12 であっても，の色を一度にまとめて変更してしまうため，少ない色数だ

必要な処理に要する時間が大きいことを確認した．ここでと減色の影響が広範に及ぶためと考えられる．対策としは，提案手法を用いることで，セル数が 64，430，2,400 とて，一度に複数のセルの色を変更するのではなく，1 つず

十分大きな例を用いて実験を行い，計算時間および減色に

つセルの色を変更しながらセル面振り分け問題の解の有無よる影響について検証した．実験の環境は前項と同じであについて調べる方法が考えられる．

る．この結果を表 4 に示す．表中の「減色数」は入力と出実験 5 は計算時間の評価のために，2,400 セルという，パ力における色数の差を示し，「色距離」は減色処理によっズルにするには現実的でない大型の正答を用いたものであて，セル面あたり，どれだけ異なる色に変更されたかを示る．この例でも計算時間は 1 秒未満であり，提案手法は十す，次式で定める値（0 から 1 の範囲を取る）である．値

分高速であることを確認した．

が小さいほど色の変化が小さいことを表す．
1
√
3 NM

5.3 パズルとしての利用と考察

×





表 4 に示した例題の中で，実験 1 のパズルを実際に制|減色前の色 − 減色後の色|(すべての正答) (正答に含まれるセル面)

作し評価を行った（図 1）．解き手が正答 1 の復元を試みるとき，まず正答 1 のみに含まれる色および，正答 1 に含(6)

まれない色を持つセルは，使用する面をただちに決定でき「色の割り振り例」ではセル面振り分け問題の解の例にる．それ以外のセルは，どちらの面も正答 1 に含まれるた

ついて，ベン図の各領域に割り振られるセル面の色の種類

めに，どちらを表にするべきかで悩むことになる．どちらと枚数を示す．

かを仮定して復元を進めていくと，たとえば，最後に残っ(1)
実験 1 の正答 1 を例にあげると，{au }，u ∈ UM の集合

た 1 ピースが期待する場所に配置できない（欲しい色が表に含まれる色とその枚数を数えあげ，出力された正答に含にも裏にもない）というケースが発生する．その場合は，まれるセル面と比較することで，間違いなく正答 1 を復元

すでに配置済みのピースの裏側をそれぞれ確認し，残ったできることを確認できる（セル面振り分け問題が解を持つ

1 ピースとどれかを交換する必要が生まれる．解き手は，ための条件 1）
．また，au と aū に含まれるセル面の数が一一度に片方の面しか見られないため，裏側の色を把握して致することから，ある正答に含まれる 2 つのセル面が，同いなければ，欲しい裏側の面を探すのに悩むことになる．

じセルの表と裏に割り当てられることを回避できることを制作したパズルを 4 名の被験者が完成させるのに要した時確認できる（セル面振り分け問題が解を持つための条件 2）．

間を表 3 に示す．パズルを解くのにある程度の試行錯誤と実験 1，2 は，類似する色を持つ 2 つの正答に対して異時間を要したことから，十分に遊べるものであったと評価

なる 3 つ目の正答を与えたものである．実験 2 は実験 1 よできる．解答時間の平均は正答 2 が最も長く，これは共通

りも色の変化が大きい（減色の影響が大きい）ことを確認して利用する色（a1,2 ，a2,3 の要素）が多いため，どちらのできる．実験 1 は第 3 の正答で使われている色が第 2 の正面を利用するのか分からないピースが増えることが原因で答のものと類似しているが，実験 2 の第 3 の正答は第 1，あると推測できる．この点をあらかじめふまえて使用する

2 の正答と大きく異なる色を持っている．そのため実験 2

色を決めることで，パズルの難易度の調整が可能になるとでは，正答 1，2 の間で色を統合する作用が働いたものと考えられる．

考えられる．このことから，3 つの正答を用意する際には，なるべく共通の色を使った方が色の変化を抑えられるといえる．

6. 結論と今後の課題
本論文では，両面に色の付いた正方形をピースとし，複実験 3，4 は，セル数が 430 の正答の塗り方を変えて，そ数の正答を持つ組合せパズルについて議論し，提案した手の違いを確認した例である．実験 3 は少ない色数で塗り，法を実装したシステムの開発を行った．システムの入力は，

c 2015 Information Processing Society of Japan


1513

情報処理学会論文誌

Vol.56 No.6 1507–1516 (June 2015)

表 4

正答数が 3 の例

Table 4 Results of puzzles that have three answers.

c 2015 Information Processing Society of Japan

1514

情報処理学会論文誌

Vol.56 No.6 1507–1516 (June 2015)

セル数が等しい 3 または 4 種類の正答であり，出力は，その正答のセル面振り分け問題の解と，必要があれば色合い[10]を調整した後の正答である．今回実装したシステムには，[11]次の特徴がある．

• 正答数が 3 であれば，O(N ) の計算量の判定式を用い[12]て，セル面振り分け問題の解を持つか判定し，解を持つ場合は解を出力する．

• 4 正答以上であれば，O(22MN) の計算量の全探索を用[13]

いて，セル面振り分け問題の解を得る．

• 色の調整には，類似する 2 色を中間色に置き換える．

[14]

このシステムを用いて，実際に複数のパズルを作成できること，それが十分に考えながら解くことができるものであることを確認した．しかしながらセル面振り分け問題が解を持たない場合の色の調整方法に関しては，その評価方

[15]
[16]

法も含めたより厳密な議論が必要と考えられる．また，4正答以上の場合には，セル面振り分け問題が NP 完全であるかもしれないが，本論文では示せていない．

[17]
[18]

パズルとしての面白さを向上させるためには，次のような課題があげられる．

• ペントミノのように，複数のセルが連結したピースの

[19]

導入．

• パズルの難易度の定量化と難易度の調整方法の開発．
本研究を通して，新しいタイプの組合せパズルの提案を行うことができた．またそれが興味深い問題を内包してい[20]

pp.47–54 (2005).
小谷義行：ゲーム情報学：2. ゲーム情報学におけるパズ
ル研究，情報処理，Vol.53, No.2, pp.101–111 (2012).
是川 空，小谷善行，柴原一友，五十嵐力：BitsPuzzle の解答作成と問題作成，ゲームプログラミングワークショッ
プ 2006 論文集，pp.187–190 (2006).
Lo, K.-Y., Fu, C.-W. and Li, H.: 3D polyomino puzzle, ACM Trans. Graph., Vol.28, No.5, pp.157:1–157:8(2009).
村井保之，巽 久行，徳増眞司：位相的特徴量に基づく
平面ポリオミノ箱詰め問題の解法，情報処理学会論文誌，
Vol.43, No.12, pp.4009–4022 (2002).
西岡 潤，堀山貴史：pmg タイリング可能なポリオミノの列挙，研究報告アルゴリズム（AL），Vol.2014-AL-148,
No.18, pp.1–8 (2014).
Rover, A.: Burr Tools, available from http://burrtools.
sourceforge.net/ (accessed 2014-10-01)．
Song, P., Fu, C.-W. and Cohen-Or, D.: Recursive interlocking puzzles, ACM Trans. Graph., Vol.31, No.6,
pp.128:1–128:10 (2012).
株式会社テンヨー：ジガゾーパズル，入手先 http://www.
tenyo.co.jp/jigazo/（参照 2014-10-01）．
Xin, S.-Q., Lai, C.-F., Fu, C.-W., Wong, T.-T., He, Y.
and Cohen-Or, D.: Making burr puzzles from 3D models,
ACM Trans. Graph., Vol.30, No.4, pp.97:1–97:8 (2011).
Zhou, Y. and Wang, R.: An algorithm for creating geometric dissection puzzles, Proc. Bridges 2012: Mathematics, Music, Art, Architecture, Culture, pp.49–56(2012).
Zhou, Y., Sueda, S., Matusik, W. and Shamir, A.: Boxelization: Folding 3D Objects Into Boxes, ACM Trans.
Graph., Vol.33, No.4 (2014).

ることを確認できた．
参考文献

山本 陽平

[1]

2011 年筑波大学情報学群情報科学類

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Abbott, T.G., Abel, Z., Charlton, D., Demaine, E.D.,
Demaine, M.L. and Kominers, S.D.: Hinged dissections
exist, Proc. 24th Annual Symposium on Computational
Geometry, pp.110–119 (2008).
安倍泰孝，原口和也，丸岡 章：計算ブロックパズルの生成アルゴリズム，情報処理学会研究報告，GI，[ゲーム情報学]，Vol.2011-GI-25, No.6, pp.1–7 (2011).
Alejandro, E. and Frank, R.: Domino Tatami Covering
Is NP-Complete, 24th International Workshop, IWOCA
2013, No.10, pp.140–149 (2013).
Czyzowicz, J., Kranakis, E. and Urrutia, J.: Rectilinear glass-cut dissections of rectangles to squares, Applied Mathematical Sciences, Vol.1, No.52, pp.2593–
2600 (2007).
Gerard: Polyomino Solver, available from http://gp.
home.xs4all.nl/Site/Polyomino Solver.html (accessed
2014-10-01)．
Golomb, S.W.:
Checkerboards and Polyominoes,
The American Mathematical Monthly 61, 10 (Dec),
pp.287–294 (1954).
Golomb, S.W.: Polyominoes: Puzzles, Patterns, Problems, and Packings, Princeton University Press, Revised
edition (1994).
五十嵐力，但馬康宏，小谷善行：裁ち合わせパズルの重複解なし全解探索システム，ゲームプログラミングワー
クショップ 2006 論文集，pp.40–47 (2006).
小谷義行：図形合同分割パズルの自動生成，情報処理学会
研究報告，GI，[ゲーム情報学]，Vol.2005-GI-014, No.87,

c 2015 Information Processing Society of Japan

卒業，2015 年，同大学大学院システム
情報工学研究科コンピュータサイエン
ス専攻修了．修士（工学）．同年株式
会社技研製作所入社．パズルや折り紙の理論に関する研究を行っている．

金森 由博 （正会員）
2009 年 3 月東京大学情報理工学系研
究科コンピュータ科学専攻博士課程修了．博士（情報理工学）．同年 4 月より筑波大学に勤務し，現職は筑波大学
システム情報系・助教．コンピュータ
グラフィクス，特にレンダリング技術に興味を持つ．現実世界の現象を再現する画像編集技術
や，イラストやアニメの制作支援技術に取り組んでいる．

ACM，画像電子学会，芸術科学会各会員．

1515

情報処理学会論文誌

Vol.56 No.6 1507–1516 (June 2015)

三谷 純 （正会員）
2004 年東京大学工学部精密機械工学科博士課程修了．博士（工学）．理化
学研究所研究員を経て，2006 年より筑波大学に勤務し，現職は筑波大学シ
ステム情報系教授．コンピュータグラ
フィックスにおける形状モデリングの研究に従事．最近は折り紙で作れる幾何形状の設計技法に関する研究等を行っている．

c 2015 Information Processing Society of Japan

1516