単一SQLクエリで穴掘り法や壁伸ばし法を使って迷路をちゃんと作ってみる

## はじめに

**単一SQLクエリで迷路を作ります**。以下**Oracle**で説明していますが、**PostgreSQL**版も記載しています。

> 追記：MySQL版は、LATERALが8.0.14でサポートされた後別記事に記載しました。
> [LATERALが実装されたのでMySQLでもSQLクエリで迷路を作ってみる](https://qiita.com/tlokweng/items/5c1fa7d2ef9170108e88)

## 迷路を作るアルゴリズム

迷路を作るアルゴリズムは[たくさんある](https://en.wikipedia.org/wiki/Maze_generation_algorithm)ようですが、一般的なのはこの３つでしょう。以下のサイトで詳しく説明されており、ここでは簡単に説明します。クエリを作る難易度からいうと、あきらかに「（易）壁倒し法 >>> 穴掘り法 >>> 壁伸ばし法（難）」ですね。
> [迷路自動生成アルゴリズム](http://www5d.biglobe.ne.jp/stssk/maze/make.html)

**壁倒し法**
奇数x奇数の位置にある壁を上下左右に倒していくだけです。壁を順に倒していくだけなので非常に簡単で高速ですが、迷路の解答が非常に単調になります。見た目は迷路ですが迷路としてはあまり使えないレベルです。壁を倒す条件は、倒せる方向が一番上のラインは上下左右、その後は下左右のみで、前に倒した壁に重ならないことです。

**穴掘り法**
偶数x偶数の位置にあるセルから上下左右ランダムに穴を掘りながら一度に2セルづつ進んでいきます。掘り進む条件はこれまでに掘った穴に一切ぶつかってはいけないこと。上下左右どこにも進めなくなったらラウンドを終了し、これまでに掘ってきた穴のどこか一つ(偶数x偶数)をランダムに選び、そこから分岐してまた穴掘りを繰り返します。分岐する場所がなくなれば終了です。

**壁伸ばし法**
奇数x奇数の位置にある未接続の壁セルから上下左右ランダムに壁を伸ばしながら2セルづつ進んでいきます。伸ばす条件は現在のラウンドで伸ばした壁（ランダムに選んだスタート地点から続く壁）にぶつかってはいけないこと。これを外周や既存の壁にぶつかるまで続けます。ただし、現在のラウンドで伸ばした壁の袋小路にはいって進めなくなった場合は、ラウンドを最初からやり直します。未接続の壁がすべて接続されれば終了です。

## 壁倒し法

壁倒し法は、行間参照して倒す壁が重ならないようにするだけでいいので、モデル句を使用すれば簡単にできます。まず以下のような奇数x奇数の位置に倒す壁のある迷路の土台をつくります。
![image.png](https://qiita-image-store.s3.amazonaws.com/0/179587/257f1aa1-f8cb-9e2d-e82d-38e24e880670.png)

次に、モデルのルール句の一行目で左上から右下に向かって順番に壁をランダム方向に倒していき、二行目で倒した方向の通路に壁を追加します。最後にLISTAGGで整形して終了です。この方法であれば大きな迷路も非常に高速に作成できますが、いかんせん迷路自体がなんちゃってなのでやはり、他の方法でちゃんとした迷路を目指します。

```sql:壁倒し法(Oracle)
WITH
cells (x, y, c)                        -- 迷路の土台セル作成
    AS (SELECT MOD(LEVEL, px) + 1,
               CEIL(LEVEL / px),
               CASE WHEN MOD(LEVEL, px) + 1 in (1, px) OR
                         CEIL(LEVEL / px) in (1, py)
                         THEN '#'
                    WHEN MOD(MOD(LEVEL, px) + 1, 2) = 1 AND
                         MOD(CEIL(LEVEL / px), 2) = 1
                         THEN 'X'
                         ELSE ' '
               END
FROM (SELECT 101 px, 101 py FROM DUAL) -- 迷路のサイズ 101*101
CONNECT BY LEVEL <=  px * py
)
SELECT LISTAGG(DECODE(c, 'X', '#', c)) WITHIN GROUP (ORDER BY x) -- 整形
FROM  (SELECT x, y, dr, c
       FROM cells
       MODEL
       DIMENSION BY (x, y)
       MEASURES (c, 0 dr)
       RULES (dr[FOR (x, y) IN (SELECT x, y FROM cells WHERE c = 'X')] ORDER BY y, x    -- 壁のあるセルのみ
                  = TRUNC(DBMS_RANDOM.VALUE(2 - DECODE(cv(y), 3, 1, 0),                 -- 一番上だけ上方向も含める
                                            5 - DECODE(dr[CV() - 2, CV()], 2, 1, 0))),  -- 左隣に壁があれば重ねない
              c[FOR (x, y) IN (SELECT x, y FROM cells WHERE c= ' ')] ORDER BY y, x      -- 壁のないセルのみ
                  = CASE WHEN dr[CV(), CV() + 1] = 1 OR dr[CV() - 1, CV()] = 2 OR       -- 壁倒し方向
                              dr[CV(), CV() - 1] = 3 OR dr[CV() + 1, CV()] = 4          -- 1/上 2/右 3/下 4/左
                         THEN '#' ELSE ' '
                    END
              )
       )
GROUP BY y
ORDER BY y;
```

## 穴掘り法

穴掘り法のイメージとしては以下の感じですね。ランダムに選ばれた``A1``から出発し掘り進み、``B1``で袋小路にはいったので、これまで掘った道からランダムに新規セル``A2``を選択肢し、そこから分岐して進み``B2``の袋小路に到達。これを繰り返して進んだり分岐できるセルがなくなれば完成になります。
![image.png](https://qiita-image-store.s3.amazonaws.com/0/179587/c0ee18df-32ef-f96f-1235-266b3502fe4c.png)

#### PL/SQL版（参考）

まずは、動きの理解しやすいPL/SQLで見てみます。穴を掘り進める部分の内側のループと袋小路に入って場合に分岐の新規セルを選択する外側のループの二重ループになっています。これをそのまま再帰クエリに置き換えます。

<details><summary>PL/SQL穴掘り法 (開く)</summary><div>

```sql:コレクションの作成
CREATE OR REPLACE TYPE maze_cell_typ AS OBJECT (
    x NUMBER,        -- X座標
    y NUMBER,        -- Y座標
    c VARCHAR2(1),   -- セルの文字
    id NUMBER);      -- 通し番号
/
CREATE OR REPLACE TYPE maze_typ AS TABLE OF maze_cell_typ;
/
```
```sql:穴掘り法（PL/SQL）
SET SERVEROUT ON

DECLARE
p_size_x	number := 41;              -- 横サイズ
p_size_y	number := 21;              -- 縦サイズ

cells		maze_typ := maze_typ();    -- 迷路セル
roadcells	maze_typ := maze_typ();    -- 分岐可能セル保持用

scell		maze_cell_typ;             -- 現在セル
ncell		maze_cell_typ;             -- 次に移動するセル
bcell		maze_cell_typ;             -- 現在と次の間のセル

BEGIN
-- 迷路のサイズ条件 5x5以上で奇数
IF p_size_x < 5 OR mod(p_size_x, 2) = 0 OR 
   p_size_y < 5 OR mod(p_size_y, 2) = 0
THEN
     RAISE_APPLICATION_ERROR(-20000, 'The length and width must be odd numbers of 5 or larger.');
     RETURN;
END IF;

-- すべて壁'#'である迷路のベースを作ってcellsコレクションに保持
SELECT maze_cell_typ(MOD(LEVEL, p_size_x) + 1, CEIL(LEVEL / p_size_x), '#', LEVEL)
       BULK COLLECT INTO cells
FROM   DUAL CONNECT BY LEVEL <=  p_size_x * p_size_y;

-- 最初の開始点を(偶数x偶数)セルの中からランダムに選ぶ
SELECT v INTO scell
FROM  (SELECT VALUE(t) v,
              ROW_NUMBER() OVER (ORDER BY DBMS_RANDOM.VALUE) rn
       FROM   TABLE(cells) t
       WHERE  MOD(x, 2) = 0 and MOD(y, 2) = 0)
WHERE rn = 1;

roadcells.EXTEND(cells.count);  -- 分岐可能セルを保持するための迷路と同じ大きさに拡張
roadcells(scell.id) := scell;   -- 開始点セルを分岐可能セルリストに追加
cells(scell.id).c := ' ';       -- 開始点セルを道として確定

LOOP
    -- 分岐可能セルリストの中から開始点セルとしてランダムに一つ選ぶ
    -- 選ぶセルがなければ迷路は完成なのでループを抜ける
    BEGIN
    SELECT v INTO scell
    FROM  (SELECT VALUE(t) v,
                  ROW_NUMBER() OVER (ORDER BY DBMS_RANDOM.VALUE) rn
           FROM   TABLE(roadcells) t
           WHERE  id IS NOT NULL)
    WHERE rn = 1;

    EXCEPTION WHEN NO_DATA_FOUND THEN EXIT; -- 迷路完成
    END;

    LOOP
        -- 現在のセルの上下左右２つとなりでかつ"#"であるセルを進めるセルとして取得し、
        -- そのうちの一つをランダムで選ぶ(ncell)。同時に隣のセルも取得しておく(bcell)。
        -- 進めなければ、分岐可能セルリストから現在セルを削除し今回のラウンドを終了する
        BEGIN
        SELECT v, value(p) INTO ncell, bcell
        FROM  (SELECT value(t) v,
                      ROW_NUMBER() OVER (ORDER BY DBMS_RANDOM.VALUE(1, 1000)) rn
               FROM   TABLE(cells) t
               WHERE  t.c = '#' AND
                     (t.x, t.y) IN ((scell.x + 2, scell.y), (scell.x - 2, scell.y),  -- 二つ隣のセル
                                    (scell.x, scell.y + 2), (scell.x,  scell.y - 2))
               ) n,
               TABLE(cells) p
        WHERE rn = 1 AND
              p.x = scell.x + (n.v.x - scell.x)/2 AND -- 移動する方向の一つ隣のセル
              p.y = scell.y + (n.v.y - scell.y)/2;

        EXCEPTION WHEN NO_DATA_FOUND THEN
              roadcells.delete(scell.id);  -- 分岐可能セルリストから削除
              EXIT;
        END;

        cells(ncell.id).c := ' ';      -- 二つ隣のセルを道に確定
        cells(bcell.id).c := ' ';      -- 一つ隣のセルを道に確定
        roadcells(ncell.id) := ncell;  -- 次の探査対象セルを分岐可能セルリストに追加
        scell := ncell;                -- 次の探査対象セルをセット
    END LOOP;
END LOOP;

-- 行ごとにまとめて迷路図を出力
FOR i IN (SELECT  y, LISTAGG (c) WITHIN GROUP (ORDER BY x) l
          FROM    TABLE(cells)
          GROUP BY y
          ORDER BY y)
LOOP
    DBMS_OUTPUT.PUT_LINE(i.l);
END LOOP;

END;
/
```
</div></details>

#### 単一クエリ(Oracle)版

二重ループ部分は、ラテラル句内でユニオンを使って分岐させることで実現可能です。またラテラル内のサブクエリが深くなっても「副問合せの多重飛び参照」によって直接再帰クエリのカラムを参照できるので全く問題になりません。ともにOracle 12cからの機能であり再帰クエリはそれらのおかげで自由度が上がっています。PostgreSQLも同様のことができるようです。

ここで必要となる再帰は本来の再帰ではなくただのループです。再帰内では現在位置とこれまで通ったセルのカンマ区切り文字列を受け取り、その上下左右セルの中からこれまで通った道にぶつからないように次に進むセルをランダムに決定します。進むセルがあればカンマ区切り文字列を追加して次のレベルへ、進めるセルがなければフラグをセットして(action=1)そのまま次のレベル進み次レベルではフラグに従い新規の分岐セルをランダムに選択します。プログラムでフラグを使用して二重ループを単一ループに書き換えることをイメージすれば理解しやすいのではないかと思います。

```sql:穴掘り法(Oracle12c)
WITH
msize(size_x, size_y) AS (SELECT 51, 21 FROM DUAL), -- 迷路のサイズ定義
moves(move_x, move_y) AS (SELECT +2, 0 FROM DUAL UNION ALL SELECT 0, +2 FROM DUAL UNION ALL
                          SELECT -2, 0 FROM DUAL UNION ALL SELECT 0, -2 FROM DUAL),
cells (x, y) -- 迷路サイズのセル作成
    AS (SELECT MOD(LEVEL, size_x) + 1, CEIL(LEVEL / size_x)
        FROM  msize CONNECT BY LEVEL <=  size_x * size_y
        ),
mazedig (n, x, y, cx, cy, action, path)
    AS (-- セルの中から開始点(偶数x偶数)をランダムで一つ選ぶ
        SELECT 1, x, y, x, y, 0, ',' || x || '/' || y || ','
        FROM  (SELECT x, y,
                      ROW_NUMBER() OVER (ORDER BY DBMS_RANDOM.VALUE) rn
               FROM   cells
               WHERE  MOD(x, 2) = 0 and MOD(y, 2) = 0)
        WHERE rn = 1
        UNION ALL
        -- パフォーマンスのために、ACTIONフラグで必要なときだけ分岐の道の計算を行う
        -- 継続して伸ばすセルが袋小路に入った場合にNULLが選択されACTIONがセットされる
        SELECT n + 1, s.x, s.y, s.cx, s.cy,
               DECODE(s.flg, 1, 1, 0),
               path || DECODE(s.flg, 1, '', s.str || ',')
        FROM   mazedig r,
               msize   m,
               LATERAL (SELECT i.x, i.y, i.x || '/' || i.y str, i.flg,
                               i.x - (i.x - i.nx)/2 cx,
                               i.y - (i.y - i.ny)/2 cy,
                               ROW_NUMBER() OVER (ORDER BY flg, DBMS_RANDOM.VALUE) rn
                        FROM (-- 既存の道からの分岐計算（前レベルで袋小路に入った場合のみ）
                              SELECT 2 flg, b.x + move_x x, b.y + move_y y, b.x nx, b.y ny
                              FROM   moves,
                                    (SELECT TO_NUMBER(SUBSTR(r.path, 
                                                      INSTR(r.path, ',', 1, level) + 1, 
                                                      INSTR(r.path, '/', 1, level)
                                                    - INSTR(r.path, ',', 1, level) - 1)) x,
                                            TO_NUMBER(SUBSTR(r.path, 
                                                      INSTR(r.path, '/', 1, level) + 1, 
                                                      INSTR(r.path, ',', 1, level + 1)
                                                    - INSTR(r.path, '/', 1, level) - 1)) y
                                     FROM   dual
                                     CONNECT BY LEVEL <= LENGTH(r.path)
                                                       - LENGTH(REPLACE(r.path, ',', '')) - 1
                                     ) b
                              WHERE b.x IS NOT NULL AND b.y IS NOT NULL AND
                                    r.action > 0  -- パフォーマンスのため必要なときのみ計算
                              UNION ALL
                              -- 継続して伸ばす穴掘り先
                              SELECT 0, r.x + move_x, r.y + move_y, r.x, r.y
                              FROM   moves WHERE r.action = 0
                              UNION ALL
                              -- 袋小路に入った場合に取得される
                              SELECT 1, NULL, NULL, NULL, NULL
                              FROM   DUAL  WHERE r.action = 0
                              ) i
                       WHERE  i.flg = 1 OR
                             (r.path NOT LIKE '%,' || i.x || '/' || i.y || ',%' AND 
                              i.x > 1 AND i.y > 1 AND i.x < size_x AND i.y < size_y)
               ) s
        WHERE  s.rn = 1
        )
        CYCLE n SET cycle TO 1 DEFAULT 0
SELECT  LISTAGG (c) WITHIN GROUP (ORDER BY x) maze
FROM   (SELECT c.x, c.y, NVL2(p.x, ' ', '#') c
        FROM   cells c,
              (SELECT  x,  y FROM mazedig UNION 
               SELECT cx, cy FROM mazedig) p
        WHERE  c.x = p.x (+) AND c.y = p.y (+)
       )
GROUP BY y
ORDER BY y;

MAZE
---------------------------------------------------------
###################################################
# #           #       #     #         #   #   #   #
# # ##### ##### # ####### # # ####### # # # ### # #
#   #   # #   # #     #   #         # # # # #   # #
##### ### # # # ##### # ##### ##### # ### # # ### #
#           # # #     #     #   # # #     #   #   #
# # ### ####### # # ##### # ### # # ########### ###
# # #     #     # #   #   #   #   # #   #   #   # #
### # ### # # ### # # ####### ##### # # # # # ### #
#   #   #   # #   # # #       #   # # #   #     # #
# ############# ##### # ####### # # # ######### # #
# #   #             # #     # # # # # #       # # #
# # ### ########### # ##### # # ### # ### ### # # #
#     #   #     #   #     # # #   #   #   #     # #
##### ### # ##### ####### # # ### ##### ### ##### #
#   #   #       # #     #   # #         # #   #   #
# ##### ####### # # ### ##### ####### ### ### # # #
#   #   #   #   # # # # #     #       #     # # # #
# # # ### # ### ### # # # ##### # ### ##### # # # #
# #   #   #         #   #       #   #       #   # #
###################################################

21 rows selected.

Elapsed: 00:00:01.64
```

カンマ区切り文字列の展開があるので冗長になっていますが、カンマ区切り文字列ではなくコレクションを使えばもっとシンプルになりかつVARCHAR2の文字列制限がなくなります。

#### PostgreSQL版

穴掘り法のPostgreSQL版です。PostgreSQL 11.0で確認しました。ARRAYが使えるのでかなりスッキリしますね。

```sql:穴掘り法(PostgreSQL)
WITH RECURSIVE
msize(size_x, size_y) AS (SELECT 51, 21),
moves(move_x, move_y) AS (SELECT +2, 0 UNION ALL SELECT 0, +2 UNION ALL
                          SELECT -2, 0 UNION ALL SELECT 0, -2),
cells (n, x, y)
    AS (SELECT 1, 1, 1
        UNION ALL
        SELECT n + 1, MOD(n, size_x) + 1, CAST((n / size_x) + 1 AS INTEGER)
        FROM   cells, msize
        WHERE  n < size_x * size_y
        ),
mazedig (n, x, y, cx, cy, action, path)
    AS (SELECT 1, x, y, x, y, 0, ARRAY[str]
        FROM  (SELECT x, y, CONCAT(x, '/', y) str,
                      ROW_NUMBER() OVER (ORDER BY RANDOM()) rn
               FROM   cells
               WHERE  MOD(x, 2) = 0 AND MOD(y, 2) = 0) c
        WHERE rn = 1
        UNION ALL
        SELECT r.n + 1, s.x, s.y, s.cx, s.cy,
               CASE WHEN s.flg = 1 THEN 1 ELSE 0 END,
               CASE WHEN s.flg = 1 THEN path ELSE path || s.str END
        FROM   msize   m,
               mazedig r
               CROSS JOIN LATERAL (
                        SELECT i.x, i.y, CONCAT(i.x, '/', i.y) str, i.flg,
                               i.x - (i.x - i.nx)/2 cx,
                               i.y - (i.y - i.ny)/2 cy,
                               ROW_NUMBER() OVER (ORDER BY flg, random()) rn
                        FROM (SELECT 2 flg, b.x + move_x x, b.y + move_y y, b.x nx, b.y ny
                              FROM   moves,
                                    (SELECT CAST(SUBSTRING(p FROM  '^\d+')      AS INTEGER) x,
                                            CAST(REGEXP_REPLACE(p, '^\d+/', '') AS INTEGER) y
                                     FROM  (SELECT UNNEST(r.path) p) pb) b
                              WHERE  r.action > 0
                              UNION ALL
                              SELECT 0 flg, r.x + move_x x, r.y + move_y y, r.x nx, r.y ny
                              FROM   moves
                              WHERE  r.action = 0
                              UNION ALL
                              SELECT 1, NULL, NULL, NULL, NULL
                              WHERE  r.action = 0
                              ) i
                       WHERE  i.flg = 1 OR
                             (NOT CONCAT(i.x, '/', i.y) = ANY(r.path) AND
                              i.x > 1 AND i.y > 1 AND i.x < size_x AND i.y < size_y)
               ) s
        WHERE  s.rn = 1
        )
SELECT  STRING_AGG (c, '' ORDER BY x) maze
FROM   (SELECT c.x, c.y, CASE WHEN p.x IS NOT NULL THEN ' ' ELSE '#' END c
        FROM   cells c
               LEFT JOIN (SELECT  x,  y FROM mazedig UNION
                          SELECT cx, cy FROM mazedig) p
                      ON  c.x = p.x AND c.y = p.y
       ) g
GROUP BY y
ORDER BY y;
```

## 壁伸ばし法

壁伸ばし法のイメージ図です。ランダムに選ばれた未接続の壁``A1``から進んでいき``B1``で外周に衝突して終了、次にまたランダムに選ばれた未接続の壁``A2``から出発し``B2``で既存の壁に到達して終了しています。進む条件としては、ループを回避するため現ラウンドで継続して伸ばしている壁に接続することはできません。そのため袋小路に入った場合は、ラウンドを捨ててやり直します。これを繰り返し未接続の壁(X)がなくなると迷路が完成します。
![image.png](https://qiita-image-store.s3.amazonaws.com/0/179587/35971c5e-e92d-a860-fa3c-a4427b9c1259.png)

#### PL/SQL版（参考）

まずは、PL/SQL版です。穴掘り法と同じ二重ループなので同じようにクエリに置換します。

<details><summary>PL/SQL壁伸ばし法 (開く)</summary><div>

壁伸ばし法と同じコレクションタイプを使用します。

```sql:壁伸ばし法（PL/SQL）
SET SERVEROUT ON

DECLARE
p_size_x	number := 41;              -- 横サイズ
p_size_y	number := 21;              -- 縦サイズ

cells		maze_typ;    -- 迷路セル
wallpath	maze_typ;    -- 壁セル保持用

scell		maze_cell_typ := NULL;
pcell		maze_cell_typ;

BEGIN
-- 迷路のサイズ条件 5x5以上で奇数
IF p_size_x < 5 OR mod(p_size_x, 2) = 0 OR 
   p_size_y < 5 OR mod(p_size_y, 2) = 0
THEN
    RAISE_APPLICATION_ERROR(-20000, 'The length and width must be odd numbers of 5 or larger.');
    RETURN;
END IF;

-- 奇数x奇数が壁(X)の迷路のベースを作成し、セルに展開してコレクションに格納
SELECT maze_cell_typ(
           MOD(LEVEL, p_size_x) + 1,
           CEIL(LEVEL / p_size_x),
           CASE WHEN MOD(LEVEL, p_size_x) + 1 in (1, p_size_x) OR
                     CEIL(LEVEL / p_size_x) in (1, p_size_y)
                     THEN '#'
                WHEN MOD(MOD(LEVEL, p_size_x) + 1, 2) = 1 AND
                     MOD(CEIL(LEVEL / p_size_x), 2) = 1
                     THEN 'X'
                ELSE ' '
           END,
           LEVEL)
       BULK COLLECT INTO cells
FROM   DUAL CONNECT BY LEVEL <=  p_size_x * p_size_y;

LOOP
    -- 未接続の壁(X)のセルの内一つを開始点としてランダムに選択
    -- scellがNULL以外のときはラウンドのやり直しなのでそのまま使用
    IF scell.id IS NULL
    THEN
        BEGIN
        SELECT v INTO scell
        FROM  (SELECT VALUE(t) v,
                      ROW_NUMBER() OVER (ORDER BY DBMS_RANDOM.VALUE) rn
               FROM   TABLE(cells) t
               WHERE  c = 'X')
        WHERE rn = 1;

        EXCEPTION WHEN NO_DATA_FOUND THEN EXIT;
        END;
    END IF;

    wallpath := maze_typ(scell);   -- 伸ばした壁に開始点をセットしてリセット

    LOOP
        -- 今回のラウンドで倒した壁のセル以外で上下左右のいずれかのセルにランダムに選択
        BEGIN
        SELECT v, value(p) INTO scell, pcell
        FROM  (SELECT value(t) v,
                      ROW_NUMBER() OVER (ORDER BY DBMS_RANDOM.VALUE) rn
               FROM   TABLE(cells) t
               WHERE
                      NOT value(t) MEMBER OF wallpath AND    -- 伸ばし中の壁への到達は禁止
                     (t.x, t.y) IN ((scell.x + 2, scell.y), (scell.x - 2, scell.y),  -- 二つ隣のセル
                                    (scell.x, scell.y + 2), (scell.x,  scell.y - 2))
              ) n,
              TABLE(cells) p
        WHERE rn = 1 AND
            p.x = scell.x + (n.v.x - scell.x)/2 AND  -- 移動する方向の一つ隣のセル
            p.y = scell.y + (n.v.y - scell.y)/2;

        EXCEPTION WHEN NO_DATA_FOUND THEN       -- 袋小路にはいったため進めず
            scell    := wallpath(1);            -- スタート地点に戻る
            wallpath := maze_typ();             -- 伸ばした壁を削除してEMPTYに
            EXIT;                               -- やり直すためにラウンドを終了
        END;

        -- 伸ばした壁を一時的に保存
        wallpath.EXTEND(1);
        wallpath(wallpath.LAST) := pcell;
        wallpath.EXTEND(1);
        wallpath(wallpath.LAST) := scell;

        EXIT WHEN scell.c <> 'X';		-- 既存の壁に到達
    END LOOP;

    -- wallpathがEMPTYならやり直し
    -- 伸ばした壁が確定なら迷路(cells)を更新
    IF wallpath IS NOT EMPTY
    THEN
        FOR i IN 1 .. wallpath.count
        LOOP
            cells(wallpath(i).id).c := '#';
        END LOOP;

        scell := null; -- 新規スタート
    END IF;
END LOOP;

-- 行ごとにまとめて迷路図を出力
FOR i IN (SELECT  y, LISTAGG (c) WITHIN GROUP (ORDER BY x) l
          FROM    TABLE(cells)
          GROUP BY y
          ORDER BY y)
LOOP
    DBMS_OUTPUT.PUT_LINE(i.l);
END LOOP;

END;
/
```
</div></details>

#### 単一クエリ(Oracle)版

壁伸ばし法でクエリを作る時問題となるポイントはなんといっても袋小路に入ったときのロールバックでしょう。これは、確定した壁のカンマ区切り文字列(path)と未確定の壁のカンマ区切り文字列(turn)を別に保持し、壁が確定した時に未確定壁を確定壁に追加することで実現します。袋小路に入った場合は、未確定壁を捨ててやり直します。

```sql:壁伸ばし法(Oracle12c）
WITH
-- 外壁が'#'、未接続壁が'X'の迷路の土台
cells (x, y, c)
    AS (SELECT MOD(LEVEL, size_x) + 1,
               CEIL(LEVEL / size_x),
               CASE WHEN MOD(LEVEL, size_x) + 1 in (1, size_x) OR
                         CEIL(LEVEL / size_x) in (1, size_y)
                         THEN '#'
                    WHEN MOD(MOD(LEVEL, size_x) + 1, 2) = 1 AND
                         MOD(CEIL(LEVEL / size_x), 2) = 1
                         THEN 'X'
                         ELSE ' '
               END
        FROM (SELECT 51 size_x, 21 size_y FROM DUAL) -- 迷路サイズ
        CONNECT BY LEVEL <=  size_x * size_y
        ),
-- 次に進むセルが外壁または既存壁であれば、Action = 1をセットし、次レベルで未接続のスタートセルを取得
-- 袋小路に入った場合は、そのまま未接続のスタートセルを取得し、現ラウンドの壁を捨てる
-- path 確定壁、turn 未確定（現ラウンド）壁、path2 確定接続壁、tunr2 未確定接続壁
mazewall (n, x, y, action, path, turn, path2, turn2)
     AS (SELECT 1, TO_NUMBER(NULL), TO_NUMBER(NULL), 1, -- 一行目はダミー
                CAST(',' AS VARCHAR2(4000)), CAST(',' AS VARCHAR2(4000)),
                CAST(',' AS VARCHAR2(4000)), CAST(',' AS VARCHAR2(4000))
         FROM   DUAL
         UNION ALL
         SELECT n + 1, s.x, s.y,
                s.wallhit,                                                   -- 壁接続でActionフラグをセット
                DECODE(s.wallhit, 0, r.path, r.path || substr(r.turn, 2)),   -- 壁接続で壁を確定
                CASE WHEN s.wallhit > 0 THEN ''                              -- 壁接続でラウンドを終了
                     WHEN s.flg     > 0 THEN ',' || s.x || '/' || s.y || ',' -- ラウンドスタート
                     ELSE r.turn || s.x || '/' || s.y || ','                 -- 壁を現ラウンドに追加
                END,
                DECODE(s.wallhit, 0, r.path2, r.path2 || substr(r.turn2, 2) || s.cx || '/' || s.cy || ','),
                DECODE(s.flg, 0, r.turn2 || s.cx || '/' || s.cy || ',', ',')
         FROM   mazewall r,
                LATERAL (SELECT x, y,              -- 進む先のセル
                                x - (x - px)/2 cx, -- 進む方向の接続セル
                                y - (y - py)/2 cy,
                                flg,               -- 継続/0、新規/1
                                wallhit,           -- 進む先が壁でない0、壁/1
                                ROW_NUMBER() OVER (ORDER BY flg, DBMS_RANDOM.VALUE) rn -- 継続壁伸ばしを優先
                         FROM (
                               -- 現在位置からの継続壁伸ばし(flg=0)
                               -- 外壁や既存壁に接続した場合は、wallhitをセット
                               SELECT c.x, c.y, r.x px, r.y py, 0 flg,
                                      CASE WHEN c.c = '#' OR -- 外壁
                                                r.path LIKE '%,' || c.x || '/' || c.y || ',%' -- 既存壁
                                           THEN 1 ELSE 0
                                      END wallhit
                               FROM   cells c
                               WHERE  r.action = 0 AND -- 前レベルで既存の壁に接続していない（継続伸ばし）
                                      r.turn NOT LIKE '%,' || c.x || '/' || c.y || ',%' AND -- 現ラウンドの壁に接続不可
                                     (c.x, c.y) IN ((r.x + 2, r.y), (r.x - 2, r.y), (r.x, r.y + 2), (r.x, r.y - 2)) -- 現在位置からの上下左右
                               UNION ALL
                               -- 新規の未接続の壁の選択(flg=1)
                               SELECT c.x, c.y, c.x, c.y, 1, 0
                               FROM   cells c
                               WHERE  c.c = 'X' AND
                                      r.path NOT LIKE '%,' || c.x || '/' || c.y || ',%'  -- 既存の壁は選択から除外
                               )
                        ) s
         WHERE s.rn = 1
         )
         CYCLE n SET cycle TO 1 DEFAULT 0,
pcells -- カンマ区切り壁リストの展開
    AS (SELECT REGEXP_SUBSTR(path,  ',(\d+)/(\d+)', 1, LEVEL, '', 1) x,
               REGEXP_SUBSTR(path,  ',(\d+)/(\d+)', 1, LEVEL, '', 2) y,
               REGEXP_SUBSTR(path2, ',(\d+)/(\d+)', 1, LEVEL, '', 1) cx,
               REGEXP_SUBSTR(path2, ',(\d+)/(\d+)', 1, LEVEL, '', 2) cy
        FROM (SELECT path, path2
              FROM  (SELECT ROW_NUMBER() OVER (ORDER BY n DESC) rn, path, path2
                     FROM   mazewall
                     )
              WHERE rn = 1
        )
CONNECT BY LEVEL <= REGEXP_COUNT(path, ',') - 1
)
SELECT  LISTAGG (c) WITHIN GROUP (ORDER BY x) maze
FROM (SELECT c.x, c.y, NVL2(p.x, '#', c.c) c
      FROM   cells c, 
            (SELECT x, y FROM pcells UNION SELECT cx, cy FROM pcells) p
      WHERE  c.x = p.x (+) AND c.y = p.y (+)
      )
GROUP BY y
ORDER BY y;

MAZE
----------------------------------------------------------
###################################################
#           #             #               #   #   #
# # ##### # ### ### # ### # # ######### # # ##### #
# #   #   #   # #   # #   # #   #       # # #     #
# ####### ##### ### ##### # ##### ####### # ##### #
#       # #     # # #     # #   # #   # #   #     #
# ####### ##### # # ### ### ### ### # # ####### # #
# #         #   #     #       #     # # # #   # # #
### # ##### ### ### ##### # ####### ### # ### # # #
#   # #       # # # #     #       #           # # #
### ######### ### # ####### ####### ##### ####### #
#       #   #     #     # # # #   # #             #
# ##### ### ##### ### ### ### # # # ### # ##### ###
#     #   #     #   #   #   #   #     # # # # #   #
# ### ##### # # ### # ##### # ### ######### # ### #
#   #     # # #   # #       #   # #           # # #
### # ####### ########### # ### ### ### ### # # # #
#   #       #           # #         #   # # # # # #
# ### # ### ### ####### # ##### ### # ### ### # # #
#   # #   #         #         #   # # #       #   #
###################################################

21 rows selected.

Elapsed: 00:00:02.82
```

#### PostgreSQL版

```sql:壁伸ばし法(PostgreSQL)
WITH RECURSIVE
cells (n, x, y, c)
    AS (SELECT 1, 1, 1, '#'
        UNION all
        SELECT n + 1, MOD(n, size_x) + 1, CAST((n / size_x) + 1 AS INTEGER),
               CASE WHEN MOD(n, size_x) + 1 in (1, size_x) OR
                         (n / size_x)   + 1 in (1, size_y)
                         THEN '#'
                    WHEN MOD(MOD(n, size_x) + 1, 2) = 1 AND
                         MOD((n / size_x)   + 1, 2) = 1
                         THEN 'X'
                         ELSE ' '
               END
        FROM (SELECT 51 size_x, 21 size_y) msize, cells
        WHERE  n < size_x * size_y
        ),
mazewall (n, x, y, action, path, turn, path2, turn2)
     AS (SELECT 1, cast(NULL as integer), cast(NULL as integer), 1, 
                '{}'::text[], '{}'::text[], '{}'::text[], '{}'::text[]
         UNION ALL
         SELECT n + 1, s.x, s.y,
                s.wallhit,
                CASE WHEN s.wallhit = 0 THEN r.path
                                        ELSE r.path || r.turn
                END,
                CASE WHEN s.wallhit > 0 THEN NULL
                     WHEN s.flg     > 0 THEN ARRAY[CONCAT(s.x, '/', s.y)]
                                        ELSE r.turn || CONCAT(s.x, '/', s.y)
                END,
                CASE WHEN s.wallhit = 0 THEN r.path2 
                                        ELSE r.path2 || r.turn2 || CONCAT(s.cx, '/', s.cy)
                END,
                CASE WHEN s.flg     = 0 THEN r.turn2 || CONCAT(s.cx, '/', s.cy)
                                        ELSE NULL
                END
         FROM   mazewall r
                CROSS JOIN LATERAL (
                         SELECT i.x, i.y, i.x - (i.x - i.px)/2 cx, i.y - (i.y - i.py)/2 cy,
                                flg, wallhit,
                                ROW_NUMBER() OVER (ORDER BY flg, RANDOM()) rn
                         FROM (
                               SELECT c.x, c.y, r.x px, r.y py, 0 flg,
                                      CASE WHEN c.c = '#' OR
                                                CONCAT(c.x, '/', c.y) = ANY(r.path)
                                           THEN 1 ELSE 0
                                      END wallhit
                               FROM   cells c
                               WHERE  r.action = 0 AND
                                      NOT CONCAT(c.x, '/', c.y) = ANY(r.turn) AND
                                     (c.x, c.y) IN ((r.x + 2, r.y), (r.x - 2, r.y),
                                                    (r.x, r.y + 2), (r.x, r.y - 2))
                               UNION ALL
                               SELECT c.x, c.y, c.x, c.y, 1, 0
                               FROM   cells c
                               WHERE  c.c = 'X' AND
                                      NOT CONCAT(c.x, '/', c.y) = ANY(r.path)
                               ) i
                        ) s
         WHERE s.rn = 1
         ),
pcells
    AS (SELECT CAST(SUBSTRING(p  FROM  '^\d+')      AS INTEGER) x,
               CAST(REGEXP_REPLACE(p,  '^\d+/', '') AS INTEGER) y,
               CAST(SUBSTRING(p2 FROM  '^\d+')      AS INTEGER) cx,
               CAST(REGEXP_REPLACE(p2, '^\d+/', '') AS INTEGER) cy
        FROM   (SELECT UNNEST(path) p, UNNEST(path2) p2
                FROM (SELECT path, path2
                      FROM  (SELECT ROW_NUMBER() OVER (ORDER BY n DESC) rn, path, path2
                             FROM   mazewall
                             ) a
                      WHERE rn = 1
                      ) b
                ) c
        )
SELECT  STRING_AGG (c, '' ORDER BY x) maze
FROM   (SELECT c.x, c.y, CASE WHEN p.x IS NOT NULL THEN '#' ELSE c.c END c
        FROM   cells c
               LEFT JOIN (SELECT  x,  y FROM pcells 
                          UNION
                          SELECT cx, cy FROM pcells) p
                      ON  c.x = p.x AND c.y = p.y
       ) g
GROUP BY y
ORDER BY y;
```

## おわりに

ラテラル句や副問合せの多段飛び参照という比較的新しい機能を再帰内で使用すると再帰のルールである「再帰自身を再帰内のサブクエリから呼んではいけない」（PostgreSQLにはない？）や「再帰自身が再帰内で二度以上現れてはいけない」等によるクエリの行動制限をかなり回避できるようになります。またラテラル句の中でUNIONを使用して処理を意図的に分岐させることも可能であり再帰クエリが利用できる幅が大きく広がりました。これまでPL/SQLやアプリでないと制御できなかった動きがクエリ一発で済む可能性もありますね。ということで、これからもいろいろ試して行きたいと思います。

以上です。