aizu online judgeから問題を引用します。
8パズルの問題
8 パズルは１つの空白を含む 3×3のマス上に 8 枚のパネルが配置され、
空白を使ってパネルを上下左右にスライドさせ、絵柄を揃えるパズルです。
この問題では、次のように空白を 0、各パネルを 1 から 8 の番号でパズルを表します。
1 3 0 4 2 5 7 8 6
1 回の操作で空白の方向に１つのパネルを移動することができ、ゴールは次のようなパネルの配置とします。
1 2 3 4 5 6 7 8 0
８パズルの初期状態が与えられるので、ゴールまでの最短手数を求めるプログラムを作成してください。
8パズルの解法
状態の遷移状態がそれほど多くないことから、単純な深さ優先探索や幅優先探索で解くことができる。
これらの解法の練習になります。
パズルの状態を管理する構造体・クラスを作る
諸々必要な変数を定義します
// 要素数
#define N 3
#define N2 N * N
// 上,右,下,左の順でチェックする
static const int dx[4] = {0,1,0,-1};
static const int dy[4] = {-1,0,1,0};
static const char dir[4] = {'u','r','d','l'};
struct Puzzle{
// 各々のタイルの状態(spaceは0だけど、9に換算する)
int tiles[N2];
// 空白の位置を管理indexで0 - 8まで
int space;
// 解法までのルートを記録
string path;
// 同じ状態遷移か判定する
bool operator < (const Puzzle &p) const {
for(int i = 0;i < N2;++i){
if(tiles[i] == p.tiles[i]) continue;
// 最短を求めるためにタイル数値が大きいと一致していると判定する(上から1,2,3と並ぶので)
return tiles[i] > p.tiles[i];
}
return false;
}
};
ポイント
タイルの表現方法
タイルは配列で管理します。
indexを割り振ると
1[0] 2[1] 3[2] 4[3] 5[4] 6[5] 7[6] 8[7] s[8]
となります。
枝刈りの方法
mapを使用して、その状態を保存するかどうか判定します。
最短経路を求める必要があるので、保存したマップの中でindexが小さいタイルの数値が大きい場合は、
非効率とみなして、一致していると判定するようにします。
パズルが一致しているかチェックする関数
indexで0から保存しているので、+1してチェックしています
/**
パズルの一致チェック
*/
bool isCorrect(Puzzle p){
// パズルが順番通り一致しているかチェック
for(int i = 0;i < N2;++i){
// 1,2,3,4,5,6,7,8の順で並ぶ
if(p.tiles[i] != (i + 1)){
return false;
}
}
return true;
}
幅優先探索を行う関数
// 幅優先探索を行う
string bfs(Puzzle p){
// 幅優先なのでqueue
queue Q;
// 同じ遷移状態がないか判定するためにmapを利用
map V;
Puzzle u,v;
p.path = "";
Q.push(p);
// 最初の状態遷移を保存
V[p] = true;
// 幅優先探索
while(!Q.empty()){
u = Q.front();
Q.pop();
// 正解チェック
if(isCorrect(u)){
return u.path;
}
// 空白の位置を算出する
int sx = u.space % N;
int sy = u.space / N;
// スペースの周りの四方のタイルを動かす
for(int r = 0;r < 4;++r){
// 動かすタイルのindexを算出する(上,右,下,左の順)
int tx = sx + dx[r];
int ty = sy + dy[r];
// 範囲外チェック
if(tx < 0 || ty < 0 || tx >= N || ty >= N){
continue;
}
v = u;
// 入れ替え
swap(v.tiles[u.space],v.tiles[ty * N + tx]);
// 入れ替えた場所がspaceになる
v.space = (ty * N) + tx;
// 1.同じ状態がでなかったら
if(!V[v]){
V[v] = true;
v.path += dir[r];
Q.push(v);
}
}
}
return "unsolvable";
}
ポイント
ポイントは、1のmapを使って、最短の経路を探しているところです。
探索するか探索しないかの状態チェックを行うのに先ほどのPuzzle構造体で定義したoperator関数を使っています。
8マップのように探索量がそれほどでもないなら、これでいけるようです。
全体のソースコード
最後に全体のソースコードを載せます
#include <iostream>
#include <cmath>
#include <string>
#include <map>
#include <queue>
using namespace std;
// 要素数
#define N 3
#define N2 N * N
// 上,右,下,左の順でチェックする
static const int dx[4] = {0,1,0,-1};
static const int dy[4] = {-1,0,1,0};
static const char dir[4] = {'u','r','d','l'};
struct Puzzle{
// 各々のタイルの状態(spaceは0だけど、9に換算する)
int tiles[N2];
// 空白の位置を管理indexで0 - 8まで
int space;
// 解法までのルートを記録
string path;
// 同じ状態遷移か判定する
bool operator < (const Puzzle &p) const {
for(int i = 0;i < N2;++i){
if(tiles[i] == p.tiles[i]) continue;
// 最短を求めるためにタイル数値が大きいと一致していると判定する(上から1,2,3と並ぶので)
return tiles[i] > p.tiles[i];
}
return false;
}
};
/**
パズルの一致チェック
*/
bool isCorrect(Puzzle p){
// パズルが順番通り一致しているかチェック
for(int i = 0;i < N2;++i){
// 1,2,3,4,5,6,7,8の順で並ぶ
if(p.tiles[i] != (i + 1)){
return false;
}
}
return true;
}
// 幅優先探索を行う
string bfs(Puzzle p){
// queueを使って、パズルの状態遷移を管理する
queue Q;
// 同じ遷移状態がないか判定するためにmapを定義する
map V;
Puzzle u,v;
p.path = "";
Q.push(p);
// 最初の状態遷移を保存
V[p] = true;
// 幅優先探索
while(!Q.empty()){
u = Q.front();
Q.pop();
// 正解チェック
if(isCorrect(u)){
return u.path;
}
// 空白の位置を算出する
int sx = u.space % N;
int sy = u.space / N;
// スペースの周りの四方のタイルを動かす
for(int r = 0;r < 4;++r){
// 動かすタイルのindexを算出する(上,右,下,左の順)
int tx = sx + dx[r];
int ty = sy + dy[r];
// 範囲外チェック
if(tx < 0 || ty < 0 || tx >= N || ty >= N){
continue;
}
v = u;
// 入れ替え
swap(v.tiles[u.space],v.tiles[ty * N + tx]);
// 入れ替えた場所がspaceになる
v.space = (ty * N) + tx;
// 同じ状態がでなかったら
if(!V[v]){
V[v] = true;
v.path += dir[r];
Q.push(v);
}
}
}
return "unsolvable";
}
int main(){
Puzzle in;
for(int i = 0;i < N2;++i){
cin >> in.tiles[i];
if(in.tiles[i] == 0){
// 空白は9として管理
in.tiles[i] = N2;
in.space = i;
}
}
string answer = bfs(in);
cout << answer.size() << endl;
return 0;
}
0 件のコメント:
コメントを投稿