読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

UVa 10181 : 15-Puzzle Problem

UVa IDA*

問題リンク:http://uva.onlinejudge.org/external/101/10181.html

問題概要:
15パズルを完成させるために必要な最小の手数の経路を復元せよ

解法:
IDA*
IDA*自体は UVa 652 : Eightとまったく同じ
そのパズルが解けるかどうかの判定は異なる
これはグーグルで頑張って調べてみつけたよさげなサイトの方法を実装した

以下自分のコードについての解説

関数 heuristic():
現在のパズルの状態から目的のパズルの状態(パズルが解けた状態)までの各数字のマンハッタン距離の総和を返す(詳しくはEight参照)

関数 heuristic2():
空白と数字をスワップした際にヒューリスティック値の変化分を返す(詳しくはEight参照)

関数 DFS() :
探索する
引数gはこれまでに空白と数字をスワップした回数
引数hは現在のパズルの状態でのヒューリスティック
引数depthは深さ(経路復元に使った)
まず最初に、 g+h > (上限) かどうか判定する
もしtrueならば、上限を超えたのでそこで終了する
ただ、そのまま終了するのではなく次の上限を更新してから終了する
つまり (次の上限) = min((次の上限),g+h) とする
次の上限は現在の上限より大きいもののなかで最小のものとする
その後で現在のパズルの状態が解けた状態かどうかを判定し、解けているならtrueを返し終了する
unsigned long long の変数を用意する
ここにパズルの状態を4bit区切りで入れる
この変数をつかって現在の状態に以前なったことがあるかどうか、
あるのであればその時より短いステップ数できているかどうかを判定する
もし悪い状態(以前よりも遅いステップ数)なら終了
最後に空白を4方向に動かしシュミレーションを続ける

関数 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;
}