0321604-20070205

プログラミングによる
各種パズル解法の研究
-「箱入り娘」「16パズル」「ルービックキューブ」-
北海道情報大学 情報メディア学部
情報メディア学科 新井山ゼミ
0321604 大石 貴弘
発表内容(目次)
• 研究概要
• 研究目的
• 研究内容
– 箱入り娘
– 16パズル
– ルービックキューブ
• 評価
• 考察
• 今後の課題
研究概要
• 研究目的
– プログラミングによるパズルの解法の導出
• 以下のパズルを解くプログラムを制作
– 箱入り娘
– 16パズル
– ルービックキューブ
• 成果
– ルービックキューブについては未達成
– その他は達成
研究目的
• プログラミングによるパズルの解法の導出
– 使用言語
• C言語
– プログラムの制作
• 解く速度
• できるだけ小さい手数
• 無駄な動作を省略
研究内容
「箱入り娘」
• 横型探索とハッシュ法を利用
– 横型探索の特徴
•
•
•
•
すべての点を探索
探索ごとに同じ内容の点がないか確認
最短解を発見
作業が膨大
– ハッシュ法の特徴
• ハッシュ値とデータの格納位置を関連
• ハッシュ表によるデータ参照の高速化
研究内容
• 箱入り娘
– ハッシュについて
• できるだけハッシュ値が重ならないように計算
• 同じハッシュ値がないかハッシュ表を確認
• 同じハッシュ値を持ち、盤面の内容が違う場合
ハッシュ値を改めて計算し同じハッシュ値をもつ盤面
を線形リストに保存
研究内容
• 箱入り娘
研究内容
「16パズル」
• 反復深化を利用
– 反復深化の特徴
• 深さ優先探索の改良
• 横型探索よりメモリの消費が少量
• 探索する深さに上限を設定
したうえでの再帰
• 下限値枝狩り法による作業の
軽減
研究内容
• 16パズル
– 反復深化と下限値枝狩り法
• 「下限値」=盤面を完成させるための最低限の手数
• 「下限値」+「現在の深さ」>「深さ制限」⇒探索中断
研究内容
• 16パズル
– 下限値算出方法
• 各コマ(「1」~「15」)の現在の位置と
完成時の位置との距離の合算
• コマ「6」の距離: 3
• コマ「14」の距離: 2
コマ「12」の距離:3
∴合計・・・3+3+2=8
研究内容
• 16パズルの解導出
研究内容
• ルービックキューブ
– 横型探索とハッシュ法の併用
– スタート地点とゴール地点から探索する
「双方向探索」
• あらかじめゴール地点からある程度の深さまで
均一に探索
研究内容
• ルービックキューブ
– 2×2のルービックキューブの解導出
• 10手以内の盤面
– 3×3のルービックキューブ
• 10手以上の盤面は不可
• 作業量の限界
研究内容
• ルービックキューブの解導出
評価
• 箱入り娘
– 即座に最短解を導出
• 16パズル
– 大抵の盤面の最短解を導出
• ルービックキューブ
– 2×2については最短解の導出が可能
– 3×3は不満
考察
• 箱入り娘
– 探索空間が狭いため、横型探索とハッシュ法が
うまく動作
• 16パズル
– パズルとしての構造が単純
– 苦手な盤面の存在
• ルービックキューブ
– 作業が膨大
– ヒューリスティックな探索方法が困難
今後の課題
• 16パズル
– 下限値の計算方法の改良
• 探索速度は下限値の精度に比例
• 盤面に対する得手・不得手
• ルービックキューブ
– 3×3の解の導出
• 可能であれば常に最短解
• サブゴールの設定
– 計算の途中に到達すべき点を設定
• 評価値の導入
– 盤面の状態を数値で評価
参考文献
•
•
•
•
M. Hiroi’s Home Page
– http://www.geocities.co.jp/SiliconValley-Oakland/1680/
コンピュータ&パズル
– http://www.ic-net.or.jp/home/takaken/
C MAGAZINE 「悩めるプログラマに効くアルゴリズム」
– ソフトバンク 刊
2000年11月号 pp.12-39
「Perl書法」
– 増井俊之 著,アスキー出版局 刊
1993年6月