Oracleで数独を解く

# Oracleで数独を解く
Oracleで数独が解けるらしいが読んでも意味がわからなかったので細かく調べてみる。
以下は11g以上のoracleで実行可能です。

## 元記事
https://technology.amis.nl/2009/10/13/oracle-rdbms-11gr2-solving-a-sudoku-using-recursive-subquery-factoring/

## 問題
![250px-sudoku-by-l2g-20050714_svg.png](https://qiita-image-store.s3.amazonaws.com/0/44786/3fb119b9-7d78-1426-d661-88b2423eec1c.png)


この問題を左上から右方向に一行ずつ並べて空白は半角スペースといった感じで一つの文字列にして表現します
`'53  7    6  195    98    6 8   6   34  8 3  17   2   6 6    28    419  5    8  79' `

## 答え
```sql
with x( s, ind ) as
( select sud, instr( sud, ' ' )
  from ( select '53  7    6  195    98    6 8   6   34  8 3  17   2   6 6    28    419  5    8  79' sud from dual )
  union all
  select substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 )
       , instr( s, ' ', ind + 1 )
  from x
     , ( select to_char( rownum ) z
         from dual
         connect by rownum <= 9
       ) z
  where ind > 0
  and not exists ( select null
                   from ( select rownum lp
                          from dual
                          connect by rownum <= 9
                        )
                   where z = substr( s, trunc( ( ind - 1 ) / 9 ) * 9 + lp, 1 )
                   or    z = substr( s, mod( ind - 1, 9 ) - 8 + lp * 9, 1 )
                   or    z = substr( s, mod( trunc( ( ind - 1 ) / 3 ), 3 ) * 3
                                      + trunc( ( ind - 1 ) / 27 ) * 27 + lp
                                      + trunc( ( lp - 1 ) / 3 ) * 6
                                   , 1 )
                 )
)
select s
from x
where ind = 0
```

## 解説
何がなんやらよくわかりませんがまずwith句から説明を始めましょう
### 再帰WITH句
SQLで再帰書けるってだけでもちょっと驚きですが以下を引用して説明してみます。
http://www.oracle.com/technetwork/jp/articles/otnj-sql-image7-1525406-ja.html#a

簡単な再帰WITH句を例に出します。

```sql
WITH rec(STR) AS (
  SELECT CAST('A' AS VARCHAR(20))
  FROM dual
  UNION ALL
  SELECT CONCAT(STR,  'A')
  FROM rec
  WHERE LENGTH(STR) < 5)
SELECT STR
FROM rec;
```
まず`with rec(STR)`は
recはテーブル名 STRはカラム名です。

次にwith句の中を見て下さい。
UNION ALLで区切られた2つのSELECTクエリがありますが、
それぞれ前者を非再帰項。後者を再帰項と呼びます。
再帰with句は、最初に非再帰項のselectを実行して、
そのselect文の結果を使って再帰項のselectを実行して、
そのselect文の結果を使って再帰項のselectを実行して・・・・
結果が0件になるまで実行され続けます。

![0fd31a7a6b4f81631f6d5f1b776860c1.png](https://qiita-image-store.s3.amazonaws.com/0/44786/10b8b1c6-9f51-c39b-e077-4fb1fb9eb265.png)


この場合最初に非再帰項で'A'という一つのレコードが返されそれを再帰項に渡し、
長さが5を超えるまで'A'を結合してレコードを返してというのを繰り返します。

WITH句がなかなかすごいことがわかると思います。
数独も解ける気がしてきます。

## 再帰を使って数独を解く

それでは簡単なクエリから順番に肉付けして回答のクエリを組み上げていきます。

### 数独の解き方
先頭のスペースに1-9の数字を埋めたものを作り、それが数独のルールに合わなければ省く。
これを繰り返しスペースが0になればそれが答えとなります。

### 1-9の数字表を作る
```sql
SELECT rownum z
   FROM dual
   CONNECT BY rownum <= 9
```
CONNECT句が使われていますがこれも再起処理（階層問い合わせ）を行えるクエリです。
connect by句はその後に続く条件が満たされる限り行を生成していきます。
これにより9までの値を格納した表を作成することができました

### スペースを数字で埋める
再起クエリを作って2個のスペースを1か2で埋めるクエリを作ってみます。

```sql
WITH rec(s, ind) AS (
  SELECT sud, instr(sud, ' ')
  FROM (SELECT '[ ][ ]' sud FROM dual)
  UNION ALL
  SELECT
    (substr(s, 1, ind - 1) || z || substr(s, ind + 1)),
    instr(s, ' ', ind + 1)
  FROM rec, (
            SELECT to_char(rownum) z
            FROM dual
            CONNECT BY rownum <= 2
          ) z
  where ind > 0
)
SELECT s
FROM rec
```

![1eb2fa9c98505ab20aba2774d99f94f5.png](https://qiita-image-store.s3.amazonaws.com/0/44786/824a0572-520a-f68e-2523-ccdf37ceffa3.png)


先ほど作った数値表の条件を変更して2までの数値表にした上で等価結合し、
`(substr(s, 1, ind - 1) || z || substr(s, ind + 1)),`これでスペースの前後で区切って数値表の数値と置換しています。

これではスペースが残った物も計算結果に出ているので先ほどのクエリの最後に条件を追加して排除しましょう
`WHERE ind = 0;`

![cd46f12405488b344f772d0ff1533bed.png](https://qiita-image-store.s3.amazonaws.com/0/44786/97d33eab-1541-ee19-8ff4-19fd679daf46.png)

これで全ての空白マスを1-9で埋めることが出来るようになりました。

### 不正解の数独を排除する
数独のルールを復習します。
- 横に1-9が揃うこと
- 縦に1-9が揃うこと
- 左上から順に3*3で区切った格子のそれぞれの部屋に1-9までの数字が揃うこと
これを満たす数字でスペースを埋めていけばゴールに辿り着くことになります。

よってWITHの再帰項の部分は先のルールで埋める数字を選択し且つ**スペースがまだ残っている**場合、
結果を返していけば最後にはスペースを含まないルールに反しない文字列が出来上がり、再帰処理が終了します。

### ルールに反しない数字で埋める
先ほど1-9の数字で埋める方法がわかりましたがこれを「ルールに反しない数字」で埋めるように書き換えます。

まず横列を検証するルールを作ってみましょう。
先ほどまでに作ったクエリを少し修正して数独の一行目の最後だけ埋まってない文字列を与えてみます。

```sql
WITH rec(s, ind) AS (
  SELECT
    sud,
    instr(sud, ' ')
  FROM (SELECT '12345678 ' sud
        FROM dual)
  UNION ALL
  SELECT
    (substr(s, 1, ind - 1) || z || substr(s, ind + 1)),
    instr(s, ' ', ind + 1)
  FROM rec, (
              SELECT to_char(rownum) z
              FROM dual
              CONNECT BY rownum <= 9
            ) z_t
  WHERE ind > 0
)
SELECT s
FROM rec
WHERE ind = 0;
```
これをこのまま実行すると9列の結果がでますがこの内8個は横列の条件が満たせていません。
ではこれを排除するようにNOT EXISTSを使って横列に含まれている数字を除外してみましょう。

```sql
WITH rec(s, ind) AS (
  SELECT
    sud,
    instr(sud, ' ')
  FROM (SELECT '12345678 ' sud
        FROM dual)
  UNION ALL
  SELECT
    (substr(s, 1, ind - 1) || z || substr(s, ind + 1)),
    instr(s, ' ', ind + 1)
  FROM rec, (
              SELECT to_char(rownum) z
              FROM dual
              CONNECT BY rownum <= 9
            ) z_t
  WHERE ind > 0 AND NOT EXISTS(SELECT NULL
                               FROM (SELECT rownum lp
                                     FROM dual
                                     CONNECT BY rownum <= 9)
                               WHERE z = substr(s, lp, 1))
)
SELECT s
FROM rec
WHERE ind = 0;
```
NOT EXISTSの中にまたCONNECTが現れていますがこれもまた1-9の数字の表を作っています。
そして作った表をsubstrの第二引数に当てることでs(='123456789 ')から一文字ずつ取り出し
存在するものをNOT EXISTSでz_tテーブルから除外しています。

試しに複数の数字を抜いて'1 34 678 'などでも実行してみると条件を満たさない数値は除外されていることがわかります。

![ae82487f8f00d59648701883d46640d2.png](https://qiita-image-store.s3.amazonaws.com/0/44786/6d535bf0-e109-ce55-bb71-0655cebc8bfd.png)

あとは本来の数独は複数行あり、更に縦条件と格子条件があるのでそれをこのNOT EXISTS句に盛り込むと最初のクエリにたどり着けます。

## まとめ
SELECT文をちょろちょろ書いてWEBアプリ作ってるだけの人間なので、こんなことが出来たのは驚きでした。
SQL奥が深い・・・