15パズルを解くプログラムの
改良
北海道情報大学 情報メディア学部
情報メディア学科 新井山ゼミ
0321604 大石 貴弘
前回までの成果
• 成果
– 15パズルの解法のプログラム
• 誓約
– 15パズルのプログラムの改良
今回までの進捗状況
• 15パズルのプログラムの改良
研究手順
• プログラムの改良
– 下限値の変更
下限値
• 下限値 パズルを解くための最小の手数
0は空白、数字はパネル
これで一手
下限値
• 現在の深さ（○手目）+下限値＜深さ制限
初期の盤面
完成形
初期の盤面
下限値＝2
1手目
深さ制限＝1
2手目
深さ制限＝2
下限値
• 現在の深さ（○手目）+下限値＜深さ制限
– 1手ごとに確認
• 深さ制限が2の場合
初期の盤面
14を移動
1手目
初期の盤面
下限値＝2
2手目
深さ制限＝2
10を移動
開発成果
• 15パズルの解法の改良
評価
• 乱数による盤面（平均手数５０前後）の解を算
出
• それ以上の手数の盤面は計算時間が長大
考察
• ある程度の実用性
• 改良の余地有り
– より正確な下限値
– それ以外の部分での工夫
今後の課題
• 改良する点を考察
次回までの成果誓約
• プログラムの改良
– 改良する点を考察
– その実装