経営情報演習 A
パズルのモデル化
情報学部 経営情報学科 堀田敬介
2012/5/15,Tue.
Contents
• パズルを解こう
– はじめに
• 解けないパズルを解かずに知る
– パズルのモデル化
• 魔方陣
• 数独
• ペグソリティア
• ノノグラム
Puzzle を解こう
• はじめに
– 床にタイルを敷き詰めたい．できますか？ ただし，
• タイルは下の 1 種類のみで重ねたり切っては駄目
• 床の左上端・右下端には柱があるのでタイルは置けない
床
タイル
Puzzle を解こう
• はじめに
– 床にタイルを敷き詰めたい．できますか？ ただし，
• タイルは下の 1 種類のみで重ねたり切っては駄目
• 床の左上端・右下端には柱があるのでタイルは置けない
床
タイル
パズルが解ける かどうかを，説 明・説得するには
どうすれば？
Puzzle を解こう
• 魔方陣
– 3 × 3 のマスに， 1 ～ 9 の数字を 1 マスに 1 つ入れる
– ただし，縦・横・斜めの合計を全て同じにする
4 9 2 3 5 7 8 1 6 Puzzle を解こう
• 魔方陣 (cf.[5])
– ヒントと解答
• 3 つの数字の和は「 15 」（∵ (1+2+…+9)/3=15 ）
–
故に，「1, 2, 3
」から2
数を同一行・同一列・同一斜めには置けない–
故に，「7, 8, 9
」から2
数を同一行・同一列・同一斜めには置けない• 3 つの数字を足して 15 にする和のパターンは，縦 3 列，横 3 行，左右両斜 めの全部で 8 つ必要
• 3 つの数字を足して 15 にする 1 ～ 9 の数の組合せは以下の 8 通りだけ
– 1 + 5 + 9, 2 + 5 + 8, 3 + 5 + 7, 4 + 5 + 6 – 1 + 6 + 8, 2 + 4 + 9, 2 + 6 + 7, 3 + 4 + 8
• 魔方陣の各マスについて， 8 つの和のパターンに使われる回数は
–
中央マスが4
回（縦・横・両斜め)
，角が3
回（縦・横・斜め），他2
回（縦・横）• 3 数和に 4 回登場する数は「 5 」だけ， 3 回は「 2, 4 , 6 , 8 」 , 2 回は「 1, 3, 7, 9 」
→
故に，中央は必ず5, 4
角には必ず「2, 4, 6, 8
」,
他は必ず「1, 3, 7, 9
」が入る→
故に，右上に「2
」，左上に「4
」とすれば他は自明（答えはこの1
種類だけ）（他の答えは，この解の対称・鏡像しかない）
Puzzle を解こう
• 数独
– 9 × 9 のマスに， 1 ～ 9 の数字を 1 マスに 1 つ入れる
– ただし，縦・横・ブロックに 1 ～ 9 の数字は 1 つずつ
Puzzle を解こう
• 数独 (cf.[3])
– 定式化： {0,1}- 整数計画問題 （ IP; Integer Programming)
– {0,1}- 変数を 9 × 9 × 9=729 個用意
. . 0
) k
j]
([i, ] 1
, ,
[ i j k o w
x に を入れる
i
は行，j
は列を表し，k
は代入する数値とする 例）x[2,7,4]=1 … 2
行7
列のマスに4
を入れるx[6,1,3]=0 … 6
行1
列のマスに3
を入れない 制約条件1
：各行に1
～9
を1
つ（729
個）制約条件
2
：各列に1
～9
を1
つ（729
個）制約条件
3
：各枠に1
～9
を1
つ（729
個）目的関数：なんでもよい
Puzzle を解こう
• ペグソリティア
– ペグ（黒）があるマスとないマス（白）が与えられる – ペグをジャンプさせて望む配置に出来るか？
● ● ●
● ● ●
● ● ● ○ ● ● ●
● ● ○ ○ ○ ● ●
● ● ● ○ ● ● ●
● ● ●
● ● ●
● ● ○
ジャンプ
○ ○ ●
ジャンプは，
縦（上方向・下方向）
横（左方向・右方向）
の任意の
3
マスで上記配置の時にで きる．左の例では，例えば上方向に は3
カ所ジャンプ可能な箇所があるPuzzle を解こう
• ペグソリティア (cf.[4])
– 補配置：ペグのあるなしが逆転している配置
– Question? ：「ジャンプ操作」を繰り返し使って，「初期配 置（左）」から「その補配置（右）」に移行できるか？
● ● ●
● ● ●
● ● ● ○ ● ● ●
● ● ○ ○ ○ ● ●
● ● ● ○ ● ● ●
● ● ●
● ● ●
○ ○ ○
○ ○ ○
○ ○ ○ ● ○ ○ ○
○ ○ ● ● ● ○ ○
○ ○ ○ ● ○ ○ ○
○ ○ ○
○ ○ ○ 補
配
置
Puzzle を解こう
• ペグソリティア (cf.[4])
– パゴダ関数： pag(p)… 配置 p に対する値を返す関数
● ● ●
● ● ●
● ● ● ○ ● ● ●
● ● ○ ○ ○ ● ●
● ● ● ○ ● ● ●
● ● ●
● ● ●
‐1 0 ‐1
1 1 1
‐1 1 0 1 0 1 ‐1
0 1 1 2 1 1 0
‐1 1 0 1 0 1 ‐1
1 1 1
‐1 0 ‐1
配置 p s pag(p s )=4
ペグのあるマスの数値の和
○ ○ ○
○ ○ ○
○ ○ ○ ● ○ ○ ○
○ ○ ● ● ● ○ ○
○ ○ ○ ● ○ ○ ○
○ ○ ○
○ ○ ○
Puzzle を解こう
• ペグソリティア (cf.[4])
– パゴダ関数： pag(p)… 配置 p に対する値を返す関数
‐1 0 ‐1
1 1 1
‐1 1 0 1 0 1 ‐1
0 1 1 2 1 1 0
‐1 1 0 1 0 1 ‐1
1 1 1
‐1 0 ‐1
配置 p f pag(p f )=6
ペグのあるマスの数値の和
‐1 0 ‐1 1 1 1
‐1 1 0 1 0 1 ‐1
0 1 1 2 1 1 0
‐1 1 0 1 0 1 ‐1
1 1 1
‐1 0 ‐1
Puzzle を解こう
• ペグソリティア (cf.[4])
– パゴダ関数： pag(p)… 配置 p に対する値を返す関数
どの連続する
3
数（a, b, c
）についてもa + b ≧ c
が成り立つ（故に
a ≦ b + c
も成立）〔性質〕
1 1 2 1 + 1 1 ≦ 1 + 2 ≧ 2
● ● ○
ジャンプ
○ ○ ●
a + b ≧ c
なので，ジャンプ操作に対し，
pag(p)
は単調非増加配置
p
1―[
ジャンプ]→
配置p
2 のとき，pag(p
1) ≧ pag(p
2)
Puzzle を解こう
• パゴダ関数とジャンプ操作，配置転換
1 2
3 4 5 6
7 8 9 10
11 12
● ●
● ● ○ ●
● ○ ○ ●
● ●
1 1 1 0 0 1 1 0 1 1 1 1
p
s● ●
○ ○ ● ●
● ○ ○ ●
● ●
1 1 1 0 0 1 1 1 0 0 1 1
p
t● ● ○
配置を表すベクトル ジャンプを表すベクトル
○ ○ ●
3 4 5
3 4 5
0 0 0 0 0 0 0 1 1 1 0 0
a
1配置
p
sから1
回のジャンプ（a
1） で配置p
tに移る ということはp
t= p
s －a
1 で表せるPuzzle を解こう
• ジャンプ操作
– 全てのジャンプベクトル
1 2
3 4 5 6
7 8 9 10
11 12
● ● ○
○ ○ ●
3 4 5
3 4 5
0 0 0 0 0 0 0 1 1 1 0 0 a
1
0 0 0 0 0 0 1 1 1 0 0 0 a
2
0 0 0 1 1 1 0 0 0 0 0 0 a
3
0 0 1 1 1 0 0 0 0 0 0 0 a
4
0 0 0 0 0 0 1 1 1 0 0 0 a
6
0 0 0 0 0 0 0 1 1 1 0 0 a
5
0 0 1 0 1 0 0 0 0 0 0 1 a
7
0 0 1 1 0 0 0 0 0 0 0 1 a
8
0 0 0 0 1 0 0 0 1 0 0 1 a
9
0 0 0 1 0 0 0 1 0 0 0 1 a
10
1 1 0 0 0 0 0 0 0 0 0 1 a
12
0 0 0 1 0 0 0 1 0 0 1 0 a
11
0 0 0 0 1 0 0 0 1 0 0 1 a
13
0 0 0 1 0 0 0 1 0 0 1 0 a
15
0 1 0 0 1 0 0 0 1 0 0 0 a
14
1 0 0 1 0 0 0 0 0 0 0 1 a
16●
●
○
1 4 8
○
○
●
1 4 8
1 2
3 4 5 6
7 8 9 10
11 12
Puzzle を解こう
• ジャンプ操作
– 初期配置 p
sから最終配置 p
fまでの全てのジャンプ
● ●
● ● ○ ●
● ○ ○ ●
● ●
1 1 1 0 0 1 1 0 1 1 1 1 p
s○ ○
○ ○ ● ○
○ ● ● ○
○ ○
0 0 0 1 1 0 0 1 0 0 0 0 p
f
0 0 0 0 0 0 0 1 1 1 0 0 a
1
0 0 0 0 0 0 1 1 1 0 0 0 a
2x
1 －x
2 －…
－x
16
1 0 0 1 0 0 0 1 0 0 0 0 a
16p
f= p
f-1 －a
i1= p
f-2 －a
i2 －a
i1= p
f-3 －a
i3 －a
i2 －a
i1…
= p
s －a
in －…
－a
i3 －a
i2 －a
i1－
＝
この中にa1がx1個含まれ，a2がx2個含まれ，…
Puzzle を解こう
• ジャンプ操作による配置転換実行可能性
– 初期配置 p
sから最終配置 p
fまでの全てのジャンプ
a
1x
1+ a
2x
2+ …+ a
16x
16= p
s－ p
f, x
1, x
2, …, x
16≧ 0
従って，この線形不等式系が解 x を持たないなら，初期配置 p
sから最終配置 p
fへジャンプで到達不可能．
注）解 x を持っても到達可能とは限らない（ジャンプの順番を考慮してないから）
max. 0x
1+ 0x
2+ …+ 0x
16s.t. a
1x
1+ a
2x
2+ …+ a
16x
16= p
s－ p
fx
1, x
2, …, x
16≧ 0
〔主問題
(P)
〕min. y
T(p
s－ p
f)
s.t. y
Ta
1≧ 0, y
Ta
2≧ 0, …, y
Ta
16≧ 0
〔双対問題
(D)
〕実行可能〔∵）自明解y=0〕 双対定理
実行可能（最適値
0
）or
実行不能（(D)
は非有界）yT(ps － pf)<0と なる解yが存在
(P)
が実行不能(D)
が実行可能〔非有界：
y
T(p
s －p
f)<0
となる解y
が存在〕双対定理
∵）(P)が実行可能と仮定し，実行可能解xとすると，
0 = 0x1+ 0x2+ …+ 0x16
≦ yTa1x1 + yTa2x2+…+ yTa16x16
= yT(ps－ pf) ＜0 となり矛盾
注）(P)が実行可能 なら最適値0
Puzzle を解こう
• ペグソリティア
– 初期配置 p
sから最終配置 p
fまでの全てのジャンプ（まとめ）
a
1x
1+ a
2x
2+ …+ a
16x
16= p
s－ p
fx
1, x
2, …, x
16≧ 0 が解 x を持たない
y
Ta
1≧ 0, y
Ta
2≧ 0, …, y
Ta
16≧ 0
y
T(p
s－ p
f) ＜ 0 が解 y を持つ
初期配置 p
sから最終配置 p
fまでジャンプで到達不可能
〔 C 〕の解 y についてパゴダ関数を pag(p) := y
Tp と定義すると y
T(p
s－ p
f) ＜ 0 pag(p
s) ＜ pag(p
f)
y
Ta
1≧ 0, y
3+y
4－ y
5≧ 0 y
Ta
2≧ 0, y
6+y
7－ y
8≧ 0
… …
y
Ta
16≧ 0 － y
5+y
9+y
12≧ 0
〔 A 〕
〔 B 〕
〔 C 〕
● ● ○
○ ○ ●
3 4 5
1 2
3 4 5 6
7 8 9 10
11 12
Puzzle を解こう
• パゴダ関数
– 最後の注意
max. 0x
1+0x
2+…+0x
16s.t. a
1x
1+a
2x
2+…+a
16x
16=p
s－ p
fx
1, x
2, …, x
16≧ 0
〔主問題
(P)
〕min. y
T(p
s－ p
f)
s.t. y
Ta
1≧ 0, y
Ta
2≧ 0, …, y
Ta
16≧ 0
〔双対問題
(D)
〕実行不能
実行可能
〔非有界〕
y
T(p
s －p
f)<0
となる解y
が存在実行可能
〔最適値 0 〕
実行可能
〔有界〕
y
T(p
s －p
f)=0
となる解y
が存在パゴダ関数存在
pag(p) = yTp
p
sから p
fへ
到達不可能 ？
演習
• ペグソリティア
– パゴダ関数を求めてみよう
min. y
T(p
s－ p
f)
s.t. y
Ta
1≧ 0, y
Ta
2≧ 0, …, y
Ta
16≧ 0
〔双対問題
(D)
〕min. y
T(p
s－ p
f)
s.t. y
Ta
1≧ 0, y
Ta
2≧ 0, …, y
Ta
16≧ 0 y
Tp
s=1
〔双対問題
(D’)
〕↑
目的関数が非幽界であるコトへの対処 注）y
を整数にするのは面倒だよ演習
• ペグソリティア
– やってみよう：初期配置 p
sから最終配置 p
fまで到達可能？
– 初期配置 p と最終配置（補配置でなくてよい）を適当に考え，到 達不可能になるかどうか計算してみよう
1 2
3 4 5 6
7 8 9 10
11 12
● ●
● ● ○ ●
● ○ ○ ●
● ●
○ ○
○ ○ ● ○
○ ● ● ○
○ ○
p
sp
fPuzzle を解こう
• ノノグラム（お絵かきロジック） (cf.[3])
– 縦・横のマスに，割り当てられた数字分，連続して色を塗る
問題出典：パズルゲーム・パクロス（http://www.puzzlegame.jp）
参考文献
モデル化に関する書籍
[1] H.P.Williams, ``Model Building in Mathematical Programming(4ed.)’’, Wiley (1999 [1978,1985,1990,1993]).
[2] 大山達夫 「最適化モデル分析」 日科技連 (1993).
