SQLクエリひとつで、数独の問題をつくろう！

## はじめに

単一SQLクエリで、答えが一意に定まる数独（ナンプレ）の問題をゼロからランダムで作ります。

さて、問題を作るためにはまず元となるランダムな数値表が必要だろうということで、前回数独の数値表をつくるクエリを作成しました。ここでは、そのクエリを利用してルールに則った数独の問題を作成していきます。対象としているSQLは、**Oracle(12c以降)、MySQL(8.0.14以降)、PostgreSQL(9.3以降)**ですが、それ以外でもRECURSIVEとLATERALをサポートしていればなんとかなるとおもいます。



> [単一SQLクエリで数独の数値表をランダムに作る](https://qiita.com/tlokweng/items/bdf8b3fa752f4a7c15b1)



## 数独問題のルール

大前提として数独の問題として成立させるためのルールはひとつ。

* 答えが一意に定まること

です。

まぁ他にも空欄セルを対角線対称とするような独自ルールもあるようですが、細かいルールはここでは採用しません。SQLなので勘弁してください。

ともかく、このルールに従うと数値表からランダムに数値を抜いて空欄セルを作る方法をとることはできなくなります。全体として答えが一つとなるように常に調整しながら数値を抜いて空欄セルを作っていく必要があるのです。



## 空欄セルの選択

では、どのセルの数値を抜けばいいのかという話になりますが、実は数値表を作成した時点でその一覧が手に入っています。それは前回作成した３番めのクエリであるハイブリッド型の再帰部分で保持している分岐候補リストです。

> クエリはここです。[ハイブリッド型](https://qiita.com/tlokweng/items/bdf8b3fa752f4a7c15b1#%E3%83%8F%E3%82%A4%E3%83%96%E3%83%AA%E3%83%83%E3%83%89%E5%9E%8B)

```
,,,,,,,,,,,,8,,,3,9,2,,,,2,97,,3,49,27,,,37,,,1,,,2,,8,,8,7,8,26,461,24,,,5,51,25,631,35612,1645,38274,,3,73,,9,19,,4,24,,1,14,1,61,163,246,9642,28649,,5,59,659,9564,58496,594268,2498567,59438627,
```

これは各セルにおいて配置可能であった数値をカンマ区切りでリスト化したものですが、ここに数値がないセルというのは、すでに配置した数値が唯一配置可能だったわけです。言い換えれば、これらのセルの数値をぬいて空欄にしても他のセルの影響で確実に数値が一意に決まるってことです。では実際どの程度の数のセルが空欄にできるのか数えてみると、幅はありますがだいたい30～40ほどなので全体の三分の一以上です。一般的な数独問題としては十分だと思います。

まずは対象となるセルの数値をぬいて「.」に置き換えるために前回のクエリの最後の表示部分を以下に書き換えます。

```sql
,
quiz (lvl, stk, diag) AS (
SELECT 81, stk, diag FROM recur WHERE lvl = 81
UNION ALL
SELECT lvl - 1,
       REGEXP_REPLACE(stk, '^\d*,', ''),
       CASE WHEN REGEXP_SUBSTR(stk, '^\d*,') = ','
            THEN SUBSTR(diag, 1, lvl - 1) || '.' || SUBSTR(diag, lvl + 1)
            ELSE DIAG
       END
FROM   quiz
WHERE  lvl > 0
)
SELECT diag diagram FROM quiz WHERE lvl in (81, 0);
```

出力は以下となりますが、ぱっと見て分かる通り空欄セルが右下に集中しています。数値表の作成時に数値を左上から埋めていったので当然ですね。これでも一応数独問題として機能しないこともないですが、さすがにパズルとして見栄えが悪いのである程度空欄セルがばらけるようにクエリを改良していきます。

```
DIAGRAM
---------
297463518
345128697
168759243
982645731
634871952
571932864
416297385
823516479
759384126

29746351.
34512869.
16.75.24.
9826457..
634871.5.
5..9..8..
41629....
8.3..6...
.........
```



## 空欄セル位置の改良

さて、どうやって空欄セルをバラけさせればよいのかですね。まぁ空欄セルが右下に集中した原因が、数値表作成時のセルを埋める順番にあるのだから普通に考えてセルを埋める順番をバラけさせればいいということになります。なのでセルをランダムに処理する様にクエリを変更してみましょう。

まず最初に処理するセルの順番を決め対応表をつくっておきます。これは数値表作成中に行き詰まった時分岐可能セルまでロールバックしたたり、最後にリストとセルを対応するために必要となります。81個のセル番号をランダムにならべて文字列として保持しておき、対応セル番号をSUBSTRでとりだします。以下は一例として処理順を完全にランダムに並べたものです。

```sql
cellmap(m) as (
    SELECT LISTAGG(TO_CHAR(n, 'FM00')) WITHIN GROUP (ORDER BY DBMS_RANDOM.VALUE)
    FROM  (SELECT LEVEL n FROM DUAL CONNECT BY LEVEL <= 81)
),
```

しかしここで注意して置かなければならないのは、セルの処理順変更は数値表作成のパフォーマンスに直結するということです。処理順を完全ランダムにしてしまうと、分岐候補数がなかなか減らないため処理に非常に時間がかかります。はっきり言って終わりません。かといって多くのセル順を固定してしまうと同じような数独問題になってしまうのでいい方法とはいえません。

要はパフォーマンスとバラけ度のバランスになってしまうんですが、今回採用したのは「セルは行ごとに処理するが行内のセルの順番はランダム、また処理する行の順番もランダム」とする方法です。これだとパフォーマンス問題はほぼ改善されます。ただ一行目と二行目に処理したセルはそれぞれ9個のうち8個はかならず埋まってしまうという難点があります。といっても空欄位置が固定でなく十分バラけて見えるので、まぁ妥協します。なんかいい方法があればお知らせください。

（余談ですが、オラクルはパフォーマンスを向上させるためコスト次第ではCTEをインラインに置換することがあります。しかしランダムデータを取得するCTEがインライン置換されるとアクセスするたびに異なるデータが取得されてしまう状況が生まれてしまいます。これを避けるためにMATERIALIZEヒントを入れています。基本的に同じCTEがクエリ中に二度以上あらわれればそのCTEがインライン置換されることはまずありませんが、念の為）

```sql
WITH
singles(n, s) AS (
    SELECT LEVEL, TO_CHAR(LEVEL) FROM DUAL CONNECT BY LEVEL <= 9
),
cellmap(m) as (
    SELECT --+ MATERIALIZE
           LISTAGG(s) WITHIN GROUP (ORDER BY DBMS_RANDOM.VALUE)
    FROM  (SELECT y.n, 
                LISTAGG(TO_CHAR(x.n + (y.n - 1) * 9, 'FM00'))
                        WITHIN GROUP (ORDER BY DBMS_RANDOM.VALUE) s
           FROM  singles x, singles y
           GROUP BY y.n)
),
```

さて、これまではlvlを用いてセル情報を文字列の左端から取得していましたが、ここからはcellmapを噛まして対象となるセル位置を取得しなければなりません。lvlからセル位置への変換は単純に``TO_NUMBER(SUBSTR(cellmap.m, (lvl + n) * 2 - 1, 2))``となります。しかし、すべてをそのまま置き換えると冗長になるので、LATERAL内で計算してエイリアス登録しておきます。これでlvlの代わりにptrでセル位置が取得できます。

```sql
           LATERAL (SELECT TO_NUMBER(SUBSTR(m, (lvl + 1)*2 - 1, 2)) ptr,
                           TO_NUMBER(SUBSTR(m, (lvl + 0)*2 - 1, 2)) ptr1,
                           TO_NUMBER(SUBSTR(m, (lvl - 1)*2 - 1, 2)) ptr2
                     FROM  cellmap
           ),
```



## 数独問題を作るクエリ

最後に、上記の新たなCTEとセル位置変換サブクエリを結合して完成です。これで30～40個ほどの空欄セルがあり答えが一意に決まる数独問題がランダムに作られます。ちなみに空欄にするセルの数を少なくすれば、問題の難易度が下がります。

##### Oracle版 (12c以降)

```sql
WITH
singles(n, s) AS (
    SELECT LEVEL, TO_CHAR(LEVEL) FROM DUAL CONNECT BY LEVEL <= 9
),
cellmap(m) as (
    SELECT --+ MATERIALIZE
           LISTAGG(s) WITHIN GROUP (ORDER BY DBMS_RANDOM.VALUE)
    FROM  (SELECT y.n, 
                  LISTAGG(TO_CHAR(x.n + (y.n - 1) * 9, 'FM00'))
                          WITHIN GROUP (ORDER BY DBMS_RANDOM.VALUE) s
           FROM   singles x, singles y
           GROUP BY y.n)
),
recur (lvl, stk, c, diag) AS (
    SELECT 0, CAST('' AS VARCHAR(500)), '*', RPAD('-', 81, '-') FROM DUAL
    UNION ALL
    SELECT CASE WHEN c    IS NULL THEN lvl - 1
                WHEN nums IS NULL THEN lvl
                                  ELSE lvl + 1
           END,
           CASE WHEN nums IS NULL THEN SUBSTR(stk,  2)
                                  ELSE SUBSTR(nums, 2) || ',' || stk
           END,
           CASE WHEN nums IS NULL THEN NULLIF(SUBSTR(stk,  1, 1), ',')
                                  ELSE SUBSTR(nums, 1, 1)
           END,
           CASE WHEN c    IS NULL THEN SUBSTR(diag, 1, ptr2 - 1)                 ||
                                       NVL(NULLIF(SUBSTR(stk,  1, 1), ','), '*') ||
                                       SUBSTR(diag,    ptr2 + 1)
                WHEN nums IS NULL THEN SUBSTR(diag, 1, ptr1 - 1)                 ||
                                       NVL(NULLIF(SUBSTR(stk,  1, 1), ','), '*') ||
                                       SUBSTR(diag,    ptr1 + 1)
                                  ELSE SUBSTR(diag, 1, ptr  - 1) ||
                                       SUBSTR(nums, 1,   1)     ||
                                       SUBSTR(diag,    ptr  + 1)
           END
    FROM   recur r,
           LATERAL (SELECT TO_NUMBER(SUBSTR(m, (lvl + 1)*2 - 1, 2)) ptr,
                           TO_NUMBER(SUBSTR(m, (lvl + 0)*2 - 1, 2)) ptr1,
                           TO_NUMBER(SUBSTR(m, (lvl - 1)*2 - 1, 2)) ptr2
                     FROM  cellmap
           ),
           LATERAL (
           SELECT nums
           FROM   (SELECT LISTAGG(s) WITHIN GROUP (ORDER BY DBMS_RANDOM.VALUE) OVER () nums,
                   ROW_NUMBER() OVER (ORDER BY null) rn
                   FROM  (SELECT s FROM singles UNION ALL SELECT NULL FROM DUAL)
                   WHERE  s IS NULL
                          OR
                          (c IS NOT NULL and
                              (SUBSTR(diag, ptr, 1) = s
                               OR
                               SUBSTR(diag, ptr, 1) in ('-', '*') AND
                               INSTR(
                               -- row
                               SUBSTR(diag, TRUNC((ptr - 1)/9)*9 + 1, 9) ||
                               -- col
                               SUBSTR(diag, MOD((ptr - 1), 9) +  1, 1) ||
                               SUBSTR(diag, MOD((ptr - 1), 9) + 10, 1) ||
                               SUBSTR(diag, MOD((ptr - 1), 9) + 19, 1) ||
                               SUBSTR(diag, MOD((ptr - 1), 9) + 28, 1) ||
                               SUBSTR(diag, MOD((ptr - 1), 9) + 37, 1) ||
                               SUBSTR(diag, MOD((ptr - 1), 9) + 46, 1) ||
                               SUBSTR(diag, MOD((ptr - 1), 9) + 55, 1) ||
                               SUBSTR(diag, MOD((ptr - 1), 9) + 64, 1) ||
                               SUBSTR(diag, MOD((ptr - 1), 9) + 73, 1) ||
                               -- box
                               SUBSTR(diag, TRUNC((ptr - 1)/27)*27 + MOD(TRUNC((ptr - 1)/3),3)*3 +  1, 3) ||
                               SUBSTR(diag, TRUNC((ptr - 1)/27)*27 + MOD(TRUNC((ptr - 1)/3),3)*3 + 10, 3) ||
                               SUBSTR(diag, TRUNC((ptr - 1)/27)*27 + MOD(TRUNC((ptr - 1)/3),3)*3 + 19, 3),
                               s) = 0)
                          )
                  )
            WHERE rn = 1
           )
    WHERE  lvl < 81
)
CYCLE diag, stk, c SET cycle TO 1 DEFAULT 0
,
puzzle (lvl, stk, diag) AS (
SELECT 81, stk, diag FROM recur WHERE lvl = 81
UNION ALL
SELECT lvl - 1,
       REGEXP_REPLACE(stk, '^\d*,', ''),
       CASE WHEN REGEXP_SUBSTR(stk, '^\d*,') = ','
            THEN SUBSTR(diag, 1, ptr - 1) || '.' || SUBSTR(diag, ptr + 1)
            ELSE diag
       END
FROM   puzzle,
       LATERAL (SELECT TO_NUMBER(SUBSTR(m, lvl*2 - 1, 2)) ptr FROM cellmap)
WHERE  lvl > 0
)
SELECT s "Sudoku Quiz" FROM (
SELECT n,
       SUBSTR(diag, 9*(n - 1) + 1, 3) || '|' ||
       SUBSTR(diag, 9*(n - 1) + 4, 3) || '|' ||
       SUBSTR(diag, 9*(n - 1) + 7, 3) s
FROM  (SELECT * FROM puzzle WHERE lvl = 0), singles
UNION ALL SELECT 3.5, '---+---+---' FROM DUAL
UNION ALL SELECT 6.5, '---+---+---' FROM DUAL)
ORDER BY n;
```

どうでしょう？

それなりにまともっぽい問題ができていますね！ :-)。

```
Sudoku Quiz
-----------
8..|...|...
415|73.|289
.9.|.52|1.6
---+---+---
786|4.9|532
..3|..8|..1
15.|.27|6.8
---+---+---
5.9|.81|.27
...|...|...
67.|2..|.1.
```

パフォーマンスについてですが、多くの場合1秒以内に終了します。しかし、ランダムな処理順に依存しているのでたまに時間がかかることがあります。長いときは一分ほどかかることがあるので、気長にまってやってください。



##### MySQL版 (8.0.14以降)

```sql
SET SESSION CTE_MAX_RECURSION_DEPTH = 500000;

WITH RECURSIVE
singles(n, s) AS (
SELECT 1, '1' UNION ALL SELECT N + 1, CAST(n + 1 AS CHAR(1)) FROM singles WHERE n < 9
),
cellmap(m) as (
    SELECT GROUP_CONCAT(s ORDER BY RAND() SEPARATOR '')
    FROM  (SELECT y.n, 
                  GROUP_CONCAT(SUBSTR(CONCAT('0', CONVERT(x.n + (y.n - 1) * 9, CHAR)), -2, 2)
                               ORDER BY RAND() SEPARATOR '') s
           FROM   singles x, singles y
           GROUP BY y.n) g
),
recur (cnt, lvl, stk, c, diag) AS (
    SELECT 0, 0, CAST(',' AS CHAR(500)), '*', RPAD('-', 81, '-')
    UNION ALL
    SELECT cnt + 1,
           CASE WHEN c    IS NULL THEN lvl - 1
                WHEN nums IS NULL THEN lvl
                                  ELSE lvl + 1
           END,
           CASE WHEN nums IS NULL THEN SUBSTR(stk,  2)
                                  ELSE CONCAT(SUBSTR(nums, 2), ',', stk)
           END,
           CASE WHEN nums IS NULL THEN NULLIF(SUBSTR(stk,  1, 1), ',')
                                  ELSE SUBSTR(nums, 1, 1)
           END,
           CASE WHEN c    IS NULL THEN CONCAT(SUBSTR(diag, 1, ptr2 - 1),
                                              IFNULL(NULLIF(SUBSTR(stk,  1, 1), ','), '*'),
                                              SUBSTR(diag,    ptr2 + 1))
                WHEN nums IS NULL THEN CONCAT(SUBSTR(diag, 1, ptr1 - 1),
                                              IFNULL(NULLIF(SUBSTR(stk,  1, 1), ','), '*'),
                                              SUBSTR(diag,    ptr1 + 1))
                                  ELSE CONCAT(SUBSTR(diag, 1, ptr  - 1),
                                              SUBSTR(nums, 1, 1),
                                              SUBSTR(diag,    ptr  + 1))
           END
    FROM   recur r,
           LATERAL (SELECT CONVERT(SUBSTR(m, (lvl + 1)*2 - 1, 2), UNSIGNED) ptr,
                           CONVERT(SUBSTR(m, (lvl + 0)*2 - 1, 2), UNSIGNED) ptr1,
                           CONVERT(SUBSTR(m, (lvl - 1)*2 - 1, 2), UNSIGNED) ptr2
                     FROM  cellmap
           ) cnv,
           LATERAL(SELECT GROUP_CONCAT(s ORDER BY RAND() SEPARATOR '') nums
                   FROM  (SELECT s FROM singles UNION ALL SELECT NULL) i
                   WHERE  s IS NULL
                          OR
                          (c IS NOT NULL AND
                              (SUBSTR(diag, ptr, 1) = s
                               OR
                               SUBSTR(diag, ptr, 1) in ('-', '*') AND
                               INSTR(CONCAT(
                               -- row
                               SUBSTR(diag, TRUNCATE((ptr - 1)/9,0)*9 + 1, 9),
                               -- col
                               SUBSTR(diag, MOD(ptr - 1, 9) +  1, 1),
                               SUBSTR(diag, MOD(ptr - 1, 9) + 10, 1),
                               SUBSTR(diag, MOD(ptr - 1, 9) + 19, 1),
                               SUBSTR(diag, MOD(ptr - 1, 9) + 28, 1),
                               SUBSTR(diag, MOD(ptr - 1, 9) + 37, 1),
                               SUBSTR(diag, MOD(ptr - 1, 9) + 46, 1),
                               SUBSTR(diag, MOD(ptr - 1, 9) + 55, 1),
                               SUBSTR(diag, MOD(ptr - 1, 9) + 64, 1),
                               SUBSTR(diag, MOD(ptr - 1, 9) + 73, 1),
                               -- box
                               SUBSTR(diag, TRUNCATE((ptr - 1)/27,0)*27 + MOD(TRUNCATE((ptr - 1)/3,0),3)*3 +  1, 3),
                               SUBSTR(diag, TRUNCATE((ptr - 1)/27,0)*27 + MOD(TRUNCATE((ptr - 1)/3,0),3)*3 + 10, 3),
                               SUBSTR(diag, TRUNCATE((ptr - 1)/27,0)*27 + MOD(TRUNCATE((ptr - 1)/3,0),3)*3 + 19, 3))
                               , s) = 0)
                          )
           ) l
    WHERE  lvl < 81
),
puzzle (lvl, stk, diag) AS (
SELECT 81, stk, diag FROM recur WHERE lvl = 81
UNION ALL
SELECT lvl - 1,
       REGEXP_REPLACE(stk, '^[0-9]*,', ''),
       CASE WHEN REGEXP_SUBSTR(stk, '^[0-9]*,') = ','
            THEN CONCAT(SUBSTR(diag, 1, ptr - 1), '.', SUBSTR(diag, ptr + 1))
            ELSE diag
       END
FROM   puzzle,
       LATERAL (SELECT CONVERT(SUBSTR(m, lvl*2 - 1, 2), UNSIGNED) ptr FROM cellmap) l
WHERE  lvl > 0
)
SELECT s "Sudoku Quiz" FROM (
SELECT n, 
       CONCAT(SUBSTR(diag, 9*(n - 1) + 1, 3), '|', 
              SUBSTR(diag, 9*(n - 1) + 4, 3), '|',
              SUBSTR(diag, 9*(n - 1) + 7, 3)) s
FROM   (SELECT * FROM puzzle WHERE lvl = 0) r, singles
UNION ALL SELECT 3.5, '---+---+---'
UNION ALL SELECT 6.5, '---+---+---') t
ORDER BY n;
```

```
+-------------+
| Sudoku Quiz |
+-------------+
| ...|...|... |
| 451|6..|872 |
| .2.|.4.|.91 |
| ---+---+--- |
| 16.|42.|.39 |
| .49|358|.1. |
| 73.|961|428 |
| ---+---+--- |
| 6.4|5.9|287 |
| 873|21.|.6. |
| ...|...|1.. |
+-------------+
```



##### PostgreSQL(9.3以降?)

旧バージョンが手元にないので確認できませんが、LATERALがサポートされたのが9.3らしいのでたぶんそれ以降で動くはず。PostgreSQL 11.0で確認しました。

```sql
WITH RECURSIVE
singles(n, s) AS (
    SELECT n, TO_CHAR(n, 'FM0') FROM GENERATE_SERIES(1, 9) n
),
cellmap(m) as (
    SELECT STRING_AGG(s, '' ORDER BY RANDOM())
    FROM  (SELECT y.n, 
                  STRING_AGG(TO_CHAR(x.n + (y.n - 1) * 9, 'FM00'), '' ORDER BY RANDOM()) s
           FROM   singles x, singles y
           GROUP BY y.n) g
),
recur (cnt, lvl, stk, c, diag) AS (
    SELECT 0, 0, ','::TEXT, '*', RPAD('-', 81, '-')
    UNION ALL
    SELECT cnt + 1,
           CASE WHEN NULLIF(c,    '') IS NULL THEN lvl - 1
                WHEN NULLIF(nums, '') IS NULL THEN lvl
                                              ELSE lvl + 1
           END,
           CASE WHEN NULLIF(nums, '') IS NULL THEN SUBSTR(stk,  2)
                                              ELSE CONCAT(SUBSTR(nums, 2), ',', stk)
           END,
           CASE WHEN NULLIF(nums, '') IS NULL THEN NULLIF(SUBSTR(stk,  1, 1), ',')
                                              ELSE SUBSTR(nums, 1, 1)
           END,
           CASE WHEN NULLIF(c,    '') IS NULL THEN CONCAT(SUBSTR(diag, 1, ptr2 - 1),
                                                          COALESCE(NULLIF(SUBSTR(stk,  1, 1), ','), '*'),
                                                          SUBSTR(diag,    ptr2 + 1))
                WHEN NULLIF(nums, '') IS NULL THEN CONCAT(SUBSTR(diag, 1, ptr1 - 1),
                                                          COALESCE(NULLIF(SUBSTR(stk,  1, 1), ','), '*'),
                                                          SUBSTR(diag,    ptr1 + 1))
                                              ELSE CONCAT(SUBSTR(diag, 1, ptr  - 1),
                                                          SUBSTR(nums, 1, 1),
                                                          SUBSTR(diag,    ptr  + 1))
           END
    FROM   recur r,
           LATERAL (SELECT SUBSTR(m, (lvl + 1)*2 - 1, 2)::INT ptr,
                           SUBSTR(m, (lvl + 0)*2 - 1, 2)::INT ptr1,
                           SUBSTR(m, (lvl - 1)*2 - 1, 2)::INT ptr2
                     FROM  cellmap
           ) cnv,
           LATERAL(SELECT STRING_AGG(s, '' ORDER BY RANDOM()) nums
                   FROM  (SELECT s FROM singles UNION ALL SELECT NULL) i
                   WHERE  s IS NULL
                          OR
                          (c IS NOT NULL AND
                              (SUBSTR(diag, ptr, 1) = s
                               OR
                               SUBSTR(diag, ptr, 1) in ('-', '*') AND
                               STRPOS(CONCAT(
                               -- row
                               SUBSTR(diag, (TRUNC((ptr - 1)/9)*9 + 1)::INT, 9),
                               -- col
                               SUBSTR(diag, MOD(ptr - 1, 9) +  1, 1),
                               SUBSTR(diag, MOD(ptr - 1, 9) + 10, 1),
                               SUBSTR(diag, MOD(ptr - 1, 9) + 19, 1),
                               SUBSTR(diag, MOD(ptr - 1, 9) + 28, 1),
                               SUBSTR(diag, MOD(ptr - 1, 9) + 37, 1),
                               SUBSTR(diag, MOD(ptr - 1, 9) + 46, 1),
                               SUBSTR(diag, MOD(ptr - 1, 9) + 55, 1),
                               SUBSTR(diag, MOD(ptr - 1, 9) + 64, 1),
                               SUBSTR(diag, MOD(ptr - 1, 9) + 73, 1),
                               -- box
                               SUBSTR(diag, (TRUNC((ptr - 1)/27)*27 + MOD(TRUNC((ptr - 1)/3)::INT,3)*3 +  1)::INT, 3),
                               SUBSTR(diag, (TRUNC((ptr - 1)/27)*27 + MOD(TRUNC((ptr - 1)/3)::INT,3)*3 + 10)::INT, 3),
                               SUBSTR(diag, (TRUNC((ptr - 1)/27)*27 + MOD(TRUNC((ptr - 1)/3)::INT,3)*3 + 19)::INT, 3)),
                               s) = 0)
                          )
           ) l
    WHERE  lvl < 81
),
puzzle (lvl, stk, diag) AS (
SELECT 81, stk, diag FROM recur WHERE lvl = 81
UNION ALL
SELECT lvl - 1,
       REGEXP_REPLACE(stk, '^[0-9]*,', ''),
       CASE WHEN SUBSTRING(stk from '^[0-9]*,') = ','
            THEN CONCAT(SUBSTR(diag, 1, ptr - 1), '.', SUBSTR(diag, ptr + 1))
            ELSE diag
       END
FROM   puzzle,
       LATERAL (SELECT SUBSTR(m, lvl*2 - 1, 2)::INT ptr FROM cellmap) l
WHERE  lvl > 0
)
SELECT s "Sudoku Quiz" FROM (
SELECT n, 
       CONCAT(SUBSTR(diag, 9*(n - 1) + 1, 3), '|', 
              SUBSTR(diag, 9*(n - 1) + 4, 3), '|',
              SUBSTR(diag, 9*(n - 1) + 7, 3)) s
FROM   (SELECT * FROM puzzle WHERE lvl = 0) r, singles
UNION ALL SELECT 3.5, '---+---+---'
UNION ALL SELECT 6.5, '---+---+---') t
ORDER BY n;
```

```
 Sudoku Quiz
-------------
 .94|623|187
 1..|4.7|5..
 .38|519|462
 ---+---+---
 ...|...|718
 ...|...|9..
 9.1|8.2|..4
 ---+---+---
 .59|.38|6..
 623|17.|895
 ...|...|...
```



## おわりに

再帰クエリで数独を解くことができるけれど、問題も作れるだろうか？という素朴な疑問からクエリに取り組んでみましたが、なんとか完成することができました。結果、なんだかんだいって再帰クエリって思ったより多くのことができるんだなぁって改めて実感できた次第です。

一応これでお終いですが、今回のクエリはパフォーマンスも空欄のバラけ度もすべては数値表作成時のセル処理順に依存しているのでここを弄くればさらに改良できる気がします。

以上です。