岡本 吉央 （豊橋技術科学大学情報工学系） ミニ研究集会「組合せゲーム・パズル」 平成19年 3月16日 （金）

Presentation on theme: "岡本 吉央 （豊橋技術科学大学情報工学系） ミニ研究集会「組合せゲーム・パズル」 平成19年 3月16日 （金）"— Presentation transcript:

1 岡本 吉央 （豊橋技術科学大学情報工学系） ミニ研究集会「組合せゲーム・パズル」 平成19年 3月16日 （金）
整数計画法によるパズル解法 （実習報告） 岡本　吉央 （豊橋技術科学大学情報工学系） ミニ研究集会「組合せゲーム・パズル」 平成19年　3月16日　（金）

2 豊橋技術科学大学について 設立：1976年 目的：高専生受入 ↓↓ 技術科学大学： 「長岡」と「豊橋」 詳細：「三十年史」を参照
目的：高専生受入 　　↓↓ 技術科学大学： 「長岡」と「豊橋」 詳細：「三十年史」を参照

3 豊橋技術科学大学：入学生 高等学校 高専・短大 外国人留学生 高専専攻科 　社会人　 　他大学　

4 豊橋技術科学大学：出身地域 中部 外国 北海道・東北 その他 近畿 中国 関東 九州・沖縄 愛知 四国

5 高専生体験実習 開催時期： 7月後半～8月前半 対象：高専4年生
目的：「本学における教育研究分野の実習を体験することにより、学校教育の充実及び学生の学習意欲の喚起等」 受入期間：１週間 注：大抵「インターン」の 単位付与 全国の高専分布

6 私の実習テーマ 「整数計画法によるパズル解法」 目的： 受入条件： 藤戸敏弘先生との共同 大学院生４人の（とても親切な）手伝い
整数計画モデルの初歩の習得 パズルの数理的側面に対する意識 道具としてのプログラミングの利用 受入条件： C/C++言語によるプログラミング経験がある 数理的・論理的思考が好きである 藤戸敏弘先生との共同 大学院生４人の（とても親切な）手伝い

7 この発表では... 実習の流れの説明 実際の解法の説明　（数独を例として） その他注意事項

8 募集状況・受入状況 募集人数：３人 応募人数：７人 受入人数：７人 （電気、電子、制御、情報などの学科より） 補足
大学全体で58テーマ、約120名受入 120÷58=およそ2

9 スケジュール 時間割 流れ 朝 ９：００～１２：００ 昼 １３：３０～１６：００ 夕 １６：３０～１８：００ 月・火 導入
朝　９：００～１２：００ 昼　１３：３０～１６：００ 夕　１６：３０～１８：００ 流れ 月・火　導入 水・木　個別実習　（班実習） 金　　　 発表会　および　討論

10 スケジュール・時間割 月 火 水 木 金 朝 講義 実習 昼 討論 夕

11 実習で行なうことの流れ パズルが持つ論理的な構造を抽出 それを整数計画問題として定式化 整数計画問題ソルバによる求解 使用したソルバ：
GLPK (GNU Linear Programming Kit) Andrew Makhorin (ロシア) による 自作テキスト（未完成）とGLPKレファレンス・マニュアル邦訳（未完成）を配布

12 ソルバに解かせる部分の詳細 パズルをそのまま記述したファイル ↓ 整数計画問題出力プログラム ↓
パズルをそのまま記述したファイル 　　　　↓ 　整数計画問題出力プログラム 　　　　↓ 整数計画問題として記述したファイル 　　　　↓ 　整数計画問題求解プログラム 　　　　↓ パズルの解答ファイル

13 ソルバに解かせる部分の詳細 パズルをそのまま記述したファイル ↓ 整数計画問題出力プログラム ↓
パズルをそのまま記述したファイル 　　　　↓ 　整数計画問題出力プログラム 　　　　↓ 整数計画問題として記述したファイル 　　　　↓ 　整数計画問題求解プログラム 　　　　↓ パズルの解答ファイル GLPK利用 実習生が作成する部分

14 実習で扱うパズル 月曜日： 魔方陣と数独 火曜日： ののぐらむ （お絵かきロジック） 水曜日、木曜日： 実習生が選択 美術館 カックロ
月曜日：　魔方陣と数独 火曜日：　ののぐらむ　（お絵かきロジック） 水曜日、木曜日：　実習生が選択 美術館 カックロ ナンバーリンク 覆面算 ウォールロジック

15 実習で扱うパズル 月曜日： 魔方陣と数独 火曜日： ののぐらむ （お絵かきロジック） 水曜日、木曜日： 実習生が選択 美術館 カックロ
月曜日：　魔方陣と数独 火曜日：　ののぐらむ　（お絵かきロジック） 水曜日、木曜日：　実習生が選択 美術館 カックロ ナンバーリンク 覆面算 ウォールロジック 定式化とプログラムは与える 実習生はプログラムを読んだり、変更することで感覚を掴む

16 実習で扱うパズル 月曜日： 魔方陣と数独 火曜日： ののぐらむ （お絵かきロジック） 水曜日、木曜日： 実習生が選択 美術館 カックロ
月曜日：　魔方陣と数独 火曜日：　ののぐらむ　（お絵かきロジック） 水曜日、木曜日：　実習生が選択 美術館 カックロ ナンバーリンク 覆面算 ウォールロジック 定式化とプログラムは与える 実習生はプログラムを読んだり、変更することで感覚を掴む 実習生は定式化とプログラムを自分で一から考えて作る

17 実習の流れを数独で説明 空きマスに1から9までの数字をいれる
同じ横行と縦列、 そして3x3のブロック には同じ数字を1つ しか入れてはいけない １ ２ ３ ４ ５ ６ ７ ９ ８ 解答→ パズル通信ニコリ144号，114.26ページ，例問より転載

18 ソルバに解かせる部分の詳細 パズルをそのまま記述したファイル ↓ 整数計画問題出力プログラム ↓
パズルをそのまま記述したファイル 　　　　↓ 　整数計画問題出力プログラム 　　　　↓ 整数計画問題として記述したファイル 　　　　↓ 　整数計画問題求解プログラム 　　　　↓ パズルの解答ファイル GLPK利用

19 ソルバに解かせる部分の詳細 パズルをそのまま記述したファイル ↓ 整数計画問題出力プログラム ↓
パズルをそのまま記述したファイル 　　　　↓ 　整数計画問題出力プログラム 　　　　↓ 整数計画問題として記述したファイル 　　　　↓ 　整数計画問題求解プログラム 　　　　↓ パズルの解答ファイル GLPK利用

20 数独入力ファイル

21 ソルバに解かせる部分の詳細 パズルをそのまま記述したファイル ↓ 整数計画問題出力プログラム ↓
パズルをそのまま記述したファイル 　　　　↓ 　整数計画問題出力プログラム 　　　　↓ 整数計画問題として記述したファイル 　　　　↓ 　整数計画問題求解プログラム 　　　　↓ パズルの解答ファイル GLPK利用

22 ソルバに解かせる部分の詳細 パズルをそのまま記述したファイル ↓ 整数計画問題出力プログラム ↓
パズルをそのまま記述したファイル 　　　　↓ 　整数計画問題出力プログラム 　　　　↓ 整数計画問題として記述したファイル 　　　　↓ 　整数計画問題求解プログラム 　　　　↓ パズルの解答ファイル GLPK利用

23 どんな変数を用意するか 上から i 番目で 左から j 番目の マス目が k という 数字になる ということを01変数に
変数： x[i,j,k] (9x9x9個) 解釈：上の通り 1 2 3 4 5 6 7 8 9 j = i = 1 2 3 4 5 6 7 8 9

24 どんな制約を用意するか？ 1 各マス目には数字が ちょうど1つ入る
上から i 番目の横行と 左から j 番目の縦列に対して、 x[i,j,1]+x[i,j,2]+ x[i,j,3]+x[i,j,4]+ x[i,j,5]+x[i,j,6]+ x[i,j,7]+x[i,j,8]+ x[i,j,9] = 1

25 どんな制約を用意するか？ 2 各横行には各数字が 1つずつ入る
上から i 番目の横行と 数字 k に対して、 x[i,1,k]+x[i,2,k]+ x[i,3,k]+x[i,4,k]+ x[i,5,k]+x[i,6,k]+ x[i,7,k]+x[i,8,k]+ x[i,9,k] = 1

26 どんな制約を用意するか？ 3 各縦列には各数字が 1つずつ入る
左から j 番目の縦列と 数字 k に対して、 x[1,j,k]+x[2,j,k]+ x[3,j,k]+x[4,j,k]+ x[5,j,k]+x[6,j,k]+ x[7,j,k]+x[8,j,k]+ x[9,j,k] = 1

27 どんな制約を用意するか？ 4 各ブロックには各数字が1つずつ入る
例えば左上のブロックに対して、 x[1,1,k]+x[2,1,k]+ x[3,1,k]+x[1,2,k]+ x[2,2,k]+x[3,2,k]+ x[1,3,k]+x[2,3,k]+ x[3,3,k] = 1

28 どんな制約を用意するか？ 5 既に数字が入っているマス目にはそれに対応する変数を1にする
例えば x[3,4,1] = 1 x[5,2,4] = 1 など

29 数独を解く問題 数独を解く問題が 制約1、2、3、4、5をすべて満たす場合があるかどうか調べる整数計画問題になった
注：　整数計画問題といっても、 　　「最適化問題」ではなく、 　　「許容性判定問題」になっている （「最適化問題」と「許容性判定問題」は多項式時間等価）

30 ソルバに解かせる部分の詳細 パズルをそのまま記述したファイル ↓ 整数計画問題出力プログラム ↓
パズルをそのまま記述したファイル 　　　　↓ 　整数計画問題出力プログラム 　　　　↓ 整数計画問題として記述したファイル 　　　　↓ 　整数計画問題求解プログラム 　　　　↓ パズルの解答ファイル GLPK利用

31 ソルバに解かせる部分の詳細 パズルをそのまま記述したファイル ↓ 整数計画問題出力プログラム ↓
パズルをそのまま記述したファイル 　　　　↓ 　整数計画問題出力プログラム 　　　　↓ 整数計画問題として記述したファイル 　　　　↓ 　整数計画問題求解プログラム 　　　　↓ パズルの解答ファイル GLPK利用

32 数独解答ファイル １ ２ ３ ４ ５ ６ ７ ９ ８

33 実習の様子

34 実習の様子

35 実習の様子

36 実習の様子

37 実習で扱ったパズル 割と簡単 数独 美術館 （集合被覆問題っぽい） 魔方陣 覆面算 カックロ お絵かきロジック 数が数字として意味を持つ
ウォールロジック ナンバーリンク （集合被覆問題っぽい） 数が数字として意味を持つ 割と難しい （論理的含意「ならば」 を定式化に用いる）

38 それ以外のパズル（超難しい？） 「言語知識必要」系 「ループ」を作る系 「分断ルール」系 「日本語の壁」系 クロスワード ナンクロ
推理パズル 推理クロス 「ループ」を作る系 スリザーリンク ましゅ ヤジリン カントリーロード ケイスケ 「分断ルール」系 へやわけ ぬりがべ 黒マスはどこだ ひとりにしてくれ ケイスケ やじさんかずさん 「日本語の壁」系 スケルトン シークワーズ カナオレ 一部のパズルはWebニコリ「ニコリのパズル」より抜粋　

39 それ以外のパズル（実習でOK？） サムライン ナンスケ　（ナンバースケルトン） 波及効果 タイルペイント バトルシップ ビルディングパズル

40 発展的な実習課題 パズルの答えを1つ求めたとき、それ以外に 答えがないことを確認したい。 整数計画法でどのように行なえばよいか？
「簡単に決まってしまうマス」を特定する方法を考えて、それによって決まったマスを予め定式化に組み込むことで、どれくらいの規模の問題が解けるようになるだろうか？

41 実習準備における心がけ 実習生のプログラミング経験： 配列、文字列が使える程度でOK
整数計画法の導入： 01整数計画のみ 「命題論理の算術化」として導入　（CSP？）アルゴリズムは説明しない オリジナルテキストの作成：　重視 フリーソフトウェアの利用：　重視

42 最後に 評価： おおむね好評 （ヒアリングによる） 継続性： 来年度も実施予定 効果： 整数計画問題の導入として好例
評価：　おおむね好評　（ヒアリングによる） 継続性：　来年度も実施予定 効果：　整数計画問題の導入として好例 注意：　次を伝えることにも重点を 「整数計画法でパズルを解く」ことがパズルに対するアプローチとして非標準的であること 「道具としてプログラミングを用いる」こと おしまい

43 ありがとうございました ここから予備スライド

44 ののぐらむを解いてみる 2 1 5 3 6 4 8 7

45 ののぐらむ：ルール (1) 白マスを以下の規則に従って黒く塗る
各横行の左、各縦列の上にある数字は、その行 (列) の中で連続して黒く塗る白マスの数を表す 2 1 5 3 6 4 8 7

46 ののぐらむ：ルール (2) 1つの行 (列) に対して数字が複数あるときは、数字の並び順どおりにその数字の数だけ連続して黒く塗る
その場合、数字と数字の間に1マス以上の塗らないマスが入る 2 1 5 3 6 4 8 7

47 ののぐらむ：別の名前 お絵かきロジック イラストロジック ピクロス Japanese Crosswords Paint by Numbers
Crucipixel Edel FigurePic Grafilogika Japanese Crosswords Logic Art Logic Square Logicolor Logik-Puzzles Paint Logic Pixel Puzzles ...

48 定式化のための用語 第 i 番目の横行 = 上から i 番目の横行 第 j 番目の縦列 = 左から j 番目の縦列
以下の定式化はBosch (200１) と本質的に同じ 第 i 番目の横行 = 上から i 番目の横行 第 j 番目の縦列 = 左から j 番目の縦列 第 i 番目の横行の 第 k クラスタ = その横行の左から k 番目の黒マス塊 第 j 番目の縦列の 第 k クラスタ = 同様 2 1 5 3 6 4 8 7 第2番目の横行の第2クラスタ

49 変数の設定 (1) 盤面の大きさは nrow × ncol とする
x[i,j] = 1 を 上から i 番目、左から j 番目のマスが黒く塗られることとする ncol 2 1 5 3 6 4 8 7 nrow

50 変数の設定 (2) y[i,j,k] = 1 を 第 i 番目の横行の第 k クラスタの左端が左から j 番目のマスにあることとする
nclt_row[i] = 第 i 番目の横行の クラスタ数　とする 2 1 5 3 6 4 8 7

51 変数の設定 (3) z[i,j,k] = 1 を 第 j 番目の縦列の第 k クラスタの上端が上から i 番目のマスにあることとする
nclt_col[j] = 第 j 番目の縦列の クラスタ数　とする 2 1 5 3 6 4 8 7

52 制約の設定　(1) 第 i 横行の黒マスの数はその行のクラスタの数字の和 x[i,1] + x[i,2] + x[i,3] x[i,ncol] = R[i,1] + R[i,2] R[i,nclt_row[i]] R[i,k] = 第 i 横行の第 k クラスタの数字 2 1 5 3 6 4 8 7

53 制約の設定　(2) 第 j 縦列の黒マスの数はその列のクラスタの数字の和 x[1,j] + x[2,j] + x[3,j] x[nrow,j] = C[j,1] + C[j,2] C[j,nclt_col[j]] C[j,k] = 第 j 縦列の第 k クラスタの数字 2 1 5 3 6 4 8 7

54 制約の設定　(3) 第 i 横行の第 k クラスタの左端はどこかにある y[i,1,k] + y[i,2,k] + y[i,3,k] y[i,ncol,k] = 1 2 1 5 3 6 4 8 7

55 制約の設定　(4) 第 j 縦列の第 k クラスタの上端はどこかにある z[1,j,k] + z[2,j,k] + z[3,j,k] z[nrow,j,k] = 1 2 1 5 3 6 4 8 7

56 制約の設定　(5)　難しい 第 i 横行の第 k クラスタの左端が上から j マス目にあるならば、 第 k+1 クラスタの左端は 左から j+R[i,k]+1 マス目か、それよりも右にないといけない R[i,k] = 第 i 横行の第 k クラスタの数字 2 1 5 3 6 4 8 7

57 制約の設定　(5)　続き 書き下してみると y[i,j,k] ≦ y[i,j+R[i,k]+1,k+1] + y[i,j+R[i,k]+2,k+1] + y[i,j+R[i,k]+3,k+1] y[i,ncol,k+1] 2 1 5 3 6 4 8 7

58 制約の設定　(6)　先と同様 第 j 縦列の第 k クラスタの上端が左から i マス目にあるならば、 第 k+1 クラスタの上端は上から i+C[j,k]+1 マス目か、それよりも下にないといけない C[j,k] = 第 j 縦列の第 k クラスタの数字 2 1 5 3 6 4 8 7

59 制約の設定　(6)　続き 書き下してみると z[i,j,k] ≦ z[i+C[j,k]+1,j,k+1] + z[i+C[j,k]+2,j,k+1] + z[i+C[j,k]+3,j,k+1] z[nrow,j,k+1] 2 1 5 3 6 4 8 7

60 制約の設定　(7)　また難しい 上から i 番目、左から j 番目のマス目が黒いならば、第 i 横行のあるクラスタがそのマス目を覆っていないといけない 2 1 5 3 6 4 8 7

61 制約の設定　(7)　続き 書き下す前に... 第 i 横行の第 k クラスタが左から j 番目のマス目を覆うとは？ y[i,j-R[i,k]+1,k] + y[i,j-R[i,k]+2,k] y[i,j,k] = 1 2 1 5 3 6 4 8 7 この左辺をC[i,j,k]と書こう

62 制約の設定　(7)　続・続き よって、書き下すと x[i,j] ≦ C[i,j,1] + C[i,j,2] + C[i,j,3] C[i,j,nclt_row[i]] nclt_row[i] = 第 i 横行のクラスタ数 2 1 5 3 6 4 8 7

63 制約の設定　(7)　注意 ここが0になる場合は項自体無視 書き下す前に... 第 i 横行の第 k クラスタが左から j 番目のマス目を覆うとは？ y[i,j-R[i,k]+1,k] + y[i,j-R[i,k]+2,k] y[i,j,k] = 1 2 1 5 3 6 4 8 7 この左辺をC[i,j,k]と書こう

64 制約の設定　(8)　同様 上から i 番目、左から j 番目のマス目が黒いならば、第 j 縦列のあるクラスタがそのマス目を覆っていないといけない 2 1 5 3 6 4 8 7

65 制約の設定　(8)　続き 書き下す前に... 第 j 縦列の第 k クラスタが上から i 番目のマス目を覆うとは？ z[i-C[j,k]+1,j,k] + z[i-C[j,k]+2,j,k] z[i,j,k] = 1 2 1 5 3 6 4 8 7 この左辺をD[i,j,k]と書こう

66 制約の設定　(8)　続・続き よって、書き下すと x[i,j] ≦ D[i,j,1] + D[i,j,2] + D[i,j,3] D[i,j,nclt_col[j]] nclt_col[j] = 第 j 縦列のクラスタ数 2 1 5 3 6 4 8 7

67 ののぐらむを解く問題 ののぐらむを解く問題が 制約1～8をすべて満たす解があるか どうか調べる整数計画問題になった あとは解けばいい
←本来は証明する必要がある！