6人の壁画の手数を短縮した話

こんなもん要はただのスライドパズルなので探索かければいけるやろ

趣旨
方針
IDA*実装
IDA*実行1
IDA*実行2
解についての考察1
解についての考察2
さらなる短縮へ
BFS
おわりに
おわらせない
双方向BFS
双方向BFS実行
おわり
ソースコード
- IDA*
- BFS
- 双方向BFS

趣旨

6人の壁画は61手解法(http://homentosu.blog.fc2.com/blog-entry-71.html)が知られているが、かなり人間的にわかりやすい操作をしている。これが最適でない可能性が少なからずある、というかさすがにもっと短くなるはず。実機でちまちまやるのは面倒だし間違いが起きそうなのでプログラムを書いてパソコンに頑張ってもらいましょう

方針

何種類か思いつくので検討してみる。

(1) 幅優先探索(BFS)

最初の盤面から（ありうるすべての）一手先盤面を考える。一手先の盤面（のうち初見のものすべて）から（ありうるすべての）二手先盤面を考える。目的の盤面が見つかるまで続ける。目的の盤面が見つかったらその道筋を復元する。

(2) A*

BFSするとき、何らかの評価値にもとづいて、評価値がよいものから優先して探索する。スライドパズルでいえば「このままいくと全体でX手以上はかかる」という見積もりを評価値として、Xが小さいものから探索する手法が一般的。

こういうBFS的手法は手数が多いと探索する盤面がどんどん増え、それに比例してメモリを食う。探索する盤面の総数が1000万ぐらいなら余裕だが、それより圧倒的に多くなる気がするのでちょっとまずそう。

……実はこの「まずそう」をきちんと評価しておけばよかったと後悔することになるのだが、それはまたのちほど。

次に深さ優先探索(DFS)的手法。イメージは、完成 or 手詰まりになるまで探索して、手詰まりならちょっと戻して別の方法を試していくという感じ。強みはメモリが少なくて済む点。スライドパズルに適用する場合は無限ループを回避するような工夫が必要。

(3) 反復深化深さ優先探索(IDDFS)

X手で行ける、と思ってX手先までDFS。だめならX+1手と思い直して最初からやり直す。実行時間はかさむが、基本的にX+1手のDFSで探索する盤面>X手のDFSで探索する盤面なので、最初から必要手数が分かっている場合と比較して致命的に遅くなるということはないと考えていい。

(4) 反復深化A* (IDA*)

基本はIDDFSと同じだが、X手で行ける可能性がなくなった時点で（X手まで探索せずに）早期撤退。不要な探索が減り、高速化につながる。

今回はIDA*を採用した。

IDA*実装

盤面の表現

プログラム上で盤面をどう表現すればよいだろうか。簡単に思いつくのは、「タイルに番号を振って二次元の配列上に盤面を見たまま表現する」ことだろう。

初期盤面（5人）を例にとるとこういう感じ。タイルに0から順に番号を振っていき、タイルがない場所は-1とした。

こうすると目的盤面（6人）はこのように表現できる。

というわけで、「6人の壁画を解く」という行為はプログラム上では「上の配列を変化させていって、下の配列にたどり着く」ことと言い表せる。

タイルをスライドするとは

「配列を変化させる」といっても、好き放題に変化させていいわけではなく、タイルのスライドに対応する変化しか許されない。スライドは「0から10までの好きな数字nと上下左右のうち好きな方向を1つ選んで、配列上にあるすべてのnをその方向にずらすこと」になるが、次の条件を満たす必要がある。

ずらした結果nが配列外にはみ出てはいけない（タイルは盤外に行けない）
-1（空き）でない場所をnで上書きするようなことがあってはいけない（タイルは重ならない）

よりプログラムにしやすい表現にしてみよう。簡単のためxの正の方向とする。

nが(x1, y1), (x2, y2), ... にあるとき、配列の(x1, y1), (x2, y2), ... 番目を-1で書き換えたうえで、(x1+1, y1), (x2+1, y2) ... 番目をnに書き換える。ただし

どの(x?+1, y?)も配列外になってはいけない
(x?+1, y?)をnに書き換える前に-1以外の数字が書かれていてはいけない

より効率的に配列を表現する方法

盤面サイズは5x5で25なので、配列を配列のまま保持するとint型(32bit) x 25個のデータ量になってしまう。IDA*をやるうえでそれが問題になることはほぼないのだが、もっと小さいデータ量で表現することができる。

盤面を復元するためには、各ピースの座標が分かればじゅうぶんである。

→ピースの各座標を(x, y)の配列にすると32bit変数2個 x 11個で足りる。

→(x, y)は25通りしかないので、(x, y)は32bit変数2個でなく1個で足りる。

具体的には、f (y, x) = 5y + xとすれば(0, 0)から(4, 4)までの数字の組は0から24の25個の数字に1対1で対応付けられる。またf(y, x)の値から y と x を復元することも容易で y = f(y, x) / 5, x = f(y, x) % 5

→もっというと、5bitあれば足りる（2⁵=32>25）。

→5bitの情報が11個あればいいので、55bitあれば足りる。

→64bit変数1個に圧縮できる。

評価値

IDA*をやるうえで重要になるのが評価値である。スライドパズルでは「完成までの手数がこれだけはかかる」という値を評価値とすることが多い。この値の見積もりに使う指標として最も基本的かつ簡単なものがマンハッタン距離である。

2次元空間でのマンハッタン距離は、2つの座標 (x1, y1), (x2, y2) に対して abs(x1 - x2) + abs(y1 - y2) で表される。ここで abs(x) は x の絶対値である。

スライドパズルにおける「マンハッタン距離」は現在の盤面と目的盤面を比較したときの各タイルのマンハッタン距離の総和であり、パズルを完成するにはこれ以上の手数が必要となる（証明：目的盤面とのマンハッタン距離はタイルのスライド1回で1より大きく減らない）。

よって、現在動かした手数+目的盤面とのマンハッタン距離がIDA*の深さ上限より大きくなったら、その時点で探索を打ち切ってよい。（なお、実際のところマンハッタン距離はあまりよい指標ではない）

ループ回避

タイルを右に動かして左に動かす行為は意味がない。それは何もしていないに等しいからである。IDA*で手数を決め打つとはいえ、こういう無駄な部分はなるべく避けたい。一般的な、全部のタイルが1x1のサイズで空きが1か所しかないようなパズルの場合、「1手前に戻らない」とするだけでよいのだが、6人の壁画では空きマスが多いためこれでは足りない。タイルAを右、タイルBを上、タイルAを左、タイルBを下、という一連の操作は、結局何もしていないのに、1手前に戻るような操作は行われていないため「1手前に戻らない」という処理では検出できない。ということは、今まで経由してきたすべての盤面を覚えておくのがよさそうである。

一般に「x が集合 S に含まれているか」の判定問題はC++ではsetを使って高速に行える。setで盤面を管理しながら、過去に探索した盤面にループしてきた場合は探索を打ち切る。このとき盤面の比較がsetの内部では行われるはずだが、上で書いた盤面情報を圧縮する方法を使うことで、25要素の配列の比較から整数1つの比較にでき、判定の高速化を図れる。

出力形式

1手目から順に、

タイル番号（スペース）移動方向

を必要な行数出力。（探索状況とか実行時間とかも出力するけど）

IDA*実行1

その他細かいことは実装に譲って、とにかく実行してみよう。

depth:19
0 sec.
depth:20
0 sec.
depth:21
0 sec.
depth:22
0 sec.
depth:23
0 sec.
depth:24
0 sec.
depth:25
0 sec.
depth:26
0 sec.
depth:27
12 sec.
depth:28
12 sec.
depth:29
861 sec.
depth:30
860 sec.
depth:31
^C
続行するには何かキーを押してください . . .

終わんねぇ～～～～～～

終わらな過ぎて途中で強制終了した。探索する盤面の数が爆発してしまっているようだ。

IDA*実行2

解全体の改善が無理なら、部分解だけでも改善したい。

このパズルの最も難しいところは縦に長い3番と4番を入れ替えるところであると言ってよいだろう。この2つを入れ替えるには4マスの縦幅が必要だが、それを確保するために61手解はタイルをかなり多く移動させており、とくに8番タイル（元サイトでは青1マス、と表現されている）の移動が激しい。この部分、削れる気がする。

というわけで、先に示したサイトで紹介されている解法を26手まで進めた盤面（(2)の終わりまで）に対して再試行。最適解の保証はなくなるが、ショートカットぐらいは見つかってもおかしくない。

depth:14
0 sec.
depth:15
0 sec.
depth:16
2 sec.
depth:17
2 sec.
depth:18
193 sec.
depth:19
193 sec.
depth:20
solution found
20 moves
0 L
0 D
6 U
6 U
6 L
6 L
3 U
6 L
8 U
8 L
4 L
1 D
1 D
4 D
3 R
3 R
4 U
4 U
8 R
8 D
(226 sec.)

終わった。

なんと26手を6手短縮して、20手で行けるらしい。つまり、このパズルの手数は61手から55手に短縮できる。

解についての考察1

IDA*の出力解に対して、同一タイルの連続移動をまとめて（可能なら適宜順番を入れ替えつつ）見やすくする。

0 LD
6 UULLL
3 U
8 UL
4 LD
1 DD
3 RR
4 UU
8 RD

8番のタイルを動かす回数がかなり減っている。

ところで、6 UULLLに注目したい。本来は6 UULLと6 Lに分かれていて間に3 Uがあった部分だ。位置関係から6 UULLは確かに3 Uの前に行う必要があるのだが、後ろの6 Lは3 Uの後でも問題ない操作なうえ、実際に手を動かしてみるとこの6 Lの必要性が（少なくとも20手目までは）存在しないことが分かる。この後どうしても6 Lの必要性が出てくる場合は仕方ないが、そうでないならこの操作は削ってしまえる。

というわけでこの6 Lをしなかった盤面をグッと睨んだ結果、6 Lが不要であることがわかった（ここは自分の頭で考えた）。

53手解法。

0 LD
6 UULL
3 U
8 UL
4 LD
1 DD
3 RR
4 UU
8 RD
2 RU 
0 RRDR
2 DD
4 L
3 L
1 UU
0 RU
2 RR
5 RR
6 DD
4 LLD
3 LL
1 LL
0 U
2 U
5 R
6 R
3 D
1 LL

解についての考察2

53手解中盤の 2 RU / 0 RRDR / 2 DD に注目したい。これは何をやっているかというと、0と2の順番を入れ替えているのだ。だが、ここの順番をもとから逆にしておけばこの操作は不要となり解が短縮できる。実際、最初の0 LD を 2 L / 0 Dとすればよく、51手解が発見できた。

図がちょっと誤植してる。本質変わんないから許して

51手解

2 L
0 D
6 UULL
3 U
8 UL
4 L
1 DD
4 D
3 RR
4 UU
8 RD
0 RDR
2 RRD
4 L
3 L
1 UU
0 RU
2 RR
5 RR
6 DD
4 LLD
3 LL
1 LL
0 U
2 U
5 R
6 R
3 D
1 LL

だが、IDA*の結果を見て改善できそうな部分はここまで。

6人の壁画の必要手数は51手でひとまず結論づいた。

……かに思えたが。

さらなる短縮へ

このパズルの重要な性質を見落としていた。

下半分、全然変わらない。

8番は縦長タイルを入れ替える関係で動かす。それはわかるが、そもそも頭を付け替えることで人数が増えるというギミックのこのパズルにおいて、下のほうにあるうえにデカい7番9番10番を動かす必要性はあまり感じられない。

こいつら、動かさないものと仮定してみるか。

こいつらを動かさないことに決めると、このパズルは一気に盤面数が小さくなる。見積もってみよう。

小さくなった壁画は、マス16個、2マスのタイル3個、1マスのタイル5個である。

2マスのタイルから置いていく。最初のタイルを置く方法は16通り（本当は盤外になるパターンがあるのでもっと小さい）、次は14マスから選ぶ。16x14通り（盤外とか干渉とか無視）。同様にやっていくと、

16 x 14 x 12 x 10 x 9 x 8 x 7 x 6 = 81285120

本当はもっと小さいという事実と、これを全部探索し尽くすよりはそれなりに早い段階で解が見つかるだろうという希望的観測を合わせると、幅優先探索が走れそうな問題サイズまで小さくなった。

BFS

幅優先探索のコードを書いた。枝刈りとかはしてない。

手元のパソコンのメモリを1GB以上食ったが、43手解が見つかった。もしこれが最適でない場合、下のでかい奴らのどれかを1回以上は動かす必要がある。

solution found (81 sec.)
43 moves:
0 L
1 L
1 L
1 L
4 U
6 U
6 U
6 L
8 U
8 R
3 R
2 R
1 D
1 L
2 D
3 D
4 L
6 L
4 L
3 U
3 U
8 L
8 D
2 R
2 R
2 U
5 R
5 R
5 R
4 D
4 L
3 L
3 D
6 R
0 R
1 U
4 L
3 L
6 D
0 R
0 R
0 R
6 D

きれいに書き直したものがこちら。

0 L
1 LLL
4 U
6 UUL
8 UR
3 RD
2 RD
1 DL
6 L
4 LL
3 UU
8 LD
2 RRU
5 RRR
4 DL
3 LD
6 R
0 R
1 U
4 L
3 L
6 DD
0 RRR

ちなみに、最適解で9番を動かす可能性は否定できないと思い、そのように書き直したものを実行してみたが、僕のパソコンでは無理そうだった。

時間とメモリがもっと潤沢にあればあるいは、いやどうだろう

おわりに

43手。もっと適切に枝刈りして双方向探索とかするともう少しどうにかなるかもしれないけど、今のところはその元気はないかな。IDA*を書いたのは初めてだったのでいい経験になりました。

おわらせない

43手解が見つかった。これより小さい手数の解があるとして、それは42手ではありえない（マンハッタン距離の偶奇性より）。あるとしたら41手か39手、37手……である。

動かさないタイルを設定したとはいえ、単純なBFSで43手先まで探索できたのなら、動かさないタイルの制限を取っ払っても20手ぐらいなら余裕で探索できるはず。双方向BFSが使えそう。

双方向BFS

初期盤面からBFSすると、手数が増えるにつれ盤面数は（たいてい）多くなっていくので、探索空間は下図左のような感じになる。しかし、目的盤面からもBFSして真ん中で落ち合うことにすれば、探索空間は下図右のようになり効率的である。

前から21手の盤面と後ろから20手の盤面の積集合が空でなければ、41手解が存在することがいえる。同様に前から19手の盤面と後ろから20手の盤面の積集合が空でなければ、39手解が存在することが言える。

とりあえず動かし方とかは考えないことにして、そういう盤面があるならそれを出力するプログラムを書いた。

双方向BFS実行

数字を変えて実行したが、41手、39手、37手、35手、33手、31手解は見つからなかった（それ以下の解がないことは最初のIDA*で実証済）。

おわり

いうことで6人の壁画の最短手数は43手、一例は上に示した通りです。この下にはソースコードしかないので見たい人だけ見てください。

ソースコード

IDA*

#include <iostream>
#include <vector>
#include <set>
#include <stack>
#include <algorithm>
#include <utility>
#include <chrono>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;

// 諸定数
const int H=5; // 縦幅
const int W=5; // 横幅
const int N=11; // ピースの数
const int space=-1; // 空白

// 方向
const string dirStr = "LURD";
const vector<int> dy = {0,-1,0,1};
const vector<int> dx = {-1,0,1,0};


// ピースの左上位置情報
const pair<int,int> undefined = {-1,-1};
vector<pair<int,int>> firstPos(N,undefined);
vector<pair<int,int>> lastPos(N,undefined);
// ピース形状
// (a,b) in pieceShape[i] = ピース[i]の左上(y,x)とすると(y+a,x+b)もピース[i]
vector<vector<pair<int,int>>> pieceShape(N);

// 判定: 座標(y,x)は盤面内
inline bool inBoard(const int y, const int x){
  return 0<=y && y<H && 0<=x && x<W;
}
// 判定: ピースの左上を(y,x)としてもピース全体が盤面内に収まる
bool pieceInBoard(const int y, const int x, const vector<pair<int,int>>& dydx){
  for(const auto& p:dydx){
    if(!inBoard(y+p.first,x+p.second)) return false;
  }
  return true;
}

// 盤面のハッシュ ピースの位置から64bit整数(使うのは55bit)
const int hashDataWidth = 5;
const int mask = (1<<hashDataWidth)-1;
long long calcHash(const vector<pair<int,int>>& pos){
  long long res = 0;
  rep(i,N){
    res<<=hashDataWidth;
    int y = pos[N-1-i].first, x = pos[N-1-i].second;
    res|=(y*W+x);
  }
  return res;
}
// ハッシュ値から指定されたピースの場所を特定
inline pair<int,int> getPos(const long long hash, const int pieceID){
  int p = (hash>>(pieceID*hashDataWidth))&mask;
  return make_pair(p/W,p%W);
}
// 指定のピースを指定の方向に動かしたときのハッシュ
long long calcSlidedHash(const long long hash, const int pieceID, const int dir){
  pair<int,int> pos = getPos(hash,pieceID);
  int y = pos.first, x = pos.second;
  y += dy[dir]; x += dx[dir];
  long long yx= y*W+x;
  long long res = hash;
  int shiftSize = pieceID*hashDataWidth;
  res ^= ((res>>shiftSize)&mask)<<shiftSize;
  res ^= (yx<<shiftSize);
  return res;
}

// 盤面から各ピースの位置情報を取得
void calcPiecePosList(const vector<vector<int>>& Board, vector<pair<int,int>>& pos){
  rep(y,H){
    rep(x,W){
      int pieceID = Board[y][x];
      if(pieceID!=space && pos[pieceID]==undefined){
        pos[pieceID] = make_pair(y,x);
      }
    }
  }
}

// ピース形状の取得
// (a,b) in pieceShape[i] = ピース[i]の左上(y,x)とすると(y+a,x+b)もピース[i]
void calcPieceShapeList(const vector<vector<int>>& Board, vector<vector<pair<int,int>>>& dydx){
  rep(y,H){
    rep(x,W){
      if(Board[y][x]!=space){
        int pieceID = Board[y][x];
        pair<int,int> pos = firstPos[pieceID];
        dydx[pieceID].push_back(make_pair(y-pos.first, x-pos.second));
      }
    }
  }
}

// 判定:指定の場所に指定の形状のピースを置くと他のピースと干渉する
bool conflict(const vector<vector<bool>>& NGPos, const vector<pair<int,int>>& pieceShape, const int y, const int x){
  for(const pair<int,int>& dydx:pieceShape){
    if(NGPos[y+dydx.first][x+dydx.second]) return true;
  }
  return false;
}

// 2点のマンハッタン距離
inline int MD(const pair<int,int> a, const pair<int,int> b){
  return abs(a.first-b.first)+abs(a.second-b.second);
}
// 2つの盤面の各ピースのマンハッタン距離の総和
// 基本はMDによる差分計算 乱用は控える
int MDSum(const vector<pair<int,int>>& pos1, const vector<pair<int,int>>& pos2){
  int res = 0;
  rep(i,N){
    res += MD(pos1[i],pos2[i]);
  }
  return res;
}

// 初期盤面
const vector<vector<int>> firstBoard = {
  {-1,  0, -1, -1,  1},
  {-1,  2,  3, -1,  4},
  { 5,  5,  3,  6,  4},
  { 7,  7,  7,  8,  9},
  { 7,  7, 10, 10,  9}
};

// 26手から20手に
const vector<vector<int>> lastBoard = {
  { 6, -1, -1,  4,  3},
  { 0,  2, -1,  4,  3},
  { 5,  5, -1, -1,  1},
  { 7,  7,  7,  8,  9},
  { 7,  7, 10, 10,  9}
};


// 51手を達成するための盤面 これは動く
/*
const vector<vector<int>> lastBoard = {
  {-1,  6, -1,  4,  3},
  { 2,  0, -1,  4,  3},
  { 5,  5, -1, -1,  1},
  { 7,  7,  7,  8,  9},
  { 7,  7, 10, 10,  9}
};
*/

// 完成盤面 これはさすがに終わらない
/*
const vector<vector<int>> lastBoard = {
  { 1, -1, -1, -1,  0},
  { 4,  3, -1, -1,  2},
  { 4,  3,  6,  5,  5},
  { 7,  7,  7,  8,  9},
  { 7,  7, 10, 10,  9}
};
*/


long long firstBoardHash, lastBoardHash;


int dfs(const int pred, const int depth, const int maxDepth, const long long boardHash, vector<vector<bool>>& NGPos,
  set<long long>& hashSet, stack<pair<int,char>>& operationStack){

  // 明らかにループしているなら探索不要
  if(hashSet.count(boardHash)) return 0;

  // 今の盤面をチェック済みリストにメモ
  hashSet.insert(boardHash);

  // 探索成功
  if(boardHash==lastBoardHash){
    cout << "solution found\n";
    vector<pair<int,int>> ans;
    while(!operationStack.empty()){
      ans.push_back(operationStack.top()); operationStack.pop();
    }
    reverse(ans.begin(),ans.end());
    cout << depth << " moves\n";
    for(auto a:ans){
      cout << a.first << ' ' << (char)a.second << '\n';
    }
    return 1;
  }
  rep(pieceID,N){ // 動かすピース
    pair<int,int> pos = getPos(boardHash, pieceID);
    int y = pos.first, x = pos.second;

    for(auto dydx:pieceShape[pieceID]){
      NGPos[y+dydx.first][x+dydx.second]=false;
    }
    rep(dir,4){ // 移動方向
      // ピースの移動先座標
      int nextY = y+dy[dir], nextX=x+dx[dir];
      // 盤面外には出られない
      if(!pieceInBoard(nextY,nextX,pieceShape[pieceID])) continue;
      // ほかのピースに被ってはいけない
      if(conflict(NGPos, pieceShape[pieceID], nextY, nextX)) continue;
      // 次の状態を計算する
      // 深さ = 手数
      int nextDepth = depth+1;
      // マンハッタン距離 (差分計算)
      int nowMD = pred-depth;
      int nextMD = nowMD-MD(pos,lastPos[pieceID])+MD(make_pair(nextY,nextX),lastPos[pieceID]);
      // 評価値 少なくともこれより少ない手数では不可能
      int nextPred = nextMD+nextDepth;
      // maxDepth手より多くなることが確定したら何もしない
      if(nextPred>maxDepth) continue;
      // ハッシュ
      long long nextHash = calcSlidedHash(boardHash, pieceID, dir);

      // 操作をスタックに積む
      operationStack.push(make_pair(pieceID,dirStr[dir]));
      for(auto dydx:pieceShape[pieceID]){
        NGPos[nextY+dydx.first][nextX+dydx.second]=true;
      }
      // 探索継続 成功したら探索は打ち切り
      if(dfs(nextPred,nextDepth,maxDepth,nextHash,NGPos,hashSet,operationStack)) return 1;
      // スタックに積んだ操作を削除
      operationStack.pop();
      for(auto dydx:pieceShape[pieceID]){
        NGPos[nextY+dydx.first][nextX+dydx.second]=false;
      }
    }
    for(auto dydx:pieceShape[pieceID]){
      NGPos[y+dydx.first][x+dydx.second]=true;
    }
  }
  // チェック済みリストから今の盤面を削除
  hashSet.erase(boardHash);
  return 0;
}

int main(){
  // 初期位置情報(左上)の取得
  calcPiecePosList(firstBoard, firstPos);
  // 完成位置情報の取得
  calcPiecePosList(lastBoard, lastPos);
  // ピース形状の取得
  calcPieceShapeList(firstBoard, pieceShape);
  // 初期盤面と完成盤面のハッシュ計算
  firstBoardHash = calcHash(firstPos);
  lastBoardHash = calcHash(lastPos);

  // IDA*準備
  int firstMD = MDSum(firstPos, lastPos);
  set<long long> hashSet;
  stack<pair<int,char>> operationStack;
  vector<vector<bool>> NGPos(H,vector<bool>(W,false));
  rep(pieceID,N){
    int y = firstPos[pieceID].first, x = firstPos[pieceID].second;
    for(auto dydx:pieceShape[pieceID]){
      NGPos[y+dydx.first][x+dydx.second] = true;
    }
  }
  // IDA*実行
  chrono::system_clock::time_point start, end;
  for(int maxDepth=firstMD;;maxDepth++){ // firstMD未満ではできないのでそこは省略
    cout << "depth:" << maxDepth << '\n';
    start = chrono::system_clock::now();
    if(dfs(firstMD,0,maxDepth,firstBoardHash,NGPos,hashSet,operationStack)){ // 成功
      end = chrono::system_clock::now();
      double ela = chrono::duration_cast<chrono::seconds> (end-start).count();
      cout << "(" << ela << " sec.)\n";
      break;
    }
    end = chrono::system_clock::now();
    double ela = chrono::duration_cast<chrono::seconds> (end-start).count();
    cout << ela << " sec." << '\n';
  }
  return 0;
}

BFS

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <utility>
#include <chrono>
#include <queue>
#include <map>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;

// 諸定数
const int H=5; // 縦幅
const int W=5; // 横幅
const int N=11; // ピースの数
const int space=-1; // 空白

// 方向
const string dirStr = "LURD";
const vector<int> dy = {0,-1,0,1};
const vector<int> dx = {-1,0,1,0};

// 判定: 座標(y,x)は盤面内
inline bool inBoard(const int y, const int x){
  return 0<=y && y<H && 0<=x && x<W;
}
// 判定: ピースの左上を(y,x)としてもピース全体が盤面内に収まる
bool pieceInBoard(const int y, const int x, const vector<pair<int,int>>& dydx){
  for(const auto& p:dydx){
    if(!inBoard(y+p.first,x+p.second)) return false;
  }
  return true;
}

// 盤面のハッシュ ピースの位置から64bit整数(使うのは55bit)
const int hashDataWidth = 5;
const int mask = (1<<hashDataWidth)-1;
long long calcHash(const vector<pair<int,int>>& pos){
  long long res = 0;
  rep(i,N){
    res<<=hashDataWidth;
    int y = pos[N-1-i].first, x = pos[N-1-i].second;
    res|=(y*W+x);
  }
  return res;
}
// ハッシュ値から指定されたピースの場所を特定
inline pair<int,int> getPos(const long long hash, const int pieceID){
  int p = (hash>>(pieceID*hashDataWidth))&mask;
  return make_pair(p/W,p%W);
}
// 指定のピースを指定の方向に動かしたときのハッシュ
long long calcSlidedHash(const long long hash, const int pieceID, const int dir){
  pair<int,int> pos = getPos(hash,pieceID);
  int y = pos.first, x = pos.second;
  y += dy[dir]; x += dx[dir];
  long long yx= y*W+x;
  long long res = hash;
  int shiftSize = pieceID*hashDataWidth;
  res ^= ((res>>shiftSize)&mask)<<shiftSize;
  res ^= (yx<<shiftSize);
  return res;
}

// 盤面から各ピースの位置情報を取得
const pair<int,int> undefined = {-1,-1};
void calcPiecePosList(const vector<vector<int>>& Board, vector<pair<int,int>>& pos){
  rep(y,H){
    rep(x,W){
      int pieceID = Board[y][x];
      if(pieceID!=space && pos[pieceID]==undefined){
        pos[pieceID] = make_pair(y,x);
      }
    }
  }
}

// ピース形状の取得
// (a,b) in pieceShape[i] = ピース[i]の左上(y,x)とすると(y+a,x+b)もピース[i]
void calcPieceShapeList(const vector<vector<int>>& Board, const vector<pair<int,int>>& piecePos, vector<vector<pair<int,int>>>& dydx){
  rep(y,H){
    rep(x,W){
      if(Board[y][x]!=space){
        int pieceID = Board[y][x];
        pair<int,int> pos = piecePos[pieceID];
        dydx[pieceID].push_back(make_pair(y-pos.first, x-pos.second));
      }
    }
  }
}

// ピースがある場所の計算
void getNGPos(const long long hash, const vector<vector<pair<int,int>>>& pieceShape, vector<vector<bool>>& NGPos){
  rep(pieceID,N){
    pair<int,int> pos = getPos(hash,pieceID);
    int y = pos.first, x = pos.second;
    for(auto dydx:pieceShape[pieceID]){
      NGPos[y+dydx.first][x+dydx.second] = true;
    }
  }
}

// 判定:指定の場所に指定の形状のピースを置くと他のピースと干渉する
bool conflict(const vector<vector<bool>>& NGPos, const vector<pair<int,int>>& pieceShape, const int y, const int x){
  for(const pair<int,int>& dydx:pieceShape){
    if(NGPos[y+dydx.first][x+dydx.second]) return true;
  }
  return false;
}

struct prevHandData{
  int movedPieceID;
  int movedDir;
};

int main(){
  // 時間計測
  chrono::system_clock::time_point startTime, endTime;
  startTime = chrono::system_clock::now();
  // 初期盤面
  const vector<vector<int>> firstBoard = {
    {-1,  0, -1, -1,  1},
    {-1,  2,  3, -1,  4},
    { 5,  5,  3,  6,  4},
    { 7,  7,  7,  8,  9},
    { 7,  7, 10, 10,  9}
  };
  // 完成盤面
  const vector<vector<int>> lastBoard = {
    { 1, -1, -1, -1,  0},
    { 4,  3, -1, -1,  2},
    { 4,  3,  6,  5,  5},
    { 7,  7,  7,  8,  9},
    { 7,  7, 10, 10,  9}
  };
  // 初期/完成盤面のピースの左上位置情報
  vector<pair<int,int>> firstPos(N,undefined);
  vector<pair<int,int>> lastPos(N,undefined);
  calcPiecePosList(firstBoard, firstPos);
  calcPiecePosList(lastBoard, lastPos);
  // ピース形状の取得
  // (a,b) in pieceShape[i] = ピース[i]の左上(y,x)とすると(y+a,x+b)もピース[i]
  vector<vector<pair<int,int>>> pieceShape(N);
  calcPieceShapeList(firstBoard, firstPos, pieceShape);
  // 初期盤面と完成盤面のハッシュ計算
  const long long firstBoardHash = calcHash(firstPos), lastBoardHash = calcHash(lastPos);

  queue<long long> que; que.push(firstBoardHash);
  map<long long,prevHandData> prevHand; prevHand[firstBoardHash]={-1,'X'};
  while(!que.empty()){
    const long long boardHash = que.front(); que.pop();
    // ピースがある場所の計算
    vector<vector<bool>> NGPos(H,vector<bool>(W,false));
    getNGPos(boardHash, pieceShape, NGPos);
    rep(pieceID,N){ // 動かすピース
      if(pieceID==7||8<pieceID) continue; // ここは動かさないことに決めた
      // 動かしたいピースの位置
      const pair<int,int> pos = getPos(boardHash, pieceID);
      const int y = pos.first, x = pos.second;
      // 自分を盤面からいったん外す
      for(const pair<int,int>& dydx:pieceShape[pieceID]){
        NGPos[y+dydx.first][x+dydx.second]=false;
      }
      rep(dir,4){ // 方向
        // ピースの移動先座標
        const int nextY = y+dy[dir], nextX=x+dx[dir];
        // 盤面外には出られない
        if(!pieceInBoard(nextY,nextX,pieceShape[pieceID])) continue;
        // ほかのピースに被ってはいけない
        if(conflict(NGPos, pieceShape[pieceID], nextY, nextX)) continue;
        // 次の盤面
        const long long nextBoardHash = calcSlidedHash(boardHash, pieceID, dir);
        // 探索済みならパス
        if(prevHand.count(nextBoardHash)) continue;
        // キューに突っ込み自分の一手前をメモ
        que.push(nextBoardHash);
        prevHand[nextBoardHash] = {pieceID, dir};
        // 答えが見つかったら終了
        if(nextBoardHash==lastBoardHash) goto outOfSearch;
      }
      // 自分を盤面に戻す
      for(auto dydx:pieceShape[pieceID]){
        NGPos[y+dydx.first][x+dydx.second]=true;
      }
    }
  }
  outOfSearch:
  endTime = chrono::system_clock::now();
  double ela = chrono::duration_cast<chrono::seconds> (endTime-startTime).count();
  cout << "solution found (" << ela << " sec.)\n";
  // 手の復元
  long long nowHash = lastBoardHash;
  stack<pair<int,char>> stk;
  while(nowHash!=firstBoardHash){
    const prevHandData phd = prevHand[nowHash];
    stk.push(make_pair(phd.movedPieceID,phd.movedDir));
    nowHash = calcSlidedHash(nowHash,phd.movedPieceID,phd.movedDir^2); // 反対方向に動かす
  }
  // 解の出力
  cout << (int)stk.size() << " moves:\n";
  while(!stk.empty()){
    cout << stk.top().first << ' ' << dirStr[stk.top().second] << '\n'; stk.pop();
  }
  return 0;
}

双方向BFS

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <utility>
#include <chrono>
#include <queue>
#include <set>
#include <map>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;

// 諸定数
const int H=5; // 縦幅
const int W=5; // 横幅
const int N=11; // ピースの数
const int space=-1; // 空白

// 方向
const string dirStr = "LURD";
const vector<int> dy = {0,-1,0,1};
const vector<int> dx = {-1,0,1,0};

// 判定: 座標(y,x)は盤面内
inline bool inBoard(const int y, const int x){
  return 0<=y && y<H && 0<=x && x<W;
}
// 判定: ピースの左上を(y,x)としてもピース全体が盤面内に収まる
bool pieceInBoard(const int y, const int x, const vector<pair<int,int>>& dydx){
  for(const auto& p:dydx){
    if(!inBoard(y+p.first,x+p.second)) return false;
  }
  return true;
}

// 盤面のハッシュ ピースの位置から64bit整数(使うのは55bit)
const int hashDataWidth = 5;
const int mask = (1<<hashDataWidth)-1;
long long calcHash(const vector<pair<int,int>>& pos){
  long long res = 0;
  rep(i,N){
    res<<=hashDataWidth;
    int y = pos[N-1-i].first, x = pos[N-1-i].second;
    res|=(y*W+x);
  }
  return res;
}
// ハッシュ値から指定されたピースの場所を特定
inline pair<int,int> getPos(const long long hash, const int pieceID){
  int p = (hash>>(pieceID*hashDataWidth))&mask;
  return make_pair(p/W,p%W);
}
// 指定のピースを指定の方向に動かしたときのハッシュ
long long calcSlidedHash(const long long hash, const int pieceID, const int dir){
  pair<int,int> pos = getPos(hash,pieceID);
  int y = pos.first, x = pos.second;
  y += dy[dir]; x += dx[dir];
  long long yx= y*W+x;
  long long res = hash;
  int shiftSize = pieceID*hashDataWidth;
  res ^= ((res>>shiftSize)&mask)<<shiftSize;
  res ^= (yx<<shiftSize);
  return res;
}

// 盤面から各ピースの位置情報を取得
const pair<int,int> undefined = {-1,-1};
void calcPiecePosList(const vector<vector<int>>& Board, vector<pair<int,int>>& pos){
  rep(y,H){
    rep(x,W){
      int pieceID = Board[y][x];
      if(pieceID!=space && pos[pieceID]==undefined){
        pos[pieceID] = make_pair(y,x);
      }
    }
  }
}

// ピース形状の取得
// (a,b) in pieceShape[i] = ピース[i]の左上(y,x)とすると(y+a,x+b)もピース[i]
void calcPieceShapeList(const vector<vector<int>>& Board, const vector<pair<int,int>>& piecePos, vector<vector<pair<int,int>>>& dydx){
  rep(y,H){
    rep(x,W){
      if(Board[y][x]!=space){
        int pieceID = Board[y][x];
        pair<int,int> pos = piecePos[pieceID];
        dydx[pieceID].push_back(make_pair(y-pos.first, x-pos.second));
      }
    }
  }
}

// ピースがある場所の計算
void getNGPos(const long long hash, const vector<vector<pair<int,int>>>& pieceShape, vector<vector<bool>>& NGPos){
  rep(pieceID,N){
    pair<int,int> pos = getPos(hash,pieceID);
    int y = pos.first, x = pos.second;
    for(auto dydx:pieceShape[pieceID]){
      NGPos[y+dydx.first][x+dydx.second] = true;
    }
  }
}

// 判定:指定の場所に指定の形状のピースを置くと他のピースと干渉する
bool conflict(const vector<vector<bool>>& NGPos, const vector<pair<int,int>>& pieceShape, const int y, const int x){
  for(const pair<int,int>& dydx:pieceShape){
    if(NGPos[y+dydx.first][x+dydx.second]) return true;
  }
  return false;
}

struct prevHandData{
  int movedPieceID;
  int movedDir;
};

int main(){
  // 時間計測
  chrono::system_clock::time_point startTime, endTime;
  startTime = chrono::system_clock::now();
  // 初期盤面
  const vector<vector<int>> firstBoard = {
    {-1,  0, -1, -1,  1},
    {-1,  2,  3, -1,  4},
    { 5,  5,  3,  6,  4},
    { 7,  7,  7,  8,  9},
    { 7,  7, 10, 10,  9}
  };
  // 完成盤面
  const vector<vector<int>> lastBoard = {
    { 1, -1, -1, -1,  0},
    { 4,  3, -1, -1,  2},
    { 4,  3,  6,  5,  5},
    { 7,  7,  7,  8,  9},
    { 7,  7, 10, 10,  9}
  };
  // 初期/完成盤面のピースの左上位置情報
  vector<pair<int,int>> firstPos(N,undefined);
  vector<pair<int,int>> lastPos(N,undefined);
  calcPiecePosList(firstBoard, firstPos);
  calcPiecePosList(lastBoard, lastPos);
  // ピース形状の取得
  // (a,b) in pieceShape[i] = ピース[i]の左上(y,x)とすると(y+a,x+b)もピース[i]
  vector<vector<pair<int,int>>> pieceShape(N);
  calcPieceShapeList(firstBoard, firstPos, pieceShape);
  // 初期盤面と完成盤面のハッシュ計算
  const long long firstBoardHash = calcHash(firstPos), lastBoardHash = calcHash(lastPos);

  // スタートからfrontDepth手
  const int frontDepth = 21;
  cout << "from start\n";
  queue<long long> que; que.push(firstBoardHash);
  set<long long> hashSet; hashSet.insert(firstBoardHash);
  set<long long> d21;
  rep(depth,frontDepth){
    cout << "depth: " << depth << " queue size:" << (long long)que.size() << '\n';
    queue<long long> que2;
    while(!que.empty()){
      const long long boardHash = que.front(); que.pop();
      // ピースがある場所の計算
      vector<vector<bool>> NGPos(H,vector<bool>(W,false));
      getNGPos(boardHash, pieceShape, NGPos);
      rep(pieceID,N){ // 動かすピース
        // 動かしたいピースの位置
        const pair<int,int> pos = getPos(boardHash, pieceID);
        const int y = pos.first, x = pos.second;
        // 自分を盤面からいったん外す
        for(const pair<int,int>& dydx:pieceShape[pieceID]){
          NGPos[y+dydx.first][x+dydx.second]=false;
        }
        rep(dir,4){ // 方向
          // ピースの移動先座標
          const int nextY = y+dy[dir], nextX=x+dx[dir];
          // 盤面外には出られない
          if(!pieceInBoard(nextY,nextX,pieceShape[pieceID])) continue;
          // ほかのピースに被ってはいけない
          if(conflict(NGPos, pieceShape[pieceID], nextY, nextX)) continue;
          // 次の盤面
          const long long nextBoardHash = calcSlidedHash(boardHash, pieceID, dir);
          // 探索済みならパス
          if(hashSet.count(nextBoardHash)) continue;
          hashSet.insert(nextBoardHash);
          // キューに突っ込む
          que2.push(nextBoardHash);
        }
        // 自分を盤面に戻す
        for(auto dydx:pieceShape[pieceID]){
          NGPos[y+dydx.first][x+dydx.second]=true;
        }
      }
    }
    swap(que,que2);
  }
  cout << "depth: " << frontDepth << " queue size:" << (long long)que.size() << '\n';
  while(!que.empty()){
    d21.insert(que.front()); que.pop();
  }
  // ゴールからbackDepth手
  const int backDepth = 20;
  cout << "from goal\n";
  queue<long long> reverseQue; reverseQue.push(lastBoardHash);
  set<long long> reverseHashSet; reverseHashSet.insert(lastBoardHash);
  rep(depth,backDepth){
    cout << "depth: " << depth << " queue size:" << (long long)reverseQue.size() << '\n';
    queue<long long> reverseQue2;
    while(!reverseQue.empty()){
      const long long boardHash = reverseQue.front(); reverseQue.pop();
      // ピースがある場所の計算
      vector<vector<bool>> NGPos(H,vector<bool>(W,false));
      getNGPos(boardHash, pieceShape, NGPos);
      rep(pieceID,N){ // 動かすピース
        // 動かしたいピースの位置
        const pair<int,int> pos = getPos(boardHash, pieceID);
        const int y = pos.first, x = pos.second;
        // 自分を盤面からいったん外す
        for(const pair<int,int>& dydx:pieceShape[pieceID]){
          NGPos[y+dydx.first][x+dydx.second]=false;
        }
        rep(dir,4){ // 方向
          // ピースの移動先座標
          const int nextY = y+dy[dir], nextX=x+dx[dir];
          // 盤面外には出られない
          if(!pieceInBoard(nextY,nextX,pieceShape[pieceID])) continue;
          // ほかのピースに被ってはいけない
          if(conflict(NGPos, pieceShape[pieceID], nextY, nextX)) continue;
          // 次の盤面
          const long long nextBoardHash = calcSlidedHash(boardHash, pieceID, dir);
          // 探索済みならパス
          if(reverseHashSet.count(nextBoardHash)) continue;
          reverseHashSet.insert(nextBoardHash);
          // キューに突っ込む
          reverseQue2.push(nextBoardHash);
        }
        // 自分を盤面に戻す
        for(auto dydx:pieceShape[pieceID]){
          NGPos[y+dydx.first][x+dydx.second]=true;
        }
      }
    }
    swap(reverseQue,reverseQue2);
  }
  cout << "depth: " << backDepth << " queue size:" << (long long)reverseQue.size() << '\n';
  bool found = false;
  while(!reverseQue.empty()){
    // 解が見つかったら
    if(d21.count(reverseQue.front())){
      cout << "solution found\n";
      cout << reverseQue.front() << '\n';
      found = true;
      break;
    }
    reverseQue.pop();
  }
  if(!found) cout << "solution not found\n";
  endTime = chrono::system_clock::now();
  double ela = chrono::duration_cast<chrono::seconds> (endTime-startTime).count();
  cout << ela << " sec.\n";
  return 0;
}

点Nの軌跡

競プロの話または日記

6人の壁画の手数を短縮した話

趣旨

方針

IDA*実装

盤面の表現

タイルをスライドするとは

より効率的に配列を表現する方法

評価値

ループ回避

出力形式

IDA*実行1

IDA*実行2

解についての考察1

解についての考察2

さらなる短縮へ

BFS

おわりに

おわらせない

双方向BFS

双方向BFS実行

おわり

ソースコード

IDA*

BFS

双方向BFS