ジグソー数独(Sudoku Jigsaw)をSQLで解く

こちらも書いたので参考まで。

https://qiita.com/gAuk/items/593ddcf52c904e03d762

## 準備

PostgreSQLをインストール

```shell
brew install postgresql
```

サーバを起動

```shell
pg_ctl -D /opt/homebrew/var/postgres start
```

データベース作成

```shell
createdb sudoku
```

データベース確認

```shell
psql -l
```

### 参考ページ

下のソースsudoku_jig.sqlはこれを参考にさせて頂きました。

https://www.forcia.com/blog/001176.html

テーブル、プロシージャ、関数の定義。

```sql:sudoku_jig.sql
-- 番号1~9 TABLE
DROP TABLE IF EXISTS allnum;
CREATE TABLE allnum AS
SELECT generate_series(1, 9) AS num
;

-- 問題 TABLE
DROP TABLE IF EXISTS sudoku_q;
CREATE TABLE sudoku_q (
  id        integer PRIMARY KEY,
  question  text,
  colors    text
);

-- マス目 TABLE
DROP TABLE IF EXISTS grid;
CREATE TABLE grid AS
SELECT
  (i - 1) * 9 + j AS indexof,
  i,
  j
FROM
  allnum n1(i),
  allnum n2(j)
;

-- 問題追加 PROCEDURE
CREATE OR REPLACE PROCEDURE add_to_sudoku_q(i integer, q text, c text)
LANGUAGE SQL
AS $$
UPDATE sudoku_q SET question=q, colors=c WHERE id=i;
INSERT INTO sudoku_q (id, question, colors)
       SELECT i, q, c
       WHERE NOT EXISTS (SELECT 1 FROM sudoku_q WHERE id=i);
$$;

-- 数独を解く FUNCTION
CREATE OR REPLACE FUNCTION sudoku_jig(text, colors text)
RETURNS text LANGUAGE sql IMMUTABLE AS $$
WITH RECURSIVE _sudoku AS (
  -- 初期値
  SELECT $1 kekka
  -- 再帰with句で追加されていく行
  UNION ALL(
    -- 1. 数字の候補が複数存在する場合に並列で処理する
    --    行程3で数字を埋めたマス目に数字の候補が複数あったとき、再帰with句で複数行が一度に追加されることがあります。
    --    この後の処理で並列して計算を行うため、番号をふります。
    WITH latest AS (
      SELECT
        kekka
        ,(ROW_NUMBER() OVER())::int parallelid
      FROM _sudoku
    )
    -- 2. 数字の候補が最も少ないマス目(indexof) を計算
    --    事前に用意したgridテーブルを使用します。
    --    最新の計算結果とマス目の縦・横・色の情報を結合します。
    ,gridnum AS (
      SELECT
        latest.parallelid -- 並列化番号
        ,indexof, i, j -- gridテーブルの情報
        ,substr(latest.kekka, indexof, 1) AS num -- そこに存在する数字(空欄は空文字)
        ,substr(colors, indexof, 1) AS color -- そのマスの色
      FROM latest, grid
    )
    -- マス目ごとに縦・横・色で既に使用されている数を配列に集約します。
    ,used AS (
      SELECT
        gridnums.parallelid -- 並列化番号
        ,gridnums.indexof -- マス目
        ,array_agg(DISTINCT usednums.num :: int) usednumarray -- 使用済数配列を作成
      FROM
        gridnum usednums -- 上で計算した結果1(使用済数配列の作成に使用)
        ,gridnum gridnums -- 上で計算した結果2(基準)
      WHERE
        usednums.num <> ' ' -- 空欄じゃないマス
      AND
        gridnums.num = ' ' -- 空欄のマス
      AND
        usednums.parallelid = gridnums.parallelid -- 並列化番号
      AND(
          usednums.i = gridnums.i -- 横が同じ
        OR
          usednums.j = gridnums.j -- 縦が同じ
        OR
          usednums.color = gridnums.color -- 色が同じ
      )
      GROUP BY
        gridnums.parallelid -- 並列化番号
        ,gridnums.indexof -- マス目ごとに集約
    )
    -- usedで計算した usednumarray を元に、最も数字の候補が少ないマスを計算します。
    -- ここでは順番をふり、後のSELECT句で insertorder = 1 に絞り込みます。
    ,insertnum AS (
      SELECT
        parallelid -- 並列化番号
        ,indexof -- マス目
        ,usednumarray -- 使用済数の配列
        -- 使用済数の配列が長い順(数字の候補が少ない順)に番号をふる
        ,DENSE_RANK() OVER(
          PARTITION BY used.parallelid
          ORDER BY ARRAY_LENGTH(used.usednumarray, 1) DESC, indexof
        ) AS insertorder
      FROM used
    )
    -- 3. 1の計算結果を元に、最も数字の候補が少ないマス目を埋める
    --    再帰with句でUNIONされる本体部分のSQLです。
    --    overlay関数を使用し、数字を埋めています。
    --    候補の数字が複数ある場合、複数行が作られます。
    SELECT
      -- {latest.kekka}を、{insertnum.indexof}文字目から{1}文字分{allnum.num::text}に置き換える
      overlay(latest.kekka placing allnum.num::text FROM insertnum.indexof FOR 1) AS kekka
    FROM
      latest -- 最新の計算結果
      ,allnum -- 1-9までの数字
      ,insertnum -- 1で計算した結果
    WHERE
      latest.parallelid = insertnum.parallelid -- 並列化への対応
    AND
      insertnum.insertorder = 1 -- 最も数字の候補が少ないマス目の情報のみを使用
    AND
      allnum.num <> ALL(insertnum.usednumarray) -- 縦・横・色で使われていない数字のみを使用
  )
)
SELECT kekka
FROM _sudoku
WHERE strpos(kekka, ' ') = 0;
$$ ;
```

上のテーブル、プロシージャ、関数をデータベースに登録。

```shell
psql -f sudoku_jig.sql -d sudoku
```

## 問題を書く

今回は２問同時に解きます。$9 \times 9 = 81$マスを81文字の文字列で表します。
問題を下の様に書いて

```sql:sudoku_jig_prob.sql
CALL add_to_sudoku_q(1, ' 9  54 81   6  4  9   2    5  46    32   9 6    1   576       41 3    2 7   4  93', 'abbbbbcccaddbbbcccaddbcccffadddeffffadeeefgggadeeefgggahhhefgggahhheiiiiahhhiiiii');
CALL add_to_sudoku_q(2, '3       4  2 6 1   1 9 8 2   5   6   2     1   9   8   8 3 4 6   4 1 9  5       7', 'aaabcccccaaabbbcccaddddbbbcaadeeeebbddddeffffggeeeefiihgggffffihhhgggiiihhhhhgiii');
```

実行すると

```shell
psql -f sudoku_jig_prob.sql -d sudoku
```

データベースに問題が追加されたはずなので、確認する。

```shell
psql -c"select * from sudoku_q;" -d sudoku
```

結果。ちゃんと追加されています。

```shell_session
 id |                                     question                                      |                                      colors
----+-----------------------------------------------------------------------------------+-----------------------------------------------------------------------------------
  1 |  9  54 81   6  4  9   2    5  46    32   9 6    1   576       41 3    2 7   4  93 | abbbbbcccaddbbbcccaddbcccffadddeffffadeeefgggadeeefgggahhhefgggahhheiiiiahhhiiiii
  2 | 3       4  2 6 1   1 9 8 2   5   6   2     1   9   8   8 3 4 6   4 1 9  5       7 | aaabcccccaaabbbcccaddddbbbcaadeeeebbddddeffffggeeeefiihgggffffihhhgggiiihhhhhgiii
(2 rows)
```

## 問題を解く

下の様に解くクエリを実行します。

```shell
psql -c 'SELECT id, sudoku_jig(question, colors) FROM sudoku_q ORDER BY id;' -d sudoku
```

こんな結果が出ます。これも$9 \times 9 = 81$マスを一列81文字の文字列で表しています。
だいぶ見づらいので、これを見やすく整形するのは後述します。

```shell_session
 id |                                    sudoku_jig                                     
----+-----------------------------------------------------------------------------------
  1 | 297354681835612479971823546589467312324579168462138957618795234143986725756241893
  2 | 358196274492567138613978425175842693826453719249731856987324561734615982561289347
(2 rows)
```

## 問題と解答を読みやすくする

問題も上のsudoku_jig_prob.sqlの様に書くのは読みづらくて書きづらいですね。
問題は下の様に書いてgawkで変換する事にします。

```:jignum.prob
start 1
numbers
_ 9 _ _ 5 4 _ 8 1
_ _ _ 6 _ _ 4 _ _
9 _ _ _ 2 _ _ _ _
5 _ _ 4 6 _ _ _ _
3 2 _ _ _ 9 _ 6 _
_ _ _ 1 _ _ _ 5 7
6 _ _ _ _ _ _ _ 4
1 _ 3 _ _ _ _ 2 _
7 _ _ _ 4 _ _ 9 3
colors
a b b b b b c c c
a d d b b b c c c
a d d b c c c f f
a d d d e f f f f
a d e e e f g g g
a d e e e f g g g
a h h h e f g g g
a h h h e i i i i
a h h h i i i i i
end

start 2
numbers
3 _ _ _ _ _ _ _ 4
_ _ 2 _ 6 _ 1 _ _
_ 1 _ 9 _ 8 _ 2 _
_ _ 5 _ _ _ 6 _ _
_ 2 _ _ _ _ _ 1 _
_ _ 9 _ _ _ 8 _ _
_ 8 _ 3 _ 4 _ 6 _
_ _ 4 _ 1 _ 9 _ _
5 _ _ _ _ _ _ _ 7
colors
a a a b c c c c c
a a a b b b c c c
a d d d d b b b c
a a d e e e e b b
d d d d e f f f f
g g e e e e f i i
h g g g f f f f i
h h h g g g i i i
h h h h h g i i i
end
```

gawkをインストールしておく。

```shell
brew install gawk
```

問題をSQL形式に変換するgawkプログラム

```awk:sudoku_prob_to_sql.awk
#!/usr/bin/env gawk -f

BEGIN {
  start = 0;
  color = 0;
  row = 0;
  qid = 0;
  num_str = "";
  color_str = "";
}

/^start [0-9]+/ {
  printf "CALL add_to_sudoku_q(%d, '", $2;
  start = 0; color = 0; num_str = ""; color_str = "";
}
/^end/ {
  if (length(num_str) != length(color_str)) { print "error2" > "/dev/stderr" }
  printf num_str "', '" color_str "');\n"
}

/^numbers/ {start = NR; color = 0;}
/^colors/ {start = NR; color = 1;}

/^[1-9_a-i] /{
  if (0 < start && start < NR && NR <= start + 9) {
    if (NF != 9) {printf "s=%s,NF=%d,列数は9にすること!\n", $0, NF > "/dev/stderr"}
    row = NR - start;
    for (col = 1; col <= 9; col++ ) {
      x = $(col);
      if (color) {
        if (x !~ /[a-i]/) {printf "x=%d,ブロック文字はa~iにすること!\n", x > "/dev/stderr"}
      }else{
        if (x !~ /[_1-9]/) {printf "x=%d,数字は1~9,不明数は_にすること!\n", x > "/dev/stderr"}
      }
      if (!color && x ~ /[1-9_]/) {
        # 数字の方
        y = x ~ /_/ ? " " : x;
        num_str = num_str y;
      }else if (color && x ~ /[a-i]/) {
        # 色定義の方
        color_str = color_str x;
      }else{
        print "error1" > "/dev/stderr";
      }
    }
  }else{
    start = 0;
  }
}

END {
}
```

出力を見やすく整形するgawkプログラム

```awk:sudoku_out.awk
#!/usr/bin/env gawk -f

BEGIN {
  str = "";
  str2 = "";
}

/^ *[0-9]+/ {
  printf "id = %d\n", $1;
  str = $3;
  for (i = 1; i <= 9; i++) {
    match(str, /^([1-9]{9})([1-9]*)/, arr);
    str2 = arr[1];
    for (j = 1; j <= 9; j++) {
      delim = j == 9 ? "\n" : " ";
      match(str2, /^([1-9])([1-9]*)/, arr2);
      printf "%s%s", arr2[1], delim;
      str2 = arr2[2];
    }
    str = arr[2];
  }
  print "\n"
}

END {
}
```

実行パーミッションを追加

```shell
chmod +x sudoku_prob_to_sql.awk
chmod +x sudoku_out.awk
```

下の様に実行

```shell:(1)
cat jignum.prob | ./sudoku_prob_to_sql.awk \
| gxargs -d'\n' -I{} psql -q -c {} -d sudoku \
&& psql -c 'SELECT id, sudoku_jig(question, colors) FROM sudoku_q ORDER BY id;' -d sudoku \
| ./sudoku_out.awk
```

結果

```shell_session
id = 1
2 9 7 3 5 4 6 8 1
8 3 5 6 1 2 4 7 9
9 7 1 8 2 3 5 4 6
5 8 9 4 6 7 3 1 2
3 2 4 5 7 9 1 6 8
4 6 2 1 3 8 9 5 7
6 1 8 7 9 5 2 3 4
1 4 3 9 8 6 7 2 5
7 5 6 2 4 1 8 9 3


id = 2
3 5 8 1 9 6 2 7 4
4 9 2 5 6 7 1 3 8
6 1 3 9 7 8 4 2 5
1 7 5 8 4 2 6 9 3
8 2 6 4 5 3 7 1 9
2 4 9 7 3 1 8 5 6
9 8 7 3 2 4 5 6 1
7 3 4 6 1 5 9 8 2
5 6 1 2 8 9 3 4 7
```

因みに上のコマンド(1)で使ったgxargsは予め下の様にインストールしておく。

```shell
brew install findutils
```

macの標準のxargsを使えば良い様に思われるかもしれないが、これには`-d`オプションが無いため、シングルクォート「'」が消えてしまう問題に対処できない。