土下座しながら探索中

主に競技プログラミング

652 : Eight

問題リンク:Eight

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

解法:
IDA*で解いた
ヒューリスティック関数では現在のパズルの状態から目的の状態(パズルが解けた状態)へのマンハッタン距離の総和を求めた
例えば、次の状態について考える

2 1 3  | 1 2 3
4 5 8  | 4 5 6
7 x 6  | 7 8 x

'|'の左側が現在のパズルの状態、右側が目的の状態(パズルが解けた状態)である
この時、

2の場所が違うので目的とのマンハッタン距離 = 1
1の場所が違うので(略           = 1
6の(略                  = 1
8(略                   = 2

よってマンハッタン距離の総和は5となる
ここで、'x'(空白)については考えない
数字を全て元の場所に戻せたのであればそれも戻っているはずだから

これともうひとつ、dfsで探索する際にヒューリスティック値を更新するための関数も用意する
この関数では、'x'の位置と'x'と位置を交換する位置を引数とする
'x'と位置を交換する位置に存在する数字のその場所から目的の場所へのマンハッタン距離をcost1とする
'x'と位置を交換した後の位置とその数字の目的の位置とのマンハッタン距離をcost2とする
そして -cost1 + cost2 をリターンする
これは、現在の状態から次の状態に遷移する際にどのくらいヒューリスティック値が変化したかを意味する
次の状態へ遷移する際のヒューリスティック値は(これまでのヒューリスティック値)+ (-cost1 + cost2)となる

それと枝刈りのためにmapで同じ状態はカットするようにした
現在のパズルの状態はpuzzle[]というint型の1次元配列で表現したが、
これをmapで記憶するために、long long 型の変数に変換する
パズルに現れる数字は(簡単のため'x'は9とする)1から9である
これは4bitあれば表現できるので、long long型の変数に4bit区切りで挿入する

あとはこれらを使ってIDA*、、、なのだが、
パズルを完成する亊ができない場合はあらかじめカットする必要がある
これについては頑張ってインターネットで調べた結果でてきたよさげなサイトの方法で実装した

コード:

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define inf (1<<29)
#define SIZE 9
#define MAX 100

using namespace std;
typedef long long ll;

int puzzle[SIZE],limit,next_limit;
char path[MAX];
map<ll,int> mincost;
int  dx[] = {+1,-1,+0,+0};
int  dy[] = {+0,+0,-1,+1};
char mv[] = {'r','l','u','d'};

int heuristic()
{
  int cost = 0;
  int position[SIZE];
  rep(i,SIZE)position[puzzle[i]] = i;

  rep(i,SIZE-1)
    {
      int cx = i % 3;
      int cy = i / 3;
      int tx = position[i] % 3;
      int ty = position[i] / 3;
      cost += abs(cx-tx) + abs(cy-ty);
    }
  return cost;
}

int heuristic2(int x,int y,int nx,int ny)
{
  int mx = puzzle[nx+ny*3] % 3;
  int my = puzzle[nx+ny*3] / 3;
  int cost1 = - ( abs(mx - nx) + abs(my - ny) );
  int cost2 =     abs(mx -  x) + abs(my -  y);
  return cost1+cost2;
}

inline bool fin()
{
  rep(i,SIZE)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;

  ll 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] == 8)
    {
      x = i % 3;
      y = i / 3;
      break;
    }
    
  rep(i,4)
    {
      int nx = x + dx[i];
      int ny = y + dy[i];

      if(!( 0 <= nx && nx < 3 && 0 <= ny && ny < 3 ))continue;

      int h2 = heuristic2(x,y,nx,ny);
      
      swap(puzzle[x+y*3],puzzle[nx+ny*3]);

      path[depth] = mv[i];
      path[depth+1] = 'x';

      if(dfs(g+1,h+h2,depth+1))
	return true;
      swap(puzzle[x+y*3],puzzle[nx+ny*3]);
      path[depth] = 'x';

    }
  return false;
}

int IDAstar()
{
  limit = heuristic();
  while(true)
    {
      next_limit = inf;
      mincost.clear();
      path[0] = 'x';

      if(dfs(0,heuristic(),0))
	return limit;

      if(next_limit == inf)
	return -1;

      limit = next_limit;

    }

}

bool check(const vector<int> &vec)
{
  int swap_cnt = 0,cur = 0;
  deque<int> deq;
  rep(i,vec.size())deq.push_back(vec[i]);


  while(!deq.empty())
    {
      if(cur != deq.front())
	{
	  for(deque<int>::iterator it = deq.begin(); it != deq.end();it++)
	    {
	      if(*it == cur)
		{
		  swap_cnt += (it-deq.begin());
		  deq.erase(it);
		  break;
		}
	    }
	  cur++;
	}
      else
	{
	  deq.pop_front();
	  cur++;
	}
    }

  return !(swap_cnt&1);
}

int main()
{
  int N;
  bool first = true;
  int rm = scanf("%d",&N);
  while(N--)
    {
      if(!first)puts("");
      first = false;

      vector<int> vec;
      rep(i,9)
	{
	  string digit;
	  cin >> digit;
	  if(digit == "x")puzzle[i] = 9;
	  else            puzzle[i] = (digit[0]-'0');
	  puzzle[i]--;
	  if(puzzle[i] != 8)vec.push_back(puzzle[i]);
	}
 
      if(!check(vec))
	{
	  printf("unsolvable\n");
	  continue;
	}

      int res = IDAstar();

      if(res == -1)printf("unsolvable\n");
      else
	{
	  for(int i=0;i<MAX&&path[i] != 'x';i++)
	    {
	      printf("%c",path[i]);
	    }
	  puts("");
	}
    }
  return 0;
}