情報学部 経営情報学科 堀田敬介

経営情報演習 B

2 ．ゲームのモデル化

情報学部 経営情報学科 堀田敬介

2009/10/23,Fri.

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

• 3

つの数字を足して

15

にするパターンは，縦

3

列，横

3

行，斜 め

2

の前部で

8

つ必要

• 3

つを足して

15

にする組合せは以下の

8

つしかない

– 1 + 5 + 9 – 1 + 6 + 8 – 2 + 4 + 9 – 2 + 5 + 8 – 2 + 6 + 7 – 3 + 4 + 8 – 3 + 5 + 7 – 4 + 5 + 6

•1,2,3

は同一行・列・

斜めには置けない

•7,8,9

は同一行・列・

斜めには置けない

•

角は

3

回和に使われ，

中央は

4

回，他は

2

回

•etc…

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個）

目的関数：なんでもよい

演習

• 数独

– 4

×

4

で作ってみよう

–

解いてみよう





















) 4 ]

, ([

4

) 3 ]

, ([

3

) 2 ]

, ([

2

) 1 ] , ([

1 ]

, [

j i

j i

j i

j i j

i x

〔iは行，jは列を表す〕

•制約条件1：各行に1～4を1つ（i.e.,行の和が10）：4本 ex) x[1,1] + x[1,2] + x[1,3] + x[1,4] = 10

•制約条件2：各列に1～4を1つ（i.e.,列の和が10）：4本 ex) x[1,1] + x[2,1] + x[3,1] + x[4,1] = 10

•制約条件3：各枠に1～4を1つ（i.e.,枠の和が10）：4本 ex) x[1,1] + x[1,2] + x[2,1] + x[2,2] = 10

•目的関数：なんでもよい

覚え書き：

Classic LINDO Trial Version Constraints:150 Variables:300 Int.Variables:30

Puzzle を解こう

• ペグソリティア (cf.[4])

– ペグ（黒）があるマスとないマス（白）が与えられる – ペグをジャンプさせて望む配置に出来るか？

● ● ●

● ● ●

● ● ● ○ ● ● ●

● ● ○ ○ ○ ● ●

● ● ● ○ ● ● ●

● ● ●

● ● ●

● ● ○

ジャンプ

○ ○ ●

ジャンプは，

縦（上方向・下方向）

横（左方向・右方向）

の任意の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¹ ―[ジャンプ]→ 配置 p² のとき，

pag(p¹) ≧ pag(p²)

Puzzle を解こう

• ペグソリティア：パゴダ関数

1 2

3 4 5 6

7 8 9 10

11 12

● ●

● ● ○ ●

● ○ ○ ●

● ●



































11 10 01 10 11 11

ps

● ●

○ ○ ● ●

● ○ ○ ●

● ●



































11 10 01 11 00 11

pt

● ● ○

配置を表すベクトル ジャンプを表すベクトル

○ ○ ●

3 4 5

3 4 5





































00 00 00 01 11 00

a1

配置p^sから

1回のジャンプ（a¹） で配置p^tに移る ということは

p^t = p^s － a¹ で表せる

Puzzle を解こう

• ペグソリティア：パゴダ関数

– 全てのジャンプベクトル

1 2

3 4 5 6

7 8 9 10

11 12

● ● ○

○ ○ ●

3 4 5

3 4 5



































00 00 00 01 1100 a1



































00 00 001 11 00 0 a2

































 00 01 11000000 a3

































 001 11 00 00 00 0 a4



































00 00 00 111 00 0 a6



































00 00 00 01 11 00 a5



































00 10 10000001 a7



































00 1100000001 a8



































00 001 00 01 00 1 a9

































000100010001 a10

































110000000001 a12

































 00 01 00 01 00 10 a11

































00 00 10 00 10 01 a13

































00 01 00 01 001 0 a15



































01 00 10 001 00 0 a14



































100 100000001 a16

●

●

○

1 4 8

○

○

●

1 4 8

1 2

3 4 5 6

7 8 9 10

11 12

Puzzle を解こう

• ペグソリティア：パゴダ関数

–

初期配置

p

^s から最終配置

p

^f までの全てのジャンプ

● ●

● ● ○ ●

● ○ ○ ●

● ●

































11 10 01 10 11 11 ps

○ ○

○ ○ ● ○

○ ● ● ○

○ ○

































00 01 10 01 00 00 pf



































00 00 00 01 1100 a1



































00 00 001 11000 a2

x₁ － x₂ － … － x₁₆



































10 01 00 01 00 00 a16

p^f = p^f-1 － aⁱ¹

= p^f-2 － aⁱ² － aⁱ¹

= p^f-3 － aⁱ³ － aⁱ² － aⁱ¹

…

= p^s － aⁱⁿ － …－ aⁱ³ － aⁱ² － aⁱ¹

－

＝

この中にa¹がx¹個含まれ，a²がx²個含まれ，…

Puzzle を解こう

• ペグソリティア：パゴダ関数

–

初期配置

p

^s から最終配置

p

^f までの全てのジャンプ

a¹x¹ + a²x² + …+ a¹⁶x¹⁶ = p^s － p^f, x¹, x², …, x¹⁶ ≧ 0

従って，この線形不等式系が解xを持たないなら，初期配置 p^s から最終配置 p^f へジャンプで到達不可能．

注）解xを持っても到達可能とは限らない（ジャンプの順番を考慮してないから）

max. 0x¹ + 0x² + …+ 0x¹⁶

s.t. a¹x¹ + a²x² + …+ a¹⁶x¹⁶ = p^s － p^f x¹, x², …, x¹⁶ ≧ 0

〔主問題(P) 〕

min. y^T(p^s － p^f)

s.t. y^T a¹≧0, y^Ta²≧0, …, y^Ta¹⁶≧0

〔双対問題(D) 〕

実行可能〔∵）自明解y=0〕 双対定理

実行可能（最適値0） or 実行不能（(D)は非有界）

y^T(p^s － p^f)<0と なる解yが存在

(P)が実行不能

(D)が実行可能

〔非有界：y^T(p^s － p^f)<0となる解yが存在〕

双対定理

∵）(P)が実行可能と仮定し，実行可能解xとすると，

0 = 0x¹+ 0x²+ …+ 0x¹⁶

≦ y^Ta¹x¹ + y^Ta²x²+…+ y^Ta¹⁶x¹⁶

= y^T(p^s－ p^f) ＜0 となり矛盾

注）(P)が実行可能 なら最適値0

Puzzle を解こう

• ペグソリティア：パゴダ関数

–

初期配置

p

^s から最終配置

p

^f までの全てのジャンプ（まとめ）

a¹x¹ + a²x² + …+ a¹⁶x¹⁶ = p^s － p^f

x¹, x², …, x¹⁶ ≧ 0 が解xを持たない

y^Ta¹≧0, y^T a²≧0, …, y^T a¹⁶≧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¹≧0, y₃+y₄－y₅≧0 y^Ta²≧0, y₆+y₇－y₈≧0

… …

y^Ta¹⁶≧0 －y₅+y₉+y₁₂≧0

〔A〕

〔B〕

〔C〕

● ● ○

○ ○ ●

3 4 5

1 2

3 4 5 6

7 8 9 10

11 12

Puzzle を解こう

• パゴダ関数

–

最後の注意

max. 0x¹+0x²+…+0x¹⁶

s.t. a¹x¹+a²x²+…+a¹⁶x¹⁶ =p^s－p^f x¹, x², …, x¹⁶ ≧ 0

〔主問題(P) 〕

min. y^T(p^s － p^f)

s.t. y^Ta¹≧0, y^T a²≧0, …, y^T a¹⁶≧0

〔双対問題(D) 〕

実行不能

実行可能

〔非有界〕

y^T(p^s － p^f)<0 となる解yが存在

実行可能

〔最適値0〕

実行可能

〔有界〕

y^T(p^s － p^f)=0 となる解yが存在

パゴダ関数存在

pag(p) = y^Tp

p

^s から

p

^fへ

到達不可能

？

演習

• ペグソリティア：パゴダ関数

–

パゴダ関数を求めてみよう

min. y^T(p^s － p^f)

s.t. y^Ta¹≧0, y^T a²≧0, …, y^T a¹⁶≧0

〔双対問題(D) 〕

min. y^T(p^s － p^f)

s.t. y^Ta¹≧0, y^T a²≧0, …, y^T a¹⁶≧0 y^T p^s=1

〔双対問題(D’) 〕

↑目的関数が非幽界であるコトへの対処 注）yを整数にするのは面倒だよ

演習

• ペグソリティア：パゴダ関数

–

やってみよう：初期配置

p

^s から最終配置

p

^f まで到達可能？

–

初期配置

p

と最終配置（補配置でなくてよい）を適当に考え，到 達不可能になるかどうか計算してみよう

1 2

3 4 5 6

7 8 9 10

11 12

● ●

● ● ○ ●

● ○ ○ ●

● ●

○ ○

○ ○ ● ○

○ ● ● ○

○ ○

p

^s

p

^f

Puzzle を解こう

• ノノグラム（お絵かきロジック） (cf.[3])

–

縦・横のマスに，割り当てられた数字分，連続して色を塗る

出典：パズルゲーム・パクロス（http://www.puzzlegame.jp）

参考文献

 モデル化に関する書籍

[1] H.P.Williams, ``Model Building in Mathematical Programming(4ed.)’’, Wiley (1999 [1978,1985,1990,1993]).

[2] 大山達夫 「最適化モデル分析」 日科技連(1993).

 パズルのモデル化に関する講演・記事

[3] 岡本吉央，“整数計画法によるパズル解法”，組合せゲーム・パズル ミニ プロジェクト 第2回ミニ研究集会(2007/3/16)

[4] 松井知己，“解けないパズルをLPで解く”，オペレーションズ・リサーチ, vol.53, no.11 (2008) pp.643-648.

[5] S.Flannery, D.Flannery,^{亀井よし子訳}, “16歳のセアラが挑んだ世界最強の暗 号”,日本放送出版協会(2001)