リンクスライダー(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; }