リンクスライダー(1人用)の最善手を計算してみた

前回紹介したリンクスライダー。AIを作りたいのですがJavaScriptで考えるのはしんどいので、まずc++で計算してみました。結果を見せるために、ゲーム上で手動で操作して動画は撮りました(答えを見ながらやっているため、操作がぎこちない。。)。

まずパズルをインプットとして与えるために、床=3,スライダー=2,プレイヤー=0にします。
上のマップの場合、一段目は"0323232",二段目は"3333333"になります。これらを1段目から繋いで1列の文字列にしてマップを与えます。インプットファイルの書式は、初めにマップの1辺のサイズを与え改行、それから先ほど説明したマップの情報を与えます。

7
0323232333333323333323333333233333233333332323232

プログラムの方は、幅優先探索をします。答えの候補より移動数の多いケースは調べるのを中断しています。最後に最善手で終えたときのマップの状態と、それを得るための操作手順を出力しています(0が左,1が右,2が上,3が下)。

#include<cstdio>
#include<string>
#include<map>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair < int, vector < int > >P;
map < string, P > d;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

const int INF = 100000000;
P ans = P(INF, vector < int >(0));
string ans_str;
int N;

void swap(string & str, int x, int nx)
{
    char t = str[x];
    str[x] = str[nx];
    str[nx] = t;
}

void bfs(string & sp)
{
    queue < string > que;
    que.push(sp);
    d[sp] = P(0, vector < int >(0));
    while (!que.empty()) {
	string s = que.front();
	que.pop();
	int p = s.find('0');
	int x = p % N;
	int y = p / N;
	for (int i = 0; i < 4; i++) {
	    int nx = x + dx[i];
	    int ny = y + dy[i];
	    if (0 <= nx && nx < N && 0 <= ny && ny < N) {
		string ns = s;
		if (ns[ny * N + nx] != '3')
		    swap(ns, p, ny * N + nx);
		else {
		    int tp = p;
		    while (ns[ny * N + nx] == '3') {
			swap(ns, tp, ny * N + nx);
			tp = ny * N + nx;
			nx += dx[i];
			ny += dy[i];
			if (0 > nx || nx >= N || 0 > ny || ny >= N
			    || ns[ny * N + nx] != '3') {
			    nx -= dx[i];
			    ny -= dy[i];
			    break;
			}
		    }
		}
		if (d.find(ns) == d.end() && ans.first > d[s].first + 1) {
		    d[ns].first = d[s].first + 1;
		    vector < int >v = d[s].second;
		    v.push_back(i);
		    d[ns].second = v;
		    if ((N / 2) * (N + 1) == ns.find('0')) {
			ans = d[ns];
			ans_str = ns;
		    }
		    que.push(ns);
		}
	    }
	}
    }
}

int main(void)
{
    string str;
    scanf("%d\n", &N);
    getline(cin, str);
    bfs(str);
    printf("%s\n", str.c_str());
    printf("%s\n", ans_str.c_str());
    printf("%d\n", (ans.first == INF) ? -1 : ans.first);
    for (int i = 0; i < ans.second.size(); i++) {
	printf("%d,", ans.second[i]);
    }
    puts("\n");
    return 0;
}