整数計画法によるパズル解法
（実習報告）
岡本 吉央
（豊橋技術科学大学情報工学系）
ミニ研究集会「組合せゲーム・パズ
ル」
平成19年 3月16日 （金）
豊橋技術科学大学について
• 設立：1976年
• 目的：高専生受入
↓↓
• 技術科学大学：
「長岡」と「豊橋」
• 詳細：「三十年史」を参
照
http://www.tut.ac.jp/30th/book.html
豊橋技術科学大学：入学生
高等学校
高専・短大 外国人留学生 高専専攻科
社会人
他大学
豊橋技術科学大学：出身地域
中部
外国
北海道・東北
その他
近畿
中国
関東
九州・沖縄
愛知
四国
高専生体験実習
• 開催時期：
7月後半～8月前半
• 対象：高専4年生
• 目的：「本学における
教育研究分野の実習を
体験することにより、
学校教育の充実及び学
生の学習意欲の喚起
等」
• 受入期間：１週間
• 注：大抵「インター
ン」の
全国の高専分布
私の実習テーマ
• 「整数計画法によるパズル解法」
• 目的：
– 整数計画モデルの初歩の習得
– パズルの数理的側面に対する意識
– 道具としてのプログラミングの利用
• 受入条件：
– C/C++言語によるプログラミング経験があ
る
– 数理的・論理的思考が好きである
• 藤戸敏弘先生との共同
• 大学院生４人の（とても親切な）手伝
この発表では...
• 実習の流れの説明
• 実際の解法の説明 （数独を例とし
て）
• その他注意事項
募集状況・受入状況
• 募集人数：３人
• 応募人数：７人
• 受入人数：７人
（電気、電子、制御、情報などの学科
より）
• 補足
– 大学全体で58テーマ、約120名受入
– 120÷58=およそ2
スケジュール
• 時間割
–朝
–昼
–夕
９：００～１２：００
１３：３０～１６：００
１６：３０～１８：００
• 流れ
– 月・火
– 水・木
–金
導入
個別実習 （班実習）
発表会 および 討論
スケジュール・時間割
月
火
水
木
金
朝
講義
講義
実習
実習
実習
昼
実習
実習
実習
実習
討論
夕
討論
討論
実習
実習
討論
実習で行なうことの流れ
1.
2.
3.
•
パズルが持つ論理的な構造を抽出
それを整数計画問題として定式化
整数計画問題ソルバによる求解
使用したソルバ：
–
–
–
•
GLPK (GNU Linear Programming Kit)
Andrew Makhorin (ロシア) による
http://www.gnu.org/software/glpk/
自作テキスト（未完成）とGLPKレ
ファレンス・マニュアル邦訳（未完
成）を配布
ソルバに解かせる部分の詳細
パズルをそのまま記述したファイル
↓
整数計画問題出力プログラム
↓
整数計画問題として記述したファイル
↓
整数計画問題求解プログラム
↓
パズルの解答ファイル
ソルバに解かせる部分の詳細
パズルをそのまま記述したファイル
↓
整数計画問題出力プログラム
↓
整数計画問題として記述したファイル
↓
整数計画問題求解プログラム GLPK利
↓
用
パズルの解答ファイル 実習生が作成する部分
実習で扱うパズル
• 月曜日： 魔方陣と数独
• 火曜日： ののぐらむ （お絵かきロ
ジック）
• 水曜日、木曜日： 実習生が選択
–
–
–
–
–
美術館
カックロ
ナンバーリンク
覆面算
ウォールロジック
実習で扱うパズル
• 月曜日： 魔方陣と数独
• 火曜日： ののぐらむ （お絵かきロ
ジック）
• 水曜日、木曜日： 実習生が選択
–
–
–
–
–
定式化とプログラムは与える
美術館
実習生はプログラムを読んだり、
カックロ
変更することで感覚を掴む
ナンバーリンク
覆面算
ウォールロジック
実習で扱うパズル
• 月曜日： 魔方陣と数独
• 火曜日： ののぐらむ （お絵かきロ
ジック）
• 水曜日、木曜日： 実習生が選択
–
–
–
–
–
定式化とプログラムは与える
美術館
実習生はプログラムを読んだり、
カックロ
変更することで感覚を掴む
ナンバーリンク
覆面算
ウォールロジック
実習生は定式化とプログラム
を自分で一から考えて作る
実習の流れを数独で説明
• 空きマスに1から9ま
での数字をいれる
• 同じ横行と縦列、
そして3x3のブロッ
ク
には同じ数字を1つ
しか入れてはいけな
い
解答→
５ ３
１
２
９ ４
７ １
６
３
９ ２
４ ８
３
９
５ ７
８ ２ ７
９
４
５
３
９
８
６
５
９
４
１
６ ３ ８
９ ４
３
８
６ ７
２ ６
１
５
３ ４
６ ７
５
２
１ ９
パズル通信ニコリ144号，114.26ページ，例問より転載
ソルバに解かせる部分の詳細
パズルをそのまま記述したファイル
↓
整数計画問題出力プログラム
↓
整数計画問題として記述したファイル
↓
整数計画問題求解プログラム GLPK利
↓
用
パズルの解答ファイル
ソルバに解かせる部分の詳細
パズルをそのまま記述したファイル
↓
整数計画問題出力プログラム
↓
整数計画問題として記述したファイル
↓
整数計画問題求解プログラム GLPK利
↓
用
パズルの解答ファイル
数独入力ファイル
..6.....1
.7..6..5.
8..1.32..
..5.4.8..
.4.7.2.9.
..8.1.7..
..12.5..3
.6..7..8.
2.....4..
ソルバに解かせる部分の詳細
パズルをそのまま記述したファイル
↓
整数計画問題出力プログラム
↓
整数計画問題として記述したファイル
↓
整数計画問題求解プログラム GLPK利
↓
用
パズルの解答ファイル
ソルバに解かせる部分の詳細
パズルをそのまま記述したファイル
↓
整数計画問題出力プログラム
↓
整数計画問題として記述したファイル
↓
整数計画問題求解プログラム GLPK利
↓
用
パズルの解答ファイル
どんな変数を用意するか
• 上から i 番目で
左から j 番目の
マス目が k という
数字になる
j= 1 2 3 4 5 6 7
i= 1
2
3
4
5
6
7
8
9
ということを01変数に
• 変数： x[i,j,k]
(9x9x9個)
• 解釈：上の通り
8 9
どんな制約を用意するか？ 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
どんな制約を用意するか？ 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
どんな制約を用意するか？ 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
どんな制約を用意するか？ 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
どんな制約を用意するか？ 5
• 既に数字が入ってい
るマス目にはそれに
対応する変数を1にす
る
• 例えば
x[3,4,1] = 1
x[5,2,4] = 1
など
数独を解く問題
• 数独を解く問題が
制約1、2、3、4、5をすべて満たす場
合があるかどうか調べる整数計画問題
になった
注： 整数計画問題といっても、
「最適化問題」ではなく、
「許容性判定問題」になっている
（「最適化問題」と「許容性判定問題」は多項式時間
等価）
ソルバに解かせる部分の詳細
パズルをそのまま記述したファイル
↓
整数計画問題出力プログラム
↓
整数計画問題として記述したファイル
↓
整数計画問題求解プログラム GLPK利
↓
用
パズルの解答ファイル
ソルバに解かせる部分の詳細
パズルをそのまま記述したファイル
↓
整数計画問題出力プログラム
↓
整数計画問題として記述したファイル
↓
整数計画問題求解プログラム GLPK利
↓
用
パズルの解答ファイル
数独解答ファイル
536827941
172964358
894153267
715349826
643782195
928516734
481295673
369471582
257638419
５ ３
１
２
９ ４
７ １
６
３
９ ２
４ ８
３
９
５ ７
８ ２ ７
９
４
５
３
９
８
６
５
９
４
１
６ ３ ８
９ ４
３
８
６ ７
２ ６
１
５
３ ４
６ ７
５
２
１ ９
実習の様子
実習の様子
実習の様子
実習の様子
実習で扱ったパズル
•
•
•
•
•
•
•
•
割と簡単
数独
（集合被覆問題っぽい）
美術館
魔方陣
数が数字として意味を持つ
覆面算
カックロ
割と難しい
お絵かきロジック
（論理的含意「ならば」
ウォールロジック
を定式化に用いる）
ナンバーリンク
それ以外のパズル（超難し
い？）
• 「言語知識必要」系
–
–
–
–
クロスワード
ナンクロ
推理パズル
推理クロス
–
–
–
–
–
スリザーリンク
ましゅ
ヤジリン
カントリーロード
ケイスケ
• 「ループ」を作る系
• 「分断ルール」系
–
–
–
–
–
–
へやわけ
ぬりがべ
黒マスはどこだ
ひとりにしてくれ
ケイスケ
やじさんかずさん
• 「日本語の壁」系
– スケルトン
– シークワーズ
– カナオレ
一部のパズルはWebニコリ「ニコリのパズル」より抜粋 http://www.nikoli.co.jp/
•
•
•
•
•
•
それ以外のパズル（実習で
OK？）
サムライン
ナンスケ （ナンバースケルトン）
波及効果
タイルペイント
バトルシップ
ビルディングパズル
発展的な実習課題
• パズルの答えを1つ求めたとき、それ以外
に
答えがないことを確認したい。
整数計画法でどのように行なえばよい
か？
• 「簡単に決まってしまうマス」を特定す
る方法を考えて、それによって決まった
マスを予め定式化に組み込むことで、ど
れくらいの規模の問題が解けるようにな
るだろうか？
実習準備における心がけ
• 実習生のプログラミング経験：
配列、文字列が使える程度でOK
• 整数計画法の導入：
01整数計画のみ
「命題論理の算術化」として導入
（CSP？）アルゴリズムは説明しない
• オリジナルテキストの作成： 重視
• フリーソフトウェアの利用： 重視
最後に
• 評価： おおむね好評
（ヒアリングによ
る）
• 継続性： 来年度も実施予定
• 効果： 整数計画問題の導入として好
例
• 注意： 次を伝えることにも重点を
– 「整数計画法でパズルを解く」ことがパズ
ルに対するアプローチとして非標準的であ
ること
おしまい
– 「道具としてプログラミングを用いる」こ
ありがとうございました
ここから予備スライド
ののぐらむを解いてみる
3 2 2
1
3 1
2 2 3 2 8 7 4 3 1
3
2
1
2
1
5
5 2
1
2 1
3
6
1
3 2 1
3 4
1
1
http://yuki-lab.jp/nonogram/RUN.HTM より転載
ののぐらむ：ルール (1)
• 白マスを以下の規則
に従って黒く塗る
3 2 2
• 各横行の左、各縦列
の上にある数字は、
その行 (列) の中で
連続して黒く塗る白
マスの数を表す
1
3 1
2 2 3 2 8 7 4 3 1
2
1
2
1
5
5 2
1
2 1
3
6
1
3 2 1
3 4
1
1
3
ののぐらむ：ルール (2)
• 1つの行 (列) に対し
て数字が複数あると
きは、数字の並び順
どおりにその数字の
数だけ連続して黒く
塗る
• その場合、数字と数
字の間に1マス以上
の塗らないマスが入
る
3 2 2
1
3 1
2 2 3 2 8 7 4 3 1
2
1
2
1
5
5 2
1
2 1
3
6
1
3 2 1
3 4
1
1
3
ののぐらむ：別の名前
•
•
•
•
•
•
•
•
お絵かきロジック
イラストロジック
ピクロス
Paint by Numbers
Crucipixel
Edel
FigurePic
Grafilogika
•
•
•
•
•
•
•
•
Japanese Crosswords
Logic Art
Logic Square
Logicolor
Logik-Puzzles
Paint Logic
Pixel Puzzles
...
定式化のための用語
以下の定式化はBosch (200１) と本質的に同じ
• 第 i 番目の横行 =
上から i 番目の横行
• 第 j 番目の縦列 =
左から j 番目の縦列
• 第 i 番目の横行の
第 k クラスタ =
その横行の左から k
番目の黒マス塊
• 第 j 番目の縦列の
第 k クラスタ = 同
様
3 2 2
1
3 1
2 2 3 2 8 7 4 3 1
2
1
2
1
5
5 2
1
2 1
3
6
1
3 2 1
3 4
1
1
第2番目の横行の第2クラスタ
3
変数の設定 (1)
• 盤面の大きさは
nrow × ncol とする
ncol
3 2 2
• x[i,j] = 1 を
上から i 番目、左か
ら j 番目のマスが黒
く塗られることとす
る
1
3 1
2 2 3 2 8 7 4 3 1
2
1
2
1
5
5 2
1
2 1
3
6
1
3 2 1
3 4
1
1
nrow
3
変数の設定 (2)
• y[i,j,k] = 1 を
3 2 2
3 1
2 2 3 2 8 7 4 3 1
第 i 番目の横行の第
k クラスタの左端が
左から j 番目のマス
にあることとする
• nclt_row[i] =
第 i 番目の横行の
クラスタ数 とする
1
2
1
2
1
5
5 2
1
2 1
3
6
1
3 2 1
3 4
1
1
3
変数の設定 (3)
• z[i,j,k] = 1 を
3 2 2
3 1
2 2 3 2 8 7 4 3 1
第 j 番目の縦列の第
k クラスタの上端が
上から i 番目のマス
にあることとする
• nclt_col[j] =
第 j 番目の縦列の
クラスタ数 とする
1
2
1
2
1
5
5 2
1
2 1
3
6
1
3 2 1
3 4
1
1
3
制約の設定 (1)
• 第 i 横行の黒マスの
数はその行のクラス
タの数字の和
3 2 2
3 1
2 2 3 2 8 7 4 3 1
2
x[i,1] + x[i,2] +
x[i,3] + ... x[i,ncol]
= R[i,1] + R[i,2] + ...
+ R[i,nclt_row[i]]
1
2
1
5
5 2
1
2 1
3
6
1
• R[i,k] = 第 i 横行の第
k クラスタの数字
1
3 2 1
3 4
1
1
3
制約の設定 (2)
• 第 j 縦列の黒マスの
数はその列のクラス
タの数字の和
3 2 2
3 1
2 2 3 2 8 7 4 3 1
2
x[1,j] + x[2,j] +
x[3,j] + ... x[nrow,j]
= C[j,1] + C[j,2] + ...
+ C[j,nclt_col[j]]
1
2
1
5
5 2
1
2 1
3
6
1
• C[j,k] = 第 j 縦列の
第 k クラスタの数字
1
3 2 1
3 4
1
1
3
制約の設定 (3)
• 第 i 横行の第 k クラ
スタの左端はどこか
にある
3 2 2
1
3 1
2 2 3 2 8 7 4 3 1
2
y[i,1,k] + y[i,2,k] +
y[i,3,k] + ... +
y[i,ncol,k] = 1
1
2
1
5
5 2
1
2 1
3
6
1
3 2 1
3 4
1
1
3
制約の設定 (4)
• 第 j 縦列の第 k クラ
スタの上端はどこか
にある
3 2 2
1
3 1
2 2 3 2 8 7 4 3 1
2
z[1,j,k] + z[2,j,k] +
z[3,j,k] + ... +
z[nrow,j,k] = 1
1
2
1
5
5 2
1
2 1
3
6
1
3 2 1
3 4
1
1
3
制約の設定 (5) 難しい
• 第 i 横行の第 k クラ
スタの左端が上から
j マス目にあるなら
ば、
第 k+1 クラスタの左
端は 左から
j+R[i,k]+1 マス目か、
それよりも右にない
といけない
R[i,k] = 第 i 横行の第
3 2 2
1
3 1
2 2 3 2 8 7 4 3 1
2
1
2
1
5
5 2
1
2 1
3
6
1
3 2 1
3 4
1
1
3
制約の設定 (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]
3 2 2
1
3 1
2 2 3 2 8 7 4 3 1
2
1
2
1
5
5 2
1
2 1
3
6
1
3 2 1
3 4
1
1
3
制約の設定 (6) 先と同様
• 第 j 縦列の第 k クラ
スタの上端が左から i
マス目にあるならば、
第 k+1 クラスタの上
端は上から i+C[j,k]+1
マス目か、それより
も下にないといけな
1
い
3 2 2
3 1
2 2 3 2 8 7 4 3 1
2
1
2
1
5
5 2
1
2 1
3
6
3 2 1
3 4
C[j,k] = 第 j 縦列の
第 k クラスタの数字
1
1
1
3
制約の設定 (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]
3 2 2
1
3 1
2 2 3 2 8 7 4 3 1
2
1
2
1
5
5 2
1
2 1
3
6
1
3 2 1
3 4
1
1
3
制約の設定 (7) また難しい
• 上から i 番目、左か
ら j 番目のマス目が
黒いならば、第 i 横
行のあるクラスタが
そのマス目を覆って
いないといけない
3 2 2
1
3 1
2 2 3 2 8 7 4 3 1
2
1
2
1
5
5 2
1
2 1
3
6
1
3 2 1
3 4
1
1
3
制約の設定 (7) 続き
• 書き下す前に...
第 i 横行の第 k クラ
スタが左から j 番目
のマス目を覆うと
は？
3 2 2
1
3 1
2 2 3 2 8 7 4 3 1
2
1
2
1
5
5 2
1
2 1
3
6
1 3 2 1
y[i,j-R[i,k]+1,k] +
3 4
y[i,j-R[i,k]+2,k] +
1 1
... +
y[i,j,k] = 1 この左辺をC[i,j,k]と書こう
3
制約の設定 (7) 続・続き
• よって、書き下すと
3 2 2
3 1
2 2 3 2 8 7 4 3 1
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 横行のクラスタ
数
1
2
1
2
1
5
5 2
1
2 1
3
6
1
3 2 1
3 4
1
1
3
制約の設定 (7) 注意
• 書き下す前に...
第 i 横行の第 k クラ
スタが左から j 番目
のマス目を覆うと
は？
ここが0になる場合は項自体無視
3 2 2
1
3 1
2 2 3 2 8 7 4 3 1
2
1
2
1
5
5 2
1
2 1
3
6
1 3 2 1
y[i,j-R[i,k]+1,k] +
3 4
y[i,j-R[i,k]+2,k] +
1 1
... +
y[i,j,k] = 1 この左辺をC[i,j,k]と書こう
3
制約の設定 (8) 同様
• 上から i 番目、左か
ら j 番目のマス目が
黒いならば、第 j 縦
列のあるクラスタが
そのマス目を覆って
いないといけない
3 2 2
1
3 1
2 2 3 2 8 7 4 3 1
2
1
2
1
5
5 2
1
2 1
3
6
1
3 2 1
3 4
1
1
3
制約の設定 (8) 続き
• 書き下す前に...
第 j 縦列の第 k クラ
スタが上から i 番目
のマス目を覆うと
は？
3 2 2
1
3 1
2 2 3 2 8 7 4 3 1
2
1
2
1
5
5 2
1
2 1
3
6
1 3 2 1
z[i-C[j,k]+1,j,k] +
3 4
z[i-C[j,k]+2,j,k] +
1 1
... +
z[i,j,k] = 1 この左辺をD[i,j,k]と書こう
3
制約の設定 (8) 続・続き
• よって、書き下すと
3 2 2
3 1
2 2 3 2 8 7 4 3 1
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 縦列のクラスタ
数
1
2
1
2
1
5
5 2
1
2 1
3
6
1
3 2 1
3 4
1
1
3
ののぐらむを解く問題
• ののぐらむを解く問題が
制約1～8をすべて満たす解があるか
どうか調べる整数計画問題になった
←本来は証明する必要がある！
• あとは解けばいい

Document