一般化マクマホン立方体パズルの 問題例生成

Presentation on theme: "一般化マクマホン立方体パズルの 問題例生成"— Presentation transcript:

1 一般化マクマホン立方体パズルの 問題例生成
原口和也 柿崎幸大 丸岡章 石巻専修大学 理工学部 情報電子工学科

2 マクマホン立方体 各面が相異なる6色で彩色された単位長の立方体 使える6色は決められているものとする
回転したものも同一とみなすと30通りの彩色 適当な添字を付けてキューブj(=1,...,30)と呼ぶ 上面に１色固定 側面: (4-1)!=6通り 対面: ５通り 56=30通り

3 最初のマクマホン立方体パズル モデル 残り29個で長さ2の立方体を作れ モデルとして与えられたキューブと同じ彩色
内部では同じ色の面同士が接する

4 Conwayによる解法

5 本研究で考えるパズル キューブ集合 S (|S|n3) 整数 n2 モデル（キューブj） 作れるならば 「Sは長さnのキューブjを
構成可能」 キューブ集合Sから長さnの立方体を作れ モデルとして与えられたキューブjと同じ彩色 内部の色は問わない

6 関連研究 [Berkove et al., 2008] n3 ならば任意のキューブ集合 S(|S|n3) から
S は長さ 2 のキューブ j を構成可能  長さ n のキューブ j も構成可能 |S|27  S は長さ 2 のあるキューブを構成可能 頂点：3色 (長さ2の解を割当) 辺：2色 n 2 面：1色

7 研究成果 (n=2) 12 8 キューブ集合の空間 任意のキューブを構成可能 （万能キューブ集合） 集合の サイズ どのキューブも
構成不可能 12 8 キューブ集合の空間

8 用語の準備：色トリプル 頂点に接する3面の色を (赤,水色,緑) 時計回り順に並べた3つ組 開始面によって3通り 同値とみなす
1つのキューブは 8つの色トリプルを持つ

9 キューブ集合Sはキューブjを構成できるか?
構成可能性の判定 キューブ集合Sはキューブjを構成できるか? Sに含まれるキューブ キューブjの色トリプル (赤,水色,緑) (赤,紫,水色) (赤,緑,橙) (赤,橙,紫) (青,緑,水色) (青,水色,紫) サイズ8のマッチングが存在  構成可能 (青,橙,緑) ... ... (青,紫,橙)

10 万能キューブ集合の判定 ... ... 最小サイズの 万能キューブ集合を 数理計画で求められる 30個すべての生成部分グラフにおいて
Sに含まれるキューブ キューブ1の色トリプル 最小サイズの 万能キューブ集合を 数理計画で求められる キューブ2の色トリプル ... ... キューブ30の色トリプル 30個すべての生成部分グラフにおいて サイズ8のマッチングが存在  S は万能キューブ集合

11 Conways tableとの関係

12 Conways tableとの関係 色トリプルを共有しない  キューブ構成に使えない

13 各行/列から2個づつ選ばれることの必要性 5個選ばれる行/列が存在 3, 4個選ばれる行/列が 存在する場合も同様

14 今後の課題 Conway’s Table における 最小万能キューブ集合の必要十分条件? 各行各列からちょうど2個ずつ（⇒は証明済）
対称行列（not yet）

15 任意のキューブを構成可能 （万能キューブ集合） (n=2) ? <27 22 どのモデルも 構成不可能 12 8 キューブ集合の空間