はじめに
SQLクエリで数独／ナンプレの数値表(マトリックス)をランダムに作ります。ここでいう数値表は、すべてのセルで数値の埋まった答えの表です。こういうやつですね。
SQLはOracleを使用して話をすすめていきますが、最後にMySQL版も記載しています。
クエリの考察
再帰クエリを使えば一見簡単そうに思えますが、SQLの再帰にはいろいろ制約や制限が多く一筋縄ではいきません。一番大きな制約は分岐した枝から他の枝や再帰全体に影響を与えることができないってとこです。つまり一度初期値で再帰を始めたら最後までやり遂げなければならないわけです。一説によると数独のパターンは6x10^21以上ってことなので、普通に再帰したら計算終わらないですよね。
従って考えられる戦略としては以下の３つ。
| 方法 | 内容 |
|---|---|
| 単純ループ型 | １セルに配置可能な数値をひとつづつをランダムに割り当てて進み、進行不能となったらすべてをすててやり直す |
| 初期値再帰型 | ランダムに作成した適当な初期値を与えて空白セルを減らしたのち残りを再帰探索する。 |
| ハイブリッド型 | 再帰分岐をせず分岐候補を保持しながら進み、進行不可となったらロールバックして分岐可能な位置に戻る。 |
それぞれの一長一短ありそうなので各方法でクエリを作りパフォーマンスを考察してみたいと思います。
単純ループ型
再帰クエリを使用しますが、再帰分岐はしません。分岐候補から一つだけランダムに選び進行し、進行不可となったらこれまでの結果を捨てて最初からやりなおします。最後まで到達したら終了です。
再帰分岐しない単純ループの利点は、進行中のある時点でクエリを終了させると再帰クエリ全体が終了することですね。まぁ一本道なので。ここでは81個のセルがすべて埋まった時点で再帰を終了させています。
また、LATERALの部分で数独のルールをチェックしています。ここで行、列、ボックスを確認してすでに配置されている数値を除外するわけですが、候補がない場合もループを続けなければならないため候補にNULLを混入させています。これにより行き詰まった場合にNULLが取得され、再帰のSELECTリスト部分において進行する場合と結果を捨ててやり直す場合の分岐ができます。
Oracle版 (12c以降)
WITH
singles(n, s) AS (
SELECT LEVEL, TO_CHAR(LEVEL) FROM DUAL CONNECT BY LEVEL <= 9
),
recur (cnt, rpt, lvl, diag) AS (
SELECT 0, 1, 0, RPAD('-', 81, '-') FROM DUAL
UNION ALL
SELECT cnt + 1,
DECODE(num, NULL, rpt + 1, rpt),
DECODE(num, NULL, 0, lvl + 1),
DECODE(num, NULL, RPAD('-', 81, '-'), REGEXP_REPLACE(diag, '-', num, 1, 1))
FROM recur r,
LATERAL(
SELECT num
FROM (SELECT num, ROW_NUMBER() OVER (ORDER BY v desc) rn
FROM (SELECT singles.s num, DBMS_RANDOM.VALUE + 1 v
FROM singles
WHERE INSTR(
-- row
SUBSTR(diag, TRUNC(lvl/9)*9 + 1, 9) ||
-- col
SUBSTR(diag, MOD(lvl, 9) + 1, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 10, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 19, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 28, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 37, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 46, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 55, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 64, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 73, 1) ||
-- box
SUBSTR(diag, TRUNC(lvl/27)*27 + MOD(TRUNC(lvl/3),3)*3 + 1, 3) ||
SUBSTR(diag, TRUNC(lvl/27)*27 + MOD(TRUNC(lvl/3),3)*3 + 10, 3) ||
SUBSTR(diag, TRUNC(lvl/27)*27 + MOD(TRUNC(lvl/3),3)*3 + 19, 3),
s) = 0
UNION ALL
SELECT NULL, 0 FROM DUAL) -- rollback
)
WHERE rn = 1
)
WHERE lvl < 81 and rpt > 0
)
SELECT s sudoku FROM (
SELECT n, REGEXP_REPLACE(SUBSTR(diag, 9 * (n - 1) + 1, 9), '(\d{3})(\d{3})(\d{3})', '\1|\2|\3') s
FROM (SELECT * FROM recur WHERE lvl = 81), singles
UNION ALL SELECT 3.5, '---+---+---' FROM DUAL
UNION ALL SELECT 6.5, '---+---+---' FROM DUAL)
ORDER BY n;
SUDOKU
-----------
854|793|612
629|518|734
137|642|598
---+---+---
215|967|483
946|385|271
783|421|965
---+---+---
492|836|157
371|259|846
568|174|329
Elapsed: 00:00:02.60
クエリのパフォーマンスですが、各ターンで開始して最後まで到達できるかは完全に運に左右されます。つまりやり直しの回数次第となります。運が良ければ0.5秒、運が悪ければ15秒と大きな幅があります。まぁあまりいい方法ではないようですね。
初期値再帰型
次に再帰分岐を試してみます。前述の通りすべてを分岐させることは不可能です。60該パターンとか計算がおわりません。なので、初期配置としてランダムに選択した固定数値を先においておきます。初期配置の数値が多いほど再帰する回数が減ってパフォーマンスが向上しますが、多くしすぎると数独ルールに適合しない答えのない初期配置を作ってしまう可能性が高まります。要はどのくらいでバランスをとるかですね。
まずは、斜めに3ブロックの初期配置を作成します（下図１，５，９）。なぜこの３ブロックかというと、これらは互いに他のブロックセルの影響を受けないので１～９の数値を完全にランダムに配置できるからです。３ブロックだけだとまだまだ再帰探索に時間がかかってしまうので、さらに反対側対角線の２ブロック（下図３と７）を追加します。しかしこの２ブロックを確定してしまうと答えのない初期配置になる可能性が非常に高まります。
解決方法として、右上のブロックだけを確定して開始するか、右上と左下のブロックの組み合わせをいくつか作ってそれをすべて再帰探索するかです。後者のほうが計算量を調整して幾分早く結果を取得できるため、ここでは後者のブロックの組み合わせを採用します。
Oracle版 (11g以降)
WITH
singles(n, s) AS (
SELECT LEVEL, TO_CHAR(LEVEL) FROM DUAL CONNECT BY LEVEL <= 9
),
first_blks(b1, b5, b9) AS (
SELECT LISTAGG(s) WITHIN GROUP (ORDER BY (DBMS_RANDOM.VALUE * 1)),
LISTAGG(s) WITHIN GROUP (ORDER BY (DBMS_RANDOM.VALUE * 2)),
LISTAGG(s) WITHIN GROUP (ORDER BY (DBMS_RANDOM.VALUE * 4))
FROM singles
),
corners(grp, cnt, srow, scol, str) as (
SELECT * FROM (SELECT 3, 0, b1, b9, '' FROM first_blks UNION
SELECT 7, 0, b9, b1, '' FROM first_blks)
UNION ALL
SELECT grp, cnt + 1, srow, scol, str || singles.s
FROM corners, singles
WHERE cnt < 9 AND
NVL(INSTR(str, singles.s), 0) = 0 AND
INSTR(SUBSTR(srow, TRUNC(cnt/3)*3 + 1, 3), singles.s) = 0 AND
INSTR(SUBSTR(scol, MOD(cnt, 3) + 1, 1), singles.s) = 0 AND
INSTR(SUBSTR(scol, MOD(cnt, 3) + 4, 1), singles.s) = 0 AND
INSTR(SUBSTR(scol, MOD(cnt, 3) + 7, 1), singles.s) = 0
),
targets (s) AS (
SELECT
SUBSTR(b1, 1, 3) || '---' || SUBSTR(b3, 1, 3) ||
SUBSTR(b1, 4, 3) || '---' || SUBSTR(b3, 4, 3) ||
SUBSTR(b1, 7, 3) || '---' || SUBSTR(b3, 7, 3) ||
'---' || substr(b5, 1, 3) || '---' ||
'---' || substr(b5, 4, 3) || '---' ||
'---' || substr(b5, 7, 3) || '---' ||
SUBSTR(b7, 1, 3) || '---' || SUBSTR(b9, 1, 3) ||
SUBSTR(b7, 4, 3) || '---' || SUBSTR(b9, 4, 3) ||
SUBSTR(b7, 7, 3) || '---' || SUBSTR(b9, 7, 3) s
FROM first_blks,
(SELECT str b3 FROM (
SELECT str, ROW_NUMBER() OVER (ORDER BY DBMS_RANDOM.VALUE) rn
FROM corners WHERE cnt = 9 and grp = 3)
WHERE rn <= 5),
(SELECT str b7 FROM (
SELECT str, ROW_NUMBER() OVER (ORDER BY DBMS_RANDOM.VALUE) rn
FROM corners WHERE cnt = 9 and grp = 7)
WHERE rn <= 5)
),
recur (lvl, diag) AS (
SELECT 0, s FROM targets
UNION ALL
SELECT lvl + 1,
REGEXP_REPLACE(diag, '.', singles.s, lvl + 1, 1)
FROM recur, singles
WHERE lvl < 81 AND
(SUBSTR(diag, lvl + 1, 1) = singles.s
OR
(SUBSTR(diag, lvl + 1, 1) = '-' AND
INSTR(-- row
SUBSTR(diag, TRUNC(lvl/9)*9 + 1, 9) ||
-- col
SUBSTR(diag, MOD(lvl, 9) + 1, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 10, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 19, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 28, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 37, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 46, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 55, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 64, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 73, 1) ||
-- box
SUBSTR(diag, TRUNC(lvl/27)*27 + MOD(TRUNC(lvl/3),3)*3 + 1, 3) ||
SUBSTR(diag, TRUNC(lvl/27)*27 + MOD(TRUNC(lvl/3),3)*3 + 10, 3) ||
SUBSTR(diag, TRUNC(lvl/27)*27 + MOD(TRUNC(lvl/3),3)*3 + 19, 3),
singles.s) = 0
))
)
SELECT s sudoku FROM (
SELECT n, REGEXP_REPLACE(substr(diag, 9*(n - 1)+1, 9), '(\d{3})(\d{3})(\d{3})', '\1|\2|\3') s
FROM (SELECT * FROM recur WHERE lvl = 81 and rownum = 1), singles
UNION ALL SELECT 3.5, '---+---+---' FROM DUAL
UNION ALL SELECT 6.5, '---+---+---' FROM DUAL)
ORDER BY n;
SUDOKU
-----------
593|268|174
768|431|529
241|975|368
---+---+---
815|642|793
926|713|485
437|589|216
---+---+---
652|397|841
179|854|632
384|126|957
Elapsed: 00:00:01.46
少しクエリが長くなってしまいましたが、ほぼ一秒前後長くても二秒程度で結果が取得できるようになりました。ただし、初期値によっては結果を取得できない可能性も完全にゼロではないので注意が必要です。
ハイブリッド型
最後にハイブリッド型です。なにがハイブリッドかというと、再帰分岐はせず単純ループさせながらクエリの内容で枝分かれを実現して、最初に到達した数値表でクエリを終了する、というところですね。
繰り返しになりますが、再帰クエリには分岐の機能がありながらなぜそれを使わずに自分で分岐させるのかというと、それはもう「他に分岐があっても最初の答えを得た時点でクエリを終了させたいから」につきます。自分の知ってる限りSQLの再帰はこれができません。まぁ当然といえば当然ですけどね。
ということで、再帰クエリのパラメータとして分岐可能リストを保持し、探索が行き詰まった場合に他の候補があるセルまでロールバックして、リストから次の候補を取得して探索を再開します。以下のクエリでは、stkに分岐可能リストをカンマ区切りリストで保持しています。Cにはターゲットのセルで確定した数値が入っていますが、これがNULLである場合セルを一つ戻して候補リストから次の候補を取得します。
Oracle版 (12c以降)
WITH
singles(n, s) AS (
SELECT LEVEL, TO_CHAR(LEVEL) FROM DUAL CONNECT BY LEVEL <= 9
),
recur (cnt, lvl, stk, c, diag) AS (
SELECT 0, 0, CAST(',' AS VARCHAR(500)), '*', RPAD('-', 81, '-') FROM DUAL
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 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, (lvl - 1) - 1) ||
NVL(NULLIF(SUBSTR(stk, 1, 1), ','), '*') ||
SUBSTR(diag, (lvl - 1) + 1)
WHEN nums IS NULL THEN SUBSTR(diag, 1, (lvl + 0) - 1) ||
NVL(NULLIF(SUBSTR(stk, 1, 1), ','), '*') ||
SUBSTR(diag, (lvl + 0) + 1)
ELSE SUBSTR(diag, 1, (lvl + 1) - 1) ||
SUBSTR(nums, 1, 1) ||
SUBSTR(diag, (lvl + 1) + 1)
END
FROM recur r,
LATERAL(
SELECT nums
FROM (-- aggregate function is not permitted, use analytic function instead
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, lvl + 1, 1) = s
OR
SUBSTR(diag, lvl + 1, 1) in ('-', '*') AND
INSTR(
-- row
SUBSTR(diag, TRUNC(lvl/9)*9 + 1, 9) ||
-- col
SUBSTR(diag, MOD(lvl, 9) + 1, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 10, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 19, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 28, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 37, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 46, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 55, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 64, 1) ||
SUBSTR(diag, MOD(lvl, 9) + 73, 1) ||
-- box
SUBSTR(diag, TRUNC(lvl/27)*27 + MOD(TRUNC(lvl/3),3)*3 + 1, 3) ||
SUBSTR(diag, TRUNC(lvl/27)*27 + MOD(TRUNC(lvl/3),3)*3 + 10, 3) ||
SUBSTR(diag, TRUNC(lvl/27)*27 + MOD(TRUNC(lvl/3),3)*3 + 19, 3)
, s) = 0)
)
) WHERE rn = 1
)
WHERE lvl < 81
)
CYCLE diag, stk, c SET cycle TO 1 DEFAULT 0
SELECT s sudoku FROM (
SELECT n, REGEXP_REPLACE(substr(diag, 9*(n - 1)+1, 9), '(\d{3})(\d{3})(\d{3})', '\1|\2|\3') s
FROM (SELECT * FROM recur WHERE lvl = 81), singles
UNION ALL SELECT 3.5, '---+---+---' FROM DUAL
UNION ALL SELECT 6.5, '---+---+---' FROM DUAL)
ORDER BY n;
SUDOKU
-----------
567|813|249
389|724|651
124|659|783
---+---+---
631|245|897
798|361|425
452|987|136
---+---+---
273|198|564
815|436|972
946|572|318
Elapsed: 00:00:00.08
なんとなんと、結果を得るのにかかる時間は0.1秒以下です。パフォーマンスはある程度運に左右されますが、完全に無視できる範囲内です。しかも結果が取得できないリスクもありません。他の２つのクエリを完全に凌駕してしまいました。
MySQL版 (8.0.14以降)
LATERALを使用しているので、8.0.14以降が対象となります。
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
),
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, lvl - 2),
IFNULL(NULLIF(SUBSTR(stk, 1, 1), ','), '*'),
SUBSTR(diag, lvl))
WHEN nums IS NULL THEN CONCAT(SUBSTR(diag, 1, lvl - 1),
IFNULL(NULLIF(SUBSTR(stk, 1, 1), ','), '*'),
SUBSTR(diag, lvl + 1))
ELSE CONCAT(SUBSTR(diag, 1, lvl),
SUBSTR(nums, 1, 1),
SUBSTR(diag, lvl + 2))
END
FROM recur r,
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, lvl + 1, 1) = s
OR
SUBSTR(diag, lvl + 1, 1) in ('-', '*') AND
INSTR(CONCAT(
-- row
SUBSTR(diag, TRUNCATE(lvl/9,0)*9 + 1, 9),
-- col
SUBSTR(diag, MOD(lvl, 9) + 1, 1),
SUBSTR(diag, MOD(lvl, 9) + 10, 1),
SUBSTR(diag, MOD(lvl, 9) + 19, 1),
SUBSTR(diag, MOD(lvl, 9) + 28, 1),
SUBSTR(diag, MOD(lvl, 9) + 37, 1),
SUBSTR(diag, MOD(lvl, 9) + 46, 1),
SUBSTR(diag, MOD(lvl, 9) + 55, 1),
SUBSTR(diag, MOD(lvl, 9) + 64, 1),
SUBSTR(diag, MOD(lvl, 9) + 73, 1),
-- box
SUBSTR(diag, TRUNCATE(lvl/27,0)*27 + MOD(TRUNCATE(lvl/3,0),3)*3 + 1, 3),
SUBSTR(diag, TRUNCATE(lvl/27,0)*27 + MOD(TRUNCATE(lvl/3,0),3)*3 + 10, 3),
SUBSTR(diag, TRUNCATE(lvl/27,0)*27 + MOD(TRUNCATE(lvl/3,0),3)*3 + 19, 3)),
s) = 0)
)
) l
WHERE lvl < 81
)
SELECT s sudoku 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 recur WHERE lvl = 81) r, singles
UNION ALL SELECT 3.5, '---+---+---'
UNION ALL SELECT 6.5, '---+---+---') t
ORDER BY n;
+-------------+
| sudoku |
+-------------+
| 327|169|584 |
| 481|753|962 |
| 659|482|731 |
| ---+---+--- |
| 948|516|327 |
| 135|827|496 |
| 276|394|815 |
| ---+---+--- |
| 763|248|159 |
| 594|631|278 |
| 812|975|643 |
+-------------+
11 rows in set (0.035 sec)
おわりに
久しぶりに再帰クエリに取り組んでみましたが、いい練習になりました。再帰クエリに関していえば、クエリを強制終了できる機能があるといろいろできる幅が広がるんですが、まぁSQLには必要ないんでしょうね。たぶん。
実はこのクエリ、「SQLで数独の問題を作る」という目標において、問題を作るにはまず元になる数値表が必要だよなぁ、ってことで書いたものです。そんなわけで次回は、一意に定まる数独の問題を作成するクエリについて書く予定です。