単一SQLクエリで迷路を解いてみよう

## はじめに

前回の「[単一SQLクエリでハノイの塔を解いてみよう](https://qiita.com/tlokweng/items/f8c2afb54d6f181d7f49)」に引き続いての再帰演習です。今回は迷路をSQL再帰で解きます。といっても迷路の解法自体は単純なブルートフォースサーチで特筆すべきことはあまりないので、追加として視覚的な迷路図に解答の道順をのせてちょっと見栄えのするSQLクエリにしてみます。さらに**ゴール到達に複数のルートが有る迷路も可**として、すべてのルートを短い順に出力します。前回と同じく**Oracle**のSQLで説明しつつ、最後に**PostgreSQL**版と**MySQL**版も載せておきます。

## 迷路の入力と出力

動きとしては、こういう迷路を使って、
![image.png](https://qiita-image-store.s3.amazonaws.com/0/179587/3a7dab12-2d6d-f8ae-8310-71996491a7f7.png)
こんな感じで道順をのせて迷路図を出力します。複数の道順がある場合はそれぞれの図を分けて出力します。
![image.png](https://qiita-image-store.s3.amazonaws.com/0/179587/2b85bbbb-d33e-4109-bab4-327743f40c1c.png)

迷路図は適当に作るかどっかからコピーしてきてください。。迷路の壁の文字はなんでも構いません。ちなみにここで使われている迷路はPL/SQLでやっつけで作成しました(^^)。

## 迷路テーブルの作成

まず迷路マップをテーブルを作ります。もちろんCTEにしてクエリにくっつけても構いません。CTEのほうが手軽に迷路を変更できるので便利ですが、PL/SQLや他のプログラムから直接迷路を作ることを考えてテーブルにしました。また迷路は必ずしも長方形や正方形である必要はありません。出っ張りを作ったり凸凹にしても大丈夫(のはず)です。迷路にはにスタート地点の**"S"**とゴール地点の**"G"**を適当に配置しておきます。

```sql:迷路定義

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 +===========+===+=+=+=============+
```

## 迷路を解くクエリの作成

### 迷路図の展開

ではクエリを作ります。上記テーブル内の迷路データは視覚的に理解しやすいようラインごとの文字列になってるため、まずはデータベースで探査しやすいよう一文字づつに分解しセル単位に落とし込みます。

```sql:
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句で制御しています。

```sql:
...
     -- スタートからゴールへの再帰探査
     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**を有効にします。

```sql:
...
    -- ゴールまでの経由セル座標のカンマ区切りパスの展開
    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で迷路マップの行ごとの文字列に再生成して終了です。複数ルートが有る場合を考慮して、それぞれの迷路図にタイトルを付加し解答番号とゴールまでのステップ数を表示しています。

```sql:
...
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;
```

### 全体の実行

以上をつなげると完成です。実行してみましょう。正しいの道順の載った迷路が出力されます。

```sql:迷路を解いて迷路図に道順を出力
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| |***|*|
    +=+=+==*==+*|*|*| | +==*+=+=+===+*|
    |      *****|***| | |  ***********|
    +===========+===+=+=+=============+
```

### マルチルート迷路

では、複数経路のある迷路で試してみましょう。迷路をマルチルートに変更するのは簡単です。外周から伸びる迷路の壁を一つ断ち切って、浮いた壁にしてやれば周回ルートができます。それでは以下の赤丸部分を削除してみます。
![image.png](https://qiita-image-store.s3.amazonaws.com/0/179587/eb75457d-27ac-5644-d9a1-ccef2b85072f.png)

テーブルを更新後、クエリを実行すると以下の通り60ステップと80ステップの２つのルートが出力されました。

```:マルチルート結果
Solution #1 (60 steps)
    +=======================+=+===+===+
    |                *****  | |   |   |
    +=+ ======+=+=+==*==+*| | +=+ +== |
    | |       | | |***  |*|   | |     |
    | +=======+ | |*+===+*+=+=+ +=+ | |
    |*******    |  *|    *| |***  | | |
    |*| +==*==+=+=+*+===+*| |*|*| | | |
    |S| |  *  |***|*    |***|G|*|   | |
    +=+=+==*==+*|*|*| | +==*+=+*+===+ |
    |      *****|***| | |  *****      |
    +===========+===+=+=+=============+
Solution #2 (80 steps)
    +=======================+=+===+===+
    |                *****  | |   |   |
    +=+ ======+=+=+==*==+*| | +=+ +== |
    | |       | | |***  |*|   | |  ***|
    | +=======+ | |*+===+*+=+=+ +=+*|*|
    |*******    |  *|    *| |*****|*|*|
    |*| +==*==+=+=+*+===+*| |*| |*|*|*|
    |S| |  *  |***|*    |***|G| |***|*|
    +=+=+==*==+*|*|*| | +==*+=+ +===+*|
    |      *****|***| | |  ***********|
    +===========+===+=+=+=============+
```

ちなみに、クエリがマルチルートをグループ分けしているため、スタート地点やゴール地点が複数あっても問題なく動きます。ここらへんは、さすがSQLといえますね。以下のような感じで試してみてください。各スタートからそれぞれのゴールに到達するためのルートが合計４つ出力されます。（ただし一つのゴールが他のゴールをブロックする位置にある場合はそのゴールに到達できないため２つになります）

```
+=======================+=+===+===+
|G                      | |   |S  |
+=+ ======+=+=+== ==+ | | +=+ +== |
| |       | | |     | |   | |     |
| +=======+ | | +===+ +=+=+ +=+ | |
|           |   |     | |     | | |
| | +== ==+=+=+ +===+ | | | | | | |
|S| |     |   |     |   |G| |   | |
+=+=+== ==+ | | | | +== +=+=+===+ |
|           |   | | |             |
+===========+===+=+=+=============+
```

<details><summary>マルチスタート、マルチゴールの結果 (開く)</summary><div>

```
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| |***|*|
    +=+=+==*==+*|*|*| | +==*+=+=+===+*|
    |      *****|***| | |  ***********|
    +===========+===+=+=+=============+
```
</div></details>


### もっと大きな迷路で試す

少し大き目の迷路を作って試してみます。101x101の迷路を使用すると解くのに40秒ほどかかりました。ただし、打ち切りなしのブルートフォースサーチのため、迷路の種類によっては非常に時間がかかります。分岐やマルチールートの多い迷路だと終了しないかもしれません。まぁもともとSQLですからね。パフォーマンスについては目をつむりましょう。

<details><summary>101x101迷路の結果(開く)</summary><div>

```
Solution #1 (710 steps)
    +===+=======+=====+=======+=====+===+=====+===+===+=======+=====+=====+===+=======+===+===+=========+
    |S  |*******|*****|       |     |   |     |   |   |       |     |     |   |       |   |   |         |
    |*| |*+== |*|*+=+*| +=====+ ====+ | | | | +=+ | | | +==== | +== +==== | ==+ +==== | +=+ | | ==+== | |
    |*| |*|   |***| |*| |     |       |   | |   |   |   |     | |         |     |     | |   | |   |   | |
    |*+=+*| ==+=+=+ |*| +== | +===+ +=+===+=+== +===+== | ====+ +=+====== | +===+ | | | | +=+ +== +===+ |
    |***|*|     |    *|     | |   | |     |     |       |         |       | |   | | |     | | |   |     |
    +==*|*+===+ | +==*+===+=+ | | | | +== | +===+ ==+ ==+===+ ==+ +=======+ | | | +=+=====+ | +===+ +=+ |
    |***|*****| | |  *****|   | |     |   | |       |   |***|   |           | | |         |         | | |
    |*==+=+==*| | +=+ ==+*| | +=+=====+===+ | ==+===+===+*|*+=+ +=====+===+ +=+ +====== +=+=====+===+ | |
    |*****|***| |   |   |*| |   |*********| |   |*********|*| |       |   |     |       |       |     | |
    +===+*|*+=+ +=+ +===+*| +== |*+=====+*| +===+*+=======+*| | | ==+=+ | +==== | +=====+ ==+ | | +===+ |
    |   |*|*|   | | |   |*| |***|*|     |*  |***|*|        *| | |   |   | |     | |     |   | |   |   | |
    | | |*|*| ==+ | | | |*+=+*|*|*+==== |*==+*|*|*| +===+=+*| | +===+ +=+ | ====+=+ +== +== | +===+ | | |
    | | |***|   |   | | |***|*|***|    ***  |*|***| |   | |***| |***| |   |         |   |   | |   | |   |
    | | +=+ +=+ +===+ +=+=+*|*+===+ ==+*==+ |*+===+ +== | +==*+=+*|*| | ==+=====+===+== +===+ | | | +===+
    | |   |   |     |     |***|       |***| |*|   |     | |***|***|*| |         |               | | |   |
    | +== | | | +== +==== +=+=+ ==+===+=+*+=+*| +=+ | ==+ |*+=+*+=+*| +=====+== | +=====+=======+=+ | | |
    | |   | | | |   |       |     |   | |*****| |   |     |*| |*|***|       |   | |     |         |   | |
    | | +=+=+ | | +=+ ====+ +==== | | | +=====+ | +=+===+=+*| |*|*==+ +=+== | ==+ | +=+ | +====== +===+ |
    | | |   | | | | |     |       | |   |       | | |   |  *****|***| | |   |   |   | | | |           | |
    | | +== | +=+ | +===+ +=====+=+ +===+ ==+ ==+ | | | | +===+=+=+*| | | ==+== +===+ | +=+ +====== | | |
    | | |   |   | |     | |     |   |   |   |   | |   | | |   |***|*|   |   |   |   |   |   |       | | |
    +=+ | +=+=+ +=+ +=+ | +== | | +=+ | +=+=+=+ | | +=+ | +== |*|*|*+===+== | | +== +===+ +=+=+=====+ | |
    |   | |   |     | | |     |   |   |   |   | | | |   | |   |*|***|       | |     |   | |   |     | | |
    | +=+ | | | +===+ | +=+===+== | ==+ | | | | | | | ==+ | ==+*+=+=+ +===+=+ +==== | | | | | | ====+ | |
    | | |   | | |     |   |       |   | | | | | | | |   | |   |*  |***|   |   |     | | | | | |         |
    | | +===+ | | | +=+ | +=======+=+ | | | | | | | +===+ +== |*==+*|*+=+ | ==+===+=+ | | +=+ | +=======+
    |   |     |   | |   | |         | | | | | |   |       |   |*****|***| |       | | | |   |   |       |
    | ==+ | ==+===+=+ +=+ | ==+== ==+ | | | | | +=+==== | | +=+=====+==*| +====== | | | +=+ +===+ ====+ |
    |   | |           | | |   |     | | | | | | |       |   |  *********|           | |   | |   |     | |
    +=+ | | +=====+===+ | +=+ +=+=+ | | +=+ +=+ | ==+===+ +=+=+*| ====+=+=+=+===+== | | | | | | +===+ | |
    | |   | |     |   | |   |   | |   |   |     |   |     |   |*|     |***| |   |   | | | |   |     | | |
    | +===+ +== | +=+ | +=+ | | | +=+=+=+ +===+=+=+ | ====+=+ |*+=+===+*|*| | | | +=+=+ | +===+ ====+ +=+
    |       |   |   | |   | | | |   |   |     |   | |       | |*  |*****|*|   | | |     |               |
    +== ==+=+ ==+== | +=+ | | +=+ | +== +==== | | +=+=====+ | |*==+*+===+*| +=+=+ | +===+=======+=====+ |
    |     |     |       | | | |   |     |     | |         | |  *****|*****| |***| | |           |     | |
    +==== | +== +===+=+ | | | | ==+=+ +=+ ====+ +===+==== | +=====+=+*| ==+ |*|*| | | ====+== | | ==+ | |
    |     | |   |   | | | | | |   | | | |     |     |     | |     |***|     |*|*| | |     |   | |   |   |
    | +===+ | ==+ | | | | | | +=+ | | | +=+== | ==+ +=====+ | ==+ |*==+===+ |*|*| | +=====+ ==+ | | +=+=+
    | |   | |     |   | |   |   |   | | | |   |   |       | |   | |*******| |*|*|   |*****|   | | |   | |
    | +=+ | +===+=+===+ +=+=+== | ==+ | | | ==+== +=====+ | +== | +=====+*+=+*|*+===+*+=+*| ==+ | +== | |
    |   | |     |     |   |     |   |   | |       |     |   |   | |     |*****|*******| |*|   | | |   | |
    +== | | +== | ==+ +== | | +=+=+ | ==+ | +=====+ ==+ +=+=+ | | | | ==+===+ +===+ +=+ |*+== +=+ +===+ |
    |   |   |   |   | |     | |   | |     | |     |   |   |   | |   |       | |   | |   |*|   |   |     |
    | +=+== | ==+== | | ====+ | | | +==== | +==== +== +== | +=+=+=+=+==== | | +== | | | |*| ==+ ==+ +== |
    | |     |   |   | |     | | | | |     |       |   |   | |     |       | |     |   | |*****|   | |   |
    | | +===+===+ ==+ +===+ | | | | +=====+== ==+ | | | ==+ | ==+ | ====+=+ +=====+===+=+ ==+*+=+ | +===+
    | | |   |       |     | |   |   |     |     |   | |   | |   | |     |   |     |     |   |*  | | |   |
    +=+ +== | | +===+=+ | | +===+ ==+ +=+ | | | | ==+=+== | +===+ +===+ +=+ | +== | +== +== |*| +=+ | | |
    |       | | |     | | |     |   | | |   | | |   |     |     | |   |   |   |   | |   |   |*| |   | | |
    | ==+=+=+ | +===+ | | +=+== +=+ | | +===+=+ +===+ ====+==== | | +=+== +===+ ==+ | | | ==+*| | +=+ | |
    |   | |   |     |   |   |   | | |   |     | |   |     |     | | |     |   |   | | | |   |*| | |   | |
    +=+ | | ==+=+=+ +===+=+ | ==+ | | | | +== | | | +===+=+ ==+=+ | | +===+ | | | | | +=+===+*| | | ==+=+
    | |   |     | |       | |   |   | | | |   | | | |   |     |   | | |     |   | | | |*******|   |     |
    | +== | +== | +===+== | +=+ +=+=+=+ | +===+ | | | +=+ +=+=+ | | | | ==+=+===+ +=+ |*======+===+=+ | |
    |     | |     |   |   |   |   |   |       |   | | |   | |   | |   |   |     |     |*******|   | | | |
    +==== | | ====+ +=+ +=+=+=+=+ | | +=====+ +===+ | | ==+ | +=+ +===+== | ==+ +== ==+=+====*| | | | | |
    |       |     | |   |   |   | | |       |     | | |     | |       |   |   | |       |*****| | |   | |
    +=======+=+== | | ==+ | | | | | +===+ | +===+ +=+ +== | +=+ +== | +===+===+ +=+=====+*+===+ | | +=+=+
    |         |   |     | |   |   | |   | |     |     |   |     |   | |           |*******|*****| | |***|
    | ==+=+===+ +=+== | | +=+ +=+=+=+ | +=+== +=+=====+ ==+=====+ +=+ | +=====+=+ |*+===+ |*==+*+=+ |*|*|
    |   | |     |     | |   |   |     |   |   |       |   |     | |   | |     | | |*|   | |***|***| |*|*|
    | | | | +===+ +=+=+=+=+ +=+ | ====+=+ | +=+ +=====+== | ==+ | | ==+ | +== | | |*| | | +==*+=+*| |*|*|
    | | |   |   | | |     |   | |       |   |   |         |   |   |   |   |   |   |*| |   |  ***|***|*|*|
    | | | ==+ | | | | +== +== +=+==== | +== | ==+===+ ==+=+=+ +=+=+=+ | +=+ +=+=+=+*| +===+ ==+*+=+*|*|*|
    | | |   | | | | | |   |   |       | |   |       |   |   |   |   |   |   |   |***|     |   |***|*|*|*|
    | | +== +=+ | | | | +=+=+=+ | ==+=+ +===+=+===+ +=+ | | +=+ +=+ +=+=+ +=+ | |*==+=+== +===+==*|*|*|*|
    | | |   |   | | | | |   |   |   |   |   | |   |   |   |   |   |   | | | | | |*****|   |*******|*|*|*|
    | +=+ ==+ ==+ | | +=+ | | +=+=+ +=+=+ | | | | | +=+=+ +===+== | | | | | | | +=+==*+===+*+=+===+*|*|*|
    |       |     | | |   |   |   |   | | | | | |   |   | |       | | | |   | |   |  *******| |   |***|*|
    +=====+ +=+ +=+ | | | | +=+== +=+ | | | | | +=+=+ | +=+ ==+===+ | | +== | +== | +== | +=+ | | | +=+*|
    |     |   | |   |   | | | |     | |   |       |   |   |   |   | |   |   | |   | |   | |   | |   | |*|
    +==== +== | | +=+=+=+=+ | | +== | +===+=====+ | ==+ | | | +== +=+=+ +=+ | +== +=+ +=+ | | | +===+ |*|
    |     |   |   |   |     | | |   | |         |     | | | |         |   |   |   |   | | | | |     | |*|
    | +===+ ==+=+=+ ==+ ==+=+ | +=+ | | ==+ +===+===+ +=+ +=+=======+ +== +=+=+ +=+ ==+ | | | +===+ | |*|
    | |   |     |     |   |   |   | |     | |       | |             |     | |   | |     |   |     |   |*|
    | | | +==== | ==+ +=+ | ==+=+ | +===+=+ | | ==+ | | +=========+ +== | | | ==+ +=====+===+=====+===+*|
    | | | |     |   |   |       | | |   |   | |   | | | |*********|     | | |               |          *|
    | | | | ====+===+ +=+=+===+ | | | | | +=+ +== | | +=+*+=====+*+=====+ | | ====+ +=======+===+======*|
    |   | |     |     |   |   |   | | | | |   |   |   |***|*****|*      |   |     | |*********  |*******|
    +===+ +=+== | | +=+ | | | +===+ +=+ | +===+ ==+===+*==+*+=+*|*| +===+=+=+=====+ |*====+=+*==+*+===+=+
    |       |   | | |   |   | |   |     |         |   |*****| |*|*| |*****| |       |*****| |*****|   | |
    | | ==+ | ==+ | | +=+===+ +== +=+== +===+=====+ | +===+=+ |*|*+=+*==+*| | | ====+===+*| +== ==+ | | |
    | |   | |     |   |     |     | |   |   |     | |     |   |*|***|*  |***| |     |   |*|       | |   |
    | +== +=+=+ ==+===+ +== +=====+ | +=+ | | +== +=+ ==+ +=+ |*+=+*|*| +=+*| +===+ | ==+*+=====+ | +===+
    | |     | |   |     |   |     |   |   | | |     |   |   | |***|***|   |*|     |*****|*******|   |   |
    | +===+ | +=+=+ +===+ ==+ +== +===+ +=+ | +=+== +===+=+ | +==*+=+=+== |*+=====+*| |*+=====+*+===+ | |
    | |   |   | |   |   |     |   |     | | |   |   |     |   |  *  |     |*********| |*|     |*****| | |
    +=+ +=+== | | +=+=+ +===+=+ +=+ +===+ | +== | +=+ +== +=+ | |*| +=====+=========+=+*+== ==+====*| | |
    |   |         |   | |   |   |   |     | |   | |   |     |   |*| |     |           |*|***********| | |
    | ==+ ====+===+ | | | ==+ +=+ ==+=+ ==+ | ==+ +== +=====+=+=+*| | | +=+ +===+=+ | |*|*| | ======+=+ |
    |   |     |***| | |*****| | |     |   |     |     |       | |*|   | |   |   | | | |***| |       |   |
    +=+ +=+ | |*|*| +=+*+==*| | +== | +== | +===+===+ | ==+== | |*+===+ | ==+== | | +=+===+ +===+== | ==+
    | |   | | |*|*******|***|   |   |     | |       |     |*****|*|   | |       | |         |   |   |   |
    | +=+ +=+ |*+=====+ |*+=+=+=+ | +===+ | | +==== +=====+*+==*|*+== | +=+=+===+ +===+===+=+ +=+ ==+=+ |
    |   |     |*|     | |*|***|   | |***| |   |     |*******|***|*|   |   | |   |     |   |   |       | |
    | ==+==== |*| +===+ |*|*|*| +=+=+*|*| +===+=====+*==+===+*==+*| ==+=+ | | | +===+ | +=+ +=+ +== | | |
    |***|     |*| |     |*|*|*| |*****|*| |***|*******  |   |*****|     |   | |     | | |   |   |   | | |
    |*|*| ====+*| +== ==+*|*|*+=+*+===+*+=+*|*|*========+ | +=====+==== | ==+ +==== | | | | | +=+ +=+ | |
    |G|*********|       |***|*****|    *****|***          |             |     |     |     |   |   |     |
    +=+=========+=======+===+=====+=========+=============+=============+=====+=====+=====+===+===+=====+

102 rows selected.

Elapsed: 00:00:39.93
```

</div></details>


### Oracleでの改良

オラクルは、深さ優先探査を指定しかつ探査の通し番号を取得することができます。これを利用すると経由セルのカンマ区切りリストを作らなくてもゴール後に経由セルを計算で取得することが可能です。これによって、VARCHAR2の最大4000バイトの制限という懸念事項がなくなるとともに、文字列の操作が不要となるため多少パフォーマンス的に有利になります。この場合searchとpath_cellsサブクエリが以下のように置き換わります。

```sql:カンマ区切りリストを使用しない方法
...
     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で確認しました。

```sql:MySQL版テーブル作成
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
;
```

```sql:MySQL版迷路を解く
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で確認しました。

```sql:PostgreSQL版テーブル作成
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 <> '';
```

```sql:PostgreSQL版迷路を解く
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は不慣れなので突っ込み歓迎です。