はじめに
前回の「単一SQLクエリでハノイの塔を解いてみよう」に引き続いての再帰演習です。今回は迷路をSQL再帰で解きます。といっても迷路の解法自体は単純なブルートフォースサーチで特筆すべきことはあまりないので、追加として視覚的な迷路図に解答の道順をのせてちょっと見栄えのするSQLクエリにしてみます。さらにゴール到達に複数のルートが有る迷路も可として、すべてのルートを短い順に出力します。前回と同じくOracleのSQLで説明しつつ、最後にPostgreSQL版とMySQL版も載せておきます。
迷路の入力と出力
動きとしては、こういう迷路を使って、
こんな感じで道順をのせて迷路図を出力します。複数の道順がある場合はそれぞれの図を分けて出力します。
迷路図は適当に作るかどっかからコピーしてきてください。。迷路の壁の文字はなんでも構いません。ちなみにここで使われている迷路はPL/SQLでやっつけで作成しました(^^)。
迷路テーブルの作成
まず迷路マップをテーブルを作ります。もちろんCTEにしてクエリにくっつけても構いません。CTEのほうが手軽に迷路を変更できるので便利ですが、PL/SQLや他のプログラムから直接迷路を作ることを考えてテーブルにしました。また迷路は必ずしも長方形や正方形である必要はありません。出っ張りを作ったり凸凹にしても大丈夫(のはず)です。迷路にはにスタート地点の"S"とゴール地点の"G"を適当に配置しておきます。
CREATE TABLE maze_map AS
WITH
maze_map(n, s, maze, cnt)
AS (SELECT 1, REGEXP_SUBSTR(maze, '^.+$', 1, 1, 'm'),
maze, REGEXP_COUNT(maze, '[[:cntrl:]]+') -1
FROM (SELECT q'[
+=======================+=+===+===+
| | | | |
+=+ ======+=+=+== ==+ | | +=+ +== |
| | | | | | | | | |
| +=======+ | | +===+ +=+=+ +=+ | |
| | | | | | | |
| | +== ==+=+=+ +===+ | | | | | | |
|S| | | | | |G| | | |
+=+=+== ==+ | | | | +== +=+=+===+ |
| | | | | |
+===========+===+=+=+=============+
]' maze
FROM DUAL)
UNION ALL
SELECT n + 1,
REGEXP_SUBSTR(maze, '^.+$', 1, n + 1, 'm'),
maze, cnt
FROM maze_map
WHERE n < cnt
)
SELECT n, s FROM maze_map;
SELECT * FROM maze_map ORDER BY n;
N S
---------- -------------------------------------------
1 +=======================+=+===+===+
2 | | | | |
3 +=+ ======+=+=+== ==+ | | +=+ +== |
4 | | | | | | | | | |
5 | +=======+ | | +===+ +=+=+ +=+ | |
6 | | | | | | | |
7 | | +== ==+=+=+ +===+ | | | | | | |
8 |S| | | | | |G| | | |
9 +=+=+== ==+ | | | | +== +=+=+===+ |
10 | | | | | |
11 +===========+===+=+=+=============+
迷路を解くクエリの作成
迷路図の展開
ではクエリを作ります。上記テーブル内の迷路データは視覚的に理解しやすいようラインごとの文字列になってるため、まずはデータベースで探査しやすいよう一文字づつに分解しセル単位に落とし込みます。
WITH
-- 迷路マップをひと文字ずつの行（セル）に分解
maze_cells (h, v, cell, s)
AS (SELECT 1, n, SUBSTR(s, 1, 1), s
FROM maze_map
UNION ALL
SELECT h + 1, v, SUBSTR(s, h + 1, 1), s
FROM maze_cells
WHERE h < LENGTH(s)
)
SELECT h, v, cell FROM maze_cells;
H V CELL
---------- ---------- ----
1 1 +
1 2 |
1 3 +
1 4 |
1 5 |
1 6 |
（略）
35 6 |
35 7 |
35 8 |
35 9 |
35 10 |
35 11 +
385 rows selected.
再帰での探査
次に、上記のセルを用いて再帰し、スタートセル(S)から出発しゴールセル(G)見つけるまでセルの移動を繰り返します。現在セルの上下左右セルを参照し移動可能であればそのセルを用いて次の再帰を行います。このとき、経由したセルをXPATHとYPATHにカンマ区切りで格納することでゴールまでの道順を保持しています。また探査の途中で同じセルに戻らないようCYCLE句で制御しています。
...
-- スタートからゴールへの再帰探査
search (x, y, gcell, xpath, ypath)
AS (SELECT h, v, cell,
CAST(h AS VARCHAR2(4000)), -- 道順のX座標保持する
CAST(v AS VARCHAR2(4000)) -- 道順のY座標保持する
FROM maze_cells
WHERE cell = 'S' -- スタートセル
UNION ALL
SELECT h, v, cell,
xpath || ',' || h,
ypath || ',' || v
FROM search r, -- 現在セル
maze_cells m -- 移動候補セル
WHERE gcell != 'G' AND -- 前レベルでゴールしていれば終了
cell IN (' ', 'G', 'S') AND -- 進めるセルの文字
-- 動けるのは、（右、左、下、上）の４つのセルのみ
(h, v) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1))
)
CYCLE x, y SET cycle TO 1 DEFAULT 0 -- サイクル(繰り返し)時終了
SELECT xpath FROM search WHERE gcell = 'G';
XPATH
---------------------------------------------------------------------
2,2,2,3,4,5,6,7,8,8,8,8,8,9,10,11,12,12,12,13,14,14,14,15,16, ...(略)
ルートの取得と展開
探査が無事終了しゴールまでの道筋が発見できたら、ゴールしたレベル(行)のXPATHとYPATHからX座標とY座標のカンマ区切りリストを取得し、これを迷路のセルと同様に一行一セルに展開します。
ここで一つ考慮しなければならないのは、ゴールまでのルートが複数ある場合です。たとえば外周に接続していない壁が存在する場合は、両側から回り込めるのでマルチルートになる可能性があります。したがって複数のルートに対応するためにgrpカラムを追加してそれぞれのルートを区別しています。もし最短ルートのみを出力したい場合は、以下のWHERE RN=1を有効にします。
...
-- ゴールまでの経由セル座標のカンマ区切りパスの展開
path_cells (grp, n, cx, cy, xpath, ypath)
AS (SELECT rn,
1,
TO_NUMBER(REGEXP_SUBSTR(xpath, '^\d+')),
TO_NUMBER(REGEXP_SUBSTR(ypath, '^\d+')),
xpath, ypath
FROM (SELECT xpath, ypath,
ROW_NUMBER() OVER (ORDER BY REGEXP_COUNT(xpath, ',')) rn
FROM search
WHERE gcell = 'G' AND cycle = 0) -- ゴールしたレベル(行)の取得
/* WHERE rn = 1 */ -- 最短ルートの選択
UNION ALL
SELECT grp,
n + 1,
TO_NUMBER(SUBSTR(REGEXP_SUBSTR(xpath, ',\d+', 1, n), 2)),
TO_NUMBER(SUBSTR(REGEXP_SUBSTR(ypath, ',\d+', 1, n), 2)),
xpath, ypath
FROM path_cells
WHERE n < regexp_count(xpath, ',') + 1
)
SELECT sno, n, cx, cy FROM path_cells;
GRP N CX CY
---------- ---------- ---------- ----------
1 1 2 8
1 2 2 7
1 3 2 6
1 4 3 6
1 5 4 6
1 6 5 6
（略）
1 76 29 6
1 77 28 6
1 78 27 6
1 79 26 6
1 80 26 7
1 81 26 8
81 rows selected.
解答図の出力
上記の道順セルの行を元の迷路セルと外部結合し、道順セルが存在する迷路セルの文字を"*"に置き換えます。最後にLISTAGGで迷路マップの行ごとの文字列に再生成して終了です。複数ルートが有る場合を考慮して、それぞれの迷路図にタイトルを付加し解答番号とゴールまでのステップ数を表示しています。
...
SELECT CASE WHEN v IS NULL
THEN 'Solution #' || mc.grp || ' (' || (MAX(mc.steps) - 1) || ' steps)'
ELSE ' ' ||
LISTAGG (CASE WHEN cx IS NULL OR cell != ' '
THEN cell
ELSE '*'
END)
WITHIN GROUP (ORDER BY h)
END maze_solved
FROM (SELECT grp, steps, h, v, cell
FROM (SELECT * FROM maze_cells
UNION ALL
SELECT NULL, NULL, NULL, NULL FROM DUAL) m, -- タイトル行
(SELECT grp, COUNT(*) steps FROM path_cells GROUP BY grp)) mc,
path_cells pc
WHERE h = cx(+) AND v = cy(+) AND mc.grp = pc.grp(+)
GROUP BY mc.grp, v
ORDER BY mc.grp, mc.v NULLS FIRST;
全体の実行
以上をつなげると完成です。実行してみましょう。正しいの道順の載った迷路が出力されます。
WITH
maze_cells (h, v, cell, s)
AS (SELECT 1, n, SUBSTR(s, 1, 1), s
FROM maze_map
UNION ALL
SELECT h + 1, v, SUBSTR(s, h + 1, 1), s
FROM maze_cells
WHERE h < LENGTH(s)
),
search (x, y, gcell, xpath, ypath)
AS (SELECT h, v, cell,
CAST(h AS VARCHAR2(4000)),
CAST(v AS VARCHAR2(4000))
FROM maze_cells
WHERE cell = 'S'
UNION ALL
SELECT h, v, cell,
xpath || ',' || h,
ypath || ',' || v
FROM search r, maze_cells m
WHERE gcell != 'G' AND cell IN (' ', 'G', 'S') AND
(h, v) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1))
)
CYCLE x, y SET cycle TO 1 DEFAULT 0,
path_cells (grp, n, cx, cy, xpath, ypath)
AS (SELECT rn,
1,
TO_NUMBER(REGEXP_SUBSTR(xpath, '^\d+')),
TO_NUMBER(REGEXP_SUBSTR(ypath, '^\d+')),
xpath, ypath
FROM (SELECT xpath, ypath,
ROW_NUMBER() OVER (ORDER BY REGEXP_COUNT(xpath, ',')) rn
FROM search
WHERE gcell = 'G' AND cycle = 0)
UNION ALL
SELECT grp,
n + 1,
TO_NUMBER(SUBSTR(REGEXP_SUBSTR(xpath, ',\d+', 1, n), 2)),
TO_NUMBER(SUBSTR(REGEXP_SUBSTR(ypath, ',\d+', 1, n), 2)),
xpath, ypath
FROM path_cells
WHERE n < regexp_count(xpath, ',') + 1
)
SELECT CASE WHEN v IS NULL
THEN 'Solution #' || mc.grp || ' (' || (MAX(mc.steps) - 1) || ' steps)'
ELSE ' ' ||
LISTAGG (CASE WHEN cx IS NULL OR cell != ' '
THEN cell
ELSE '*'
END)
WITHIN GROUP (ORDER BY h)
END maze_solved
FROM (SELECT grp, steps, h, v, cell
FROM (SELECT * FROM maze_cells
UNION ALL
SELECT NULL, NULL, NULL, NULL FROM DUAL) m,
(SELECT grp, COUNT(*) steps FROM path_cells GROUP BY grp)) mc,
path_cells pc
WHERE h = cx(+) AND v = cy(+) AND mc.grp = pc.grp(+)
GROUP BY mc.grp, v
ORDER BY mc.grp, mc.v NULLS FIRST;
MAZE_SOLVED
------------------------------------------------------------
Solution #1 (80 steps)
+=======================+=+===+===+
| ***** | | | |
+=+ ======+=+=+==*==+*| | +=+ +== |
| | | | |*** |*| | | ***|
| +=======+ | |*+===+*+=+=+ +=+*|*|
|******* | *| *| |*****|*|*|
|*| +==*==+=+=+*+===+*| |*| |*|*|*|
|S| | * |***|* |***|G| |***|*|
+=+=+==*==+*|*|*| | +==*+=+=+===+*|
| *****|***| | | ***********|
+===========+===+=+=+=============+
マルチルート迷路
では、複数経路のある迷路で試してみましょう。迷路をマルチルートに変更するのは簡単です。外周から伸びる迷路の壁を一つ断ち切って、浮いた壁にしてやれば周回ルートができます。それでは以下の赤丸部分を削除してみます。
テーブルを更新後、クエリを実行すると以下の通り60ステップと80ステップの２つのルートが出力されました。
Solution #1 (60 steps)
+=======================+=+===+===+
| ***** | | | |
+=+ ======+=+=+==*==+*| | +=+ +== |
| | | | |*** |*| | | |
| +=======+ | |*+===+*+=+=+ +=+ | |
|******* | *| *| |*** | | |
|*| +==*==+=+=+*+===+*| |*|*| | | |
|S| | * |***|* |***|G|*| | |
+=+=+==*==+*|*|*| | +==*+=+*+===+ |
| *****|***| | | ***** |
+===========+===+=+=+=============+
Solution #2 (80 steps)
+=======================+=+===+===+
| ***** | | | |
+=+ ======+=+=+==*==+*| | +=+ +== |
| | | | |*** |*| | | ***|
| +=======+ | |*+===+*+=+=+ +=+*|*|
|******* | *| *| |*****|*|*|
|*| +==*==+=+=+*+===+*| |*| |*|*|*|
|S| | * |***|* |***|G| |***|*|
+=+=+==*==+*|*|*| | +==*+=+ +===+*|
| *****|***| | | ***********|
+===========+===+=+=+=============+
ちなみに、クエリがマルチルートをグループ分けしているため、スタート地点やゴール地点が複数あっても問題なく動きます。ここらへんは、さすがSQLといえますね。以下のような感じで試してみてください。各スタートからそれぞれのゴールに到達するためのルートが合計４つ出力されます。（ただし一つのゴールが他のゴールをブロックする位置にある場合はそのゴールに到達できないため２つになります）
+=======================+=+===+===+
|G | | |S |
+=+ ======+=+=+== ==+ | | +=+ +== |
| | | | | | | | | |
| +=======+ | | +===+ +=+=+ +=+ | |
| | | | | | | |
| | +== ==+=+=+ +===+ | | | | | | |
|S| | | | | |G| | | |
+=+=+== ==+ | | | | +== +=+=+===+ |
| | | | | |
+===========+===+=+=+=============+
マルチスタート、マルチゴールの結果 (開く)
Solution #1 (20 steps)
+=======================+=+===+===+
|G | | |S**|
+=+ ======+=+=+== ==+ | | +=+ +==*|
| | | | | | | | | ***|
| +=======+ | | +===+ +=+=+ +=+*| |
| | | | |*****|*| |
| | +== ==+=+=+ +===+ | |*| |*|*| |
|S| | | | | |G| |***| |
+=+=+== ==+ | | | | +== +=+=+===+ |
| | | | | |
+===========+===+=+=+=============+
Solution #2 (50 steps)
+=======================+=+===+===+
|G******************** | | |S**|
+=+ ======+=+=+== ==+*| | +=+ +==*|
| | | | | |*| | | *|
| +=======+ | | +===+*+=+=+ +=+ |*|
| | | *| | | |*|
| | +== ==+=+=+ +===+*| | | | | |*|
|S| | | | |***|G| | |*|
+=+=+== ==+ | | | | +==*+=+=+===+*|
| | | | | ***********|
+===========+===+=+=+=============+
Solution #3 (50 steps)
+=======================+=+===+===+
|G**************** | | |S |
+=+ ======+=+=+==*==+ | | +=+ +== |
| | | | |*** | | | | |
| +=======+ | |*+===+ +=+=+ +=+ | |
|******* | *| | | | | |
|*| +==*==+=+=+*+===+ | | | | | | |
|S| | * |***|* | |G| | | |
+=+=+==*==+*|*|*| | +== +=+=+===+ |
| *****|***| | | |
+===========+===+=+=+=============+
Solution #4 (80 steps)
+=======================+=+===+===+
|G ***** | | |S |
+=+ ======+=+=+==*==+*| | +=+ +== |
| | | | |*** |*| | | ***|
| +=======+ | |*+===+*+=+=+ +=+*|*|
|******* | *| *| |*****|*|*|
|*| +==*==+=+=+*+===+*| |*| |*|*|*|
|S| | * |***|* |***|G| |***|*|
+=+=+==*==+*|*|*| | +==*+=+=+===+*|
| *****|***| | | ***********|
+===========+===+=+=+=============+
もっと大きな迷路で試す
少し大き目の迷路を作って試してみます。101x101の迷路を使用すると解くのに40秒ほどかかりました。ただし、打ち切りなしのブルートフォースサーチのため、迷路の種類によっては非常に時間がかかります。分岐やマルチールートの多い迷路だと終了しないかもしれません。まぁもともとSQLですからね。パフォーマンスについては目をつむりましょう。
101x101迷路の結果(開く)
Solution #1 (710 steps)
+===+=======+=====+=======+=====+===+=====+===+===+=======+=====+=====+===+=======+===+===+=========+
|S |*******|*****| | | | | | | | | | | | | | |
|*| |*+== |*|*+=+*| +=====+ ====+ | | | | +=+ | | | +==== | +== +==== | ==+ +==== | +=+ | | ==+== | |
|*| |*| |***| |*| | | | | | | | | | | | | | | | | | | |
|*+=+*| ==+=+=+ |*| +== | +===+ +=+===+=+== +===+== | ====+ +=+====== | +===+ | | | | +=+ +== +===+ |
|***|*| | *| | | | | | | | | | | | | | | | | | |
+==*|*+===+ | +==*+===+=+ | | | | +== | +===+ ==+ ==+===+ ==+ +=======+ | | | +=+=====+ | +===+ +=+ |
|***|*****| | | *****| | | | | | | |***| | | | | | | | |
|*==+=+==*| | +=+ ==+*| | +=+=====+===+ | ==+===+===+*|*+=+ +=====+===+ +=+ +====== +=+=====+===+ | |
|*****|***| | | |*| | |*********| | |*********|*| | | | | | | | |
+===+*|*+=+ +=+ +===+*| +== |*+=====+*| +===+*+=======+*| | | ==+=+ | +==== | +=====+ ==+ | | +===+ |
| |*|*| | | | |*| |***|*| |* |***|*| *| | | | | | | | | | | | | |
| | |*|*| ==+ | | | |*+=+*|*|*+==== |*==+*|*|*| +===+=+*| | +===+ +=+ | ====+=+ +== +== | +===+ | | |
| | |***| | | | |***|*|***| *** |*|***| | | |***| |***| | | | | | | | | |
| | +=+ +=+ +===+ +=+=+*|*+===+ ==+*==+ |*+===+ +== | +==*+=+*|*| | ==+=====+===+== +===+ | | | +===+
| | | | | |***| |***| |*| | | |***|***|*| | | | | | |
| +== | | | +== +==== +=+=+ ==+===+=+*+=+*| +=+ | ==+ |*+=+*+=+*| +=====+== | +=====+=======+=+ | | |
| | | | | | | | | | |*****| | | |*| |*|***| | | | | | | |
| | +=+=+ | | +=+ ====+ +==== | | | +=====+ | +=+===+=+*| |*|*==+ +=+== | ==+ | +=+ | +====== +===+ |
| | | | | | | | | | | | | | | | *****|***| | | | | | | | | | |
| | +== | +=+ | +===+ +=====+=+ +===+ ==+ ==+ | | | | +===+=+=+*| | | ==+== +===+ | +=+ +====== | | |
| | | | | | | | | | | | | | | | | |***|*| | | | | | | | | |
+=+ | +=+=+ +=+ +=+ | +== | | +=+ | +=+=+=+ | | +=+ | +== |*|*|*+===+== | | +== +===+ +=+=+=====+ | |
| | | | | | | | | | | | | | | | | |*|***| | | | | | | | | |
| +=+ | | | +===+ | +=+===+== | ==+ | | | | | | | ==+ | ==+*+=+=+ +===+=+ +==== | | | | | | ====+ | |
| | | | | | | | | | | | | | | | | | | |* |***| | | | | | | | | |
| | +===+ | | | +=+ | +=======+=+ | | | | | | | +===+ +== |*==+*|*+=+ | ==+===+=+ | | +=+ | +=======+
| | | | | | | | | | | | | | | |*****|***| | | | | | | | |
| ==+ | ==+===+=+ +=+ | ==+== ==+ | | | | | +=+==== | | +=+=====+==*| +====== | | | +=+ +===+ ====+ |
| | | | | | | | | | | | | | | | *********| | | | | | | |
+=+ | | +=====+===+ | +=+ +=+=+ | | +=+ +=+ | ==+===+ +=+=+*| ====+=+=+=+===+== | | | | | | +===+ | |
| | | | | | | | | | | | | | | |*| |***| | | | | | | | | | |
| +===+ +== | +=+ | +=+ | | | +=+=+=+ +===+=+=+ | ====+=+ |*+=+===+*|*| | | | +=+=+ | +===+ ====+ +=+
| | | | | | | | | | | | | | | |* |*****|*| | | | | |
+== ==+=+ ==+== | +=+ | | +=+ | +== +==== | | +=+=====+ | |*==+*+===+*| +=+=+ | +===+=======+=====+ |
| | | | | | | | | | | | | *****|*****| |***| | | | | |
+==== | +== +===+=+ | | | | ==+=+ +=+ ====+ +===+==== | +=====+=+*| ==+ |*|*| | | ====+== | | ==+ | |
| | | | | | | | | | | | | | | | | | |***| |*|*| | | | | | | |
| +===+ | ==+ | | | | | | +=+ | | | +=+== | ==+ +=====+ | ==+ |*==+===+ |*|*| | +=====+ ==+ | | +=+=+
| | | | | | | | | | | | | | | | | | |*******| |*|*| |*****| | | | | |
| +=+ | +===+=+===+ +=+=+== | ==+ | | | ==+== +=====+ | +== | +=====+*+=+*|*+===+*+=+*| ==+ | +== | |
| | | | | | | | | | | | | | | |*****|*******| |*| | | | | |
+== | | +== | ==+ +== | | +=+=+ | ==+ | +=====+ ==+ +=+=+ | | | | ==+===+ +===+ +=+ |*+== +=+ +===+ |
| | | | | | | | | | | | | | | | | | | | | | |*| | | |
| +=+== | ==+== | | ====+ | | | +==== | +==== +== +== | +=+=+=+=+==== | | +== | | | |*| ==+ ==+ +== |
| | | | | | | | | | | | | | | | | | | | | |*****| | | |
| | +===+===+ ==+ +===+ | | | | +=====+== ==+ | | | ==+ | ==+ | ====+=+ +=====+===+=+ ==+*+=+ | +===+
| | | | | | | | | | | | | | | | | | | | | |* | | | |
+=+ +== | | +===+=+ | | +===+ ==+ +=+ | | | | ==+=+== | +===+ +===+ +=+ | +== | +== +== |*| +=+ | | |
| | | | | | | | | | | | | | | | | | | | | | | | |*| | | | |
| ==+=+=+ | +===+ | | +=+== +=+ | | +===+=+ +===+ ====+==== | | +=+== +===+ ==+ | | | ==+*| | +=+ | |
| | | | | | | | | | | | | | | | | | | | | | | | |*| | | | |
+=+ | | ==+=+=+ +===+=+ | ==+ | | | | +== | | | +===+=+ ==+=+ | | +===+ | | | | | +=+===+*| | | ==+=+
| | | | | | | | | | | | | | | | | | | | | | | | | |*******| | |
| +== | +== | +===+== | +=+ +=+=+=+ | +===+ | | | +=+ +=+=+ | | | | ==+=+===+ +=+ |*======+===+=+ | |
| | | | | | | | | | | | | | | | | | | | |*******| | | | |
+==== | | ====+ +=+ +=+=+=+=+ | | +=====+ +===+ | | ==+ | +=+ +===+== | ==+ +== ==+=+====*| | | | | |
| | | | | | | | | | | | | | | | | | | |*****| | | | |
+=======+=+== | | ==+ | | | | | +===+ | +===+ +=+ +== | +=+ +== | +===+===+ +=+=====+*+===+ | | +=+=+
| | | | | | | | | | | | | | | | |*******|*****| | |***|
| ==+=+===+ +=+== | | +=+ +=+=+=+ | +=+== +=+=====+ ==+=====+ +=+ | +=====+=+ |*+===+ |*==+*+=+ |*|*|
| | | | | | | | | | | | | | | | | | | |*| | |***|***| |*|*|
| | | | +===+ +=+=+=+=+ +=+ | ====+=+ | +=+ +=====+== | ==+ | | ==+ | +== | | |*| | | +==*+=+*| |*|*|
| | | | | | | | | | | | | | | | | | | |*| | | ***|***|*|*|
| | | ==+ | | | | +== +== +=+==== | +== | ==+===+ ==+=+=+ +=+=+=+ | +=+ +=+=+=+*| +===+ ==+*+=+*|*|*|
| | | | | | | | | | | | | | | | | | | | | |***| | |***|*|*|*|
| | +== +=+ | | | | +=+=+=+ | ==+=+ +===+=+===+ +=+ | | +=+ +=+ +=+=+ +=+ | |*==+=+== +===+==*|*|*|*|
| | | | | | | | | | | | | | | | | | | | | | | | | |*****| |*******|*|*|*|
| +=+ ==+ ==+ | | +=+ | | +=+=+ +=+=+ | | | | | +=+=+ +===+== | | | | | | | +=+==*+===+*+=+===+*|*|*|
| | | | | | | | | | | | | | | | | | | | | | | | *******| | |***|*|
+=====+ +=+ +=+ | | | | +=+== +=+ | | | | | +=+=+ | +=+ ==+===+ | | +== | +== | +== | +=+ | | | +=+*|
| | | | | | | | | | | | | | | | | | | | | | | | | | | | |*|
+==== +== | | +=+=+=+=+ | | +== | +===+=====+ | ==+ | | | +== +=+=+ +=+ | +== +=+ +=+ | | | +===+ |*|
| | | | | | | | | | | | | | | | | | | | | | | | | |*|
| +===+ ==+=+=+ ==+ ==+=+ | +=+ | | ==+ +===+===+ +=+ +=+=======+ +== +=+=+ +=+ ==+ | | | +===+ | |*|
| | | | | | | | | | | | | | | | | | | | | |*|
| | | +==== | ==+ +=+ | ==+=+ | +===+=+ | | ==+ | | +=========+ +== | | | ==+ +=====+===+=====+===+*|
| | | | | | | | | | | | | | | | |*********| | | | | *|
| | | | ====+===+ +=+=+===+ | | | | | +=+ +== | | +=+*+=====+*+=====+ | | ====+ +=======+===+======*|
| | | | | | | | | | | | | | |***|*****|* | | | |********* |*******|
+===+ +=+== | | +=+ | | | +===+ +=+ | +===+ ==+===+*==+*+=+*|*| +===+=+=+=====+ |*====+=+*==+*+===+=+
| | | | | | | | | | | |*****| |*|*| |*****| | |*****| |*****| | |
| | ==+ | ==+ | | +=+===+ +== +=+== +===+=====+ | +===+=+ |*|*+=+*==+*| | | ====+===+*| +== ==+ | | |
| | | | | | | | | | | | | | |*|***|* |***| | | |*| | | |
| +== +=+=+ ==+===+ +== +=====+ | +=+ | | +== +=+ ==+ +=+ |*+=+*|*| +=+*| +===+ | ==+*+=====+ | +===+
| | | | | | | | | | | | | | | |***|***| |*| |*****|*******| | |
| +===+ | +=+=+ +===+ ==+ +== +===+ +=+ | +=+== +===+=+ | +==*+=+=+== |*+=====+*| |*+=====+*+===+ | |
| | | | | | | | | | | | | | | | * | |*********| |*| |*****| | |
+=+ +=+== | | +=+=+ +===+=+ +=+ +===+ | +== | +=+ +== +=+ | |*| +=====+=========+=+*+== ==+====*| | |
| | | | | | | | | | | | | | |*| | | |*|***********| | |
| ==+ ====+===+ | | | ==+ +=+ ==+=+ ==+ | ==+ +== +=====+=+=+*| | | +=+ +===+=+ | |*|*| | ======+=+ |
| | |***| | |*****| | | | | | | | |*| | | | | | | |***| | | |
+=+ +=+ | |*|*| +=+*+==*| | +== | +== | +===+===+ | ==+== | |*+===+ | ==+== | | +=+===+ +===+== | ==+
| | | | |*|*******|***| | | | | | |*****|*| | | | | | | | |
| +=+ +=+ |*+=====+ |*+=+=+=+ | +===+ | | +==== +=====+*+==*|*+== | +=+=+===+ +===+===+=+ +=+ ==+=+ |
| | |*| | |*|***| | |***| | | |*******|***|*| | | | | | | | | |
| ==+==== |*| +===+ |*|*|*| +=+=+*|*| +===+=====+*==+===+*==+*| ==+=+ | | | +===+ | +=+ +=+ +== | | |
|***| |*| | |*|*|*| |*****|*| |***|******* | |*****| | | | | | | | | | | |
|*|*| ====+*| +== ==+*|*|*+=+*+===+*+=+*|*|*========+ | +=====+==== | ==+ +==== | | | | | +=+ +=+ | |
|G|*********| |***|*****| *****|*** | | | | | | | |
+=+=========+=======+===+=====+=========+=============+=============+=====+=====+=====+===+===+=====+
102 rows selected.
Elapsed: 00:00:39.93
Oracleでの改良
オラクルは、深さ優先探査を指定しかつ探査の通し番号を取得することができます。これを利用すると経由セルのカンマ区切りリストを作らなくてもゴール後に経由セルを計算で取得することが可能です。これによって、VARCHAR2の最大4000バイトの制限という懸念事項がなくなるとともに、文字列の操作が不要となるため多少パフォーマンス的に有利になります。この場合searchとpath_cellsサブクエリが以下のように置き換わります。
...
search (x, y, lvl, gcell)
AS (SELECT h, v, 1, cell
FROM maze_cells
WHERE cell = 'S'
UNION ALL
SELECT h, v, lvl + 1, cell
FROM search r, maze_cells m
WHERE gcell != 'G' AND cell IN (' ', 'G', 'S')
AND (h, v) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)))
SEARCH DEPTH FIRST BY x, y SET search_id -- 深さ優先探索で通し番号をつける
CYCLE x, y SET cycle TO 1 default 0, -- サイクル禁止
path_cells (grp, n, cx, cy)
AS (SELECT DISTINCT
goal.rn,
s.lvl,
-- 各レベルで通し番号の最大値をとる（内輪で最もゴールに近い通し番号が道順となる)
FIRST_VALUE (s.x) OVER (PARTITION BY rn, s.lvl ORDER BY s.search_id DESC) id,
FIRST_VALUE (s.y) OVER (PARTITION BY rn, s.lvl ORDER BY s.search_id DESC) id
FROM (SELECT search_id, lvl, ROW_NUMBER() OVER (ORDER BY lvl) rn
FROM search
WHERE gcell = 'G' AND cycle = 0) goal,
search s
WHERE goal.search_id >= s.search_id AND -- ゴール以降の探索を除去
goal.lvl >= s.lvl -- コールより深い探索を除去
)
...
MySQL版
MySQLの再帰には、繰り返しを避けるCYCLE句がないため経由セルのパス（カンマ区切り文字列）をFIND_IN_SETで確認しています。マニュアルを読む限り一応これがMySQLでのサイクル回避の方法の様ですね。確認に使用する文字列は一つだけの方が扱いやすいので、迷路図を展開したセルには新たに連番(ID)をふってX,YではなくIDのみで処理しています。
MySQL 8.0.13で確認しました。
drop table if exists maze_map;
create table maze_map as
WITH RECURSIVE
maze_map(n, s, maze, cnt)
AS (SELECT 1, cast(REGEXP_SUBSTR(maze, '^.+$', 1, 1, 'm') as char(1000)),
maze, length(maze) - length(replace(maze, '\n', '')) -1
FROM (SELECT '
+=======================+=+===+===+
| | | | |
+=+ ======+=+=+== ==+ | | +=+ +== |
| | | | | | | | | |
| +=======+ | | +===+ +=+=+ +=+ | |
| | | | | | | |
| | +== ==+=+=+ +===+ | | | | | | |
|S| | | | | |G| | | |
+=+=+== ==+ | | | | +== +=+=+===+ |
| | | | | |
+===========+===+=+=+=============+
' maze) m
UNION ALL
SELECT n + 1,
REGEXP_SUBSTR(maze, '^.+$', 1, n + 1, 'm'),
maze, cnt
FROM maze_map
WHERE n < cnt
)
SELECT n, s FROM maze_map
;
WITH RECURSIVE
maze_seg (h, v, cell, s)
AS (SELECT 1, n, SUBSTR(s, 1, 1), s from maze_map
UNION ALL
SELECT h + 1, v, SUBSTR(s, h + 1, 1), s
FROM maze_seg
WHERE h < LENGTH(s)
),
maze_cells (h, v, cell, id)
AS (SELECT h, v, cell,
ROW_NUMBER () OVER (ORDER BY v, h)
FROM maze_seg
),
search (x, y, gcell, path)
AS (SELECT h, v, cell, CAST(id AS CHAR(4000))
FROM maze_cells
WHERE cell = 'S'
UNION ALL
SELECT h, v, cell, CONCAT(path, ',', id)
FROM search r, maze_cells m
WHERE gcell != 'G' AND cell IN (' ', 'G', 'S')
AND (h, v) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1))
AND FIND_IN_SET(id, path) = 0
),
path_cells(grp, n, cid, path) AS (
SELECT rn, 1, CAST(REGEXP_SUBSTR(path, '^[0-9]+') AS SIGNED), path
FROM (SELECT path,
ROW_NUMBER() OVER (ORDER BY LENGTH(path) - LENGTH(REPLACE(path,',',''))) rn
FROM search WHERE gcell = 'G') g
UNION ALL
SELECT grp, n + 1,
CAST(SUBSTR(REGEXP_SUBSTR(path, ',[0-9]+', 1, n), 2) AS SIGNED), path
FROM
path_cells
WHERE n < LENGTH(path) - LENGTH(REPLACE(path,',','')) + 1
)
SELECT CASE WHEN v is null
THEN CONCAT('Solution #', mc.grp, ' (', max(mc.steps) - 1, ' steps)')
ELSE CONCAT(' ',
GROUP_CONCAT(CASE WHEN cid IS NULL OR cell != ' '
THEN cell
ELSE '*'
END
ORDER BY h SEPARATOR ''))
END maze_solved
FROM (SELECT grp, steps, h, v, cell, id
FROM (SELECT h, v, cell, id
FROM maze_cells
UNION ALL
SELECT null, null, null, null) m,
(SELECT grp, count(*) steps FROM path_cells GROUP BY grp) s
) mc
LEFT JOIN path_cells pc
ON mc.id = pc.cid and mc.grp = pc.grp
GROUP BY mc.grp, v
ORDER BY mc.grp, v;
PostgreSQL版
ほぇーArrayって便利ですねー。OracleのTyepのようにオブジェクト作ったり宣言しなくても使えるのがいい！で、ここでは道順のセルをArrayで保持しています。行への展開もUNNESTで一発です。またサイクルの防止にANY関数を使用しているので、MySQLと同様、セルに連番をふっています。
PostgreSQL 11.0で確認しました。
drop table if exists maze_map;
CREATE TABLE maze_map AS
SELECT ROW_NUMBER() OVER (ORDER BY ORDINALITY) n, maze s
FROM REGEXP_SPLIT_TO_TABLE('
+=======================+=+===+===+
| | | | |
+=+ ======+=+=+== ==+ | | +=+ +== |
| | | | | | | | | |
| +=======+ | | +===+ +=+=+ +=+ | |
| | | | | | | |
| | +== ==+=+=+ +===+ | | | | | | |
|S| | | | | |G| | | |
+=+=+== ==+ | | | | +== +=+=+===+ |
| | | | | |
+===========+===+=+=+=============+
', '\s+\n') WITH ORDINALITY maze
WHERE maze <> '';
WITH RECURSIVE
maze_seg (h, v, cell, s)
AS (SELECT 1, n, SUBSTR(s, 1, 1), s
FROM maze_map
UNION ALL
SELECT h + 1, v, SUBSTR(s, h + 1, 1), s
FROM maze_seg
WHERE h < LENGTH(s)
),
maze_cells (h, v, cell, id)
AS (SELECT h, v, cell,
ROW_NUMBER () OVER (ORDER BY v, h)
FROM maze_seg
),
search (x, y, gcell, path)
AS (SELECT h, v, cell, ARRAY[id]
FROM maze_cells
WHERE cell = 'S'
UNION ALL
SELECT h, v, cell, path || id
FROM search r, maze_cells m
WHERE gcell != 'G' AND cell IN (' ', 'G', 'S')
AND (h, v) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1))
AND NOT id = ANY(path)
),
path_cells (grp, cid)
AS (SELECT ROW_NUMBER() OVER (ORDER BY ARRAY_LENGTH(path, 1)) rn,
UNNEST(path)
FROM search
WHERE gcell = 'G')
SELECT CASE WHEN v IS NULL
THEN 'Solution #' || mc.grp || ' (' || (MAX(mc.steps) - 1) || ' steps)'
ELSE ' ' ||
STRING_AGG (CASE WHEN cid IS NULL OR cell != ' '
THEN cell
ELSE '*'
END,
'' ORDER BY h)
END maze_solved
FROM (SELECT grp, steps, h, v, cell, id
FROM (SELECT * FROM maze_cells
UNION ALL
SELECT NULL, NULL, NULL, NULL) m,
(SELECT grp, COUNT(*) steps FROM path_cells GROUP BY grp) s) mc
LEFT JOIN path_cells pc
ON mc.id = pc.cid and mc.grp = pc.grp
GROUP BY mc.grp, v
ORDER BY mc.grp, v NULLS FIRST;
おわりに
MySQLとPostgreSQLは不慣れなので突っ込み歓迎です。