C++でスライディングパズルを解く：BFSによる最短手数の求め方

スライディングパズルとは

ここでは、2x3のボードを考えます。ボード上には1から5までの数字が書かれた5枚のタイルと、0で表される1つの空きマスがあります。

「移動」とは、空きマス(0)と、その上下左右に隣接する数字を入れ替える操作を指します。タイルが [[1,2,3],[4,5,0]] のように並んだとき、パズルは完成となります。

パズルの盤面が与えられたとき、完成状態にするために必要な最小の手数を求めます。どのように動かしても完成できない場合は -1 を返します。

例えば入力が [[1,2,3],[0,4,5]] の場合、出力は 2 になります。まず [0,4] を入れ替え、次に [0,5] を入れ替えることで完成状態にできるからです。

解法アプローチ：幅優先探索（BFS）

この問題は、各盤面をひとつの「状態」とみなせば、グラフ上の最短経路問題として捉えることができます。初期状態から完成状態までの最短手数を求めるには、幅優先探索（BFS）が最適です。BFSは浅い層から順に状態を展開していくため、初めて完成状態へ到達した時点の手数が必ず最短になると保証されます。

アルゴリズムの手順

1. 関数 slidingPuzzle() を定義し、盤面 board を引数として受け取ります。
2. 盤面がすでに完成状態であれば、0 を返します。
3. 盤面（2次元配列）を格納するキュー q を用意し、初期盤面を挿入します。
4. 訪問済みの盤面を記録するセット visited を用意し、初期盤面を登録します。
5. lvl = 1 から開始し、キューが空になるまで以下を繰り返します（各ループで lvl を1増加）。
   • キューの現在のサイズ sz を取得します。
   • sz 回だけ次の処理を繰り返します。
     • キューの先頭要素を2次元配列 node として取り出し、キューから削除します。
     • node 内で 0 の位置 (x, y) を探します。
     • 4方向（上下左右）それぞれについて、隣接座標 (nx, ny) を計算します。
     • (nx, ny) が盤面の範囲外であれば、次の反復へスキップします。
     • node[x][y] と node[nx][ny] を入れ替えます。
     • その盤面がすでに訪問済みであれば、入れ替えを元に戻してスキップします。
     • 新しい盤面を visited に追加します。
     • 盤面が完成状態であれば、lvl を返します。
     • 盤面をキューに追加し、入れ替えを元に戻します。
6. キューが空になっても完成状態に到達できなければ、-1 を返します。

C++による実装例

それでは、理解を深めるために実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
    public:
    bool ok(vector<vector<int>>& b){
        return b[0][0] == 1 && b[0][1] == 2 && b[0][2] == 3 && b[1]
        [0] == 4 && b[1][1] == 5;
    }
    int slidingPuzzle(vector<vector<int>>& board) {
        if (ok(board))
        return 0;
        queue<vector<vector<int> > > q;
        q.push(board);
        set<vector<vector<int> > > visited;
        visited.insert(board);
        for (int lvl = 1; !q.empty(); lvl++) {
            int sz = q.size();
            while (sz--) {
                vector<vector<int> > node = q.front();
                q.pop();
                int x = -1;
                int y = -1;
                for (int i = 0; i < board.size(); i++) {
                    for (int j = 0; j < board[0].size(); j++) {
                        if (node[i][j] == 0) {
                            x = i;
                            y = j;
                            break;
                        }
                    }
                }
                for (int k = 0; k < 4; k++) {
                    int nx = x + dir[k][0];
                    int ny = y + dir[k][1];
                    if (nx < 0 || ny < 0 || nx >= board.size() || ny
                    >= board[0].size())
                    continue;
                    swap(node[x][y], node[nx][ny]);
                    if (visited.count(node)) {
                        swap(node[x][y], node[nx][ny]);
                        continue;
                    }
                    visited.insert(node);
                    if (ok(node))
                    return lvl;
                    q.push(node);
                    swap(node[x][y], node[nx][ny]);
                }
            }
        }
        return -1;
    }
};
int main(){
    Solution ob;
    vector<vector<int>> v = {{1,2,3},{0,4,5}};
    cout << (ob.slidingPuzzle(v));
}

実行結果

入力：

{{1,2,3},{0,4,5}}

出力：

2

計算量の考察

2x3の盤面では、5枚のタイルと空きマスを6マスに配置する組み合わせは最大で 6! = 720 通りです。つまり、探索すべき状態数は高々720個しかなく、BFS全体の計算量は O(6!)、実質的に定数時間で完了します。必要なメモリも状態数に比例するだけであり、この手法は非常に効率的です。

また、同じ考え方は3x3の「8パズル」など、より大きな盤面にも応用できます。ただし盤面が大きくなると状態数が階乗的に増加するため、A*アルゴリズムのような発見的探索と組み合わせるのが一般的です。