UVa 10181 : 15-Puzzle Problem
問題リンク：http://uva.onlinejudge.org/external/101/10181.html
問題概要：
１５パズルを完成させるために必要な最小の手数の経路を復元せよ
解法：
IDA*
IDA*自体は UVa 652 : Eightとまったく同じ
そのパズルが解けるかどうかの判定は異なる
これはグーグルで頑張って調べてみつけたよさげなサイトの方法を実装した
以下自分のコードについての解説
関数 heuristic()：
現在のパズルの状態から目的のパズルの状態（パズルが解けた状態）までの各数字のマンハッタン距離の総和を返す（詳しくはEight参照）
関数 heuristic2():
空白と数字をスワップした際にヒューリスティック値の変化分を返す(詳しくはEight参照)
関数 DFS() :
探索する
引数gはこれまでに空白と数字をスワップした回数
引数hは現在のパズルの状態でのヒューリスティック値
引数depthは深さ（経路復元に使った）
まず最初に、 g+h > (上限) かどうか判定する
もしtrueならば、上限を超えたのでそこで終了する
ただ、そのまま終了するのではなく次の上限を更新してから終了する
つまり （次の上限） = min((次の上限),g+h) とする
次の上限は現在の上限より大きいもののなかで最小のものとする
その後で現在のパズルの状態が解けた状態かどうかを判定し、解けているならtrueを返し終了する
unsigned long long の変数を用意する
ここにパズルの状態を４bit区切りで入れる
この変数をつかって現在の状態に以前なったことがあるかどうか、
あるのであればその時より短いステップ数できているかどうかを判定する
もし悪い状態（以前よりも遅いステップ数）なら終了
最後に空白を４方向に動かしシュミレーションを続ける
関数 IDAstar() :
最初の上限をheuristic()とする
変数の初期化をする
パズルが解けるor解けない亊が分かるまで無限ループ
DFSを呼び出し、結果がtrueなら終了する
次の上限が決まっていない(パズルが解けない亊が分かった)なら終了
上限を更新する
以上
テストケース
Sample Input : 4 1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 0 1 2 3 4 5 6 7 8 9 10 11 13 15 14 12 0 1 2 3 4 12 11 10 9 8 7 6 5 13 14 15 0 1 2 3 5 6 4 9 8 7 0 10 11 14 12 13 15 Sample Output: This puzzle is not solvable. LLLURRRDLULDRRULLLDRRURD LLURRULLLDRRULLDRDRURULLDRRULLLDRRDR DRRULLDRUULLDRRRULURDDDLLLURULURRDLULDRDRRD
コード：
#include<iostream> #include<cmath> #include<algorithm> #include<cstdio> #include<map> #include<cassert> #include<deque> #include<vector> #include<climits> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) #define inf INT_MAX #define SIZE 16 #define MAX 50 #define LEN 4 using namespace std; typedef unsigned long long ull; int puzzle[SIZE],limit,next_limit; char path[MAX]; map<ull,int> mincost; int dx[] = {+1,-1,+0,+0}; int dy[] = {+0,+0,-1,+1}; char mv[] = {'R','L','U','D'}; int heuristic() { int position[SIZE]; rep(i,SIZE)position[puzzle[i]] = i; int cost = 0; rep(i,SIZE-1) { int cx = position[i] % LEN; int cy = position[i] / LEN; int tx = i % LEN; int ty = i / LEN; cost += abs(cx-tx) + abs(cy-ty); } return cost; } int heuristic2(int cx,int cy,int nx,int ny) { assert(puzzle[cx+cy*LEN] == SIZE-1); int mx = puzzle[nx+ny*LEN] % LEN; int my = puzzle[nx+ny*LEN] / LEN; int cost1 = -( abs( nx - mx ) + abs( ny - my ) ); int cost2 = abs( cx - mx ) + abs( cy - my ); return cost1 + cost2; } bool fin() { rep(i,SIZE-1)if(puzzle[i] != i)return false; return true; } bool DFS(int g,int h,int depth) { if(g+h > limit) { next_limit = min(next_limit,g+h); return false; } if(fin())return true; ull state = 0; rep(i,SIZE) { state <<= 4; state += puzzle[i]; } if(mincost.count(state) && mincost[state] <= g) { return false; } mincost[state] = g; int x,y; rep(i,SIZE)if(puzzle[i] == SIZE-1) { x = i % LEN; y = i / LEN; break; } rep(i,4) { int nx = x + dx[i]; int ny = y + dy[i]; if(!( 0 <= nx && nx < LEN && 0 <= ny && ny < LEN))continue; int h2 = heuristic2(x,y,nx,ny); swap(puzzle[x+y*LEN],puzzle[nx+ny*LEN]); path[depth] = mv[i]; path[depth+1] = 'x'; if(DFS(g+1,h+h2,depth+1)) return true; swap(puzzle[x+y*LEN],puzzle[nx+ny*LEN]); path[depth] = 'x'; } return false; } int IDAstar() { limit = heuristic(); while(true) { path[0] = 'x'; mincost.clear(); next_limit = inf; if(DFS(0,heuristic(),0)) { return limit; } if(next_limit == inf || next_limit > 45) { return -1; } limit = next_limit; } return -1; } int main() { int N; int pos = 0; scanf("%d",&N); while(N--) { rep(i,SIZE) { scanf("%d",&puzzle[i]); if(puzzle[i] == 0)puzzle[i] = SIZE; puzzle[i]--; if(puzzle[i] == SIZE-1)pos = i; } int cnt = 0; rep(i,SIZE) { if(puzzle[i] == SIZE-1)continue; rep(j,i) { if(puzzle[j] == SIZE-1)continue; if(puzzle[j] > puzzle[i])cnt++; } } cnt += pos / LEN; if(cnt%2 == 0) { puts("This puzzle is not solvable."); continue; } int res = 0; if((res = IDAstar()) == -1) { puts("This puzzle is not solvable."); } else { for(int i=0;i<MAX && path[i] != 'x';i++) { printf("%c",path[i]); } puts(""); } } return 0; }
