LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@gAuk(Yamana)

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

Posted at

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

準備

PostgreSQLをインストール

brew install postgresql

サーバを起動

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

データベース作成

createdb sudoku

データベース確認

psql -l

参考ページ

下のソースsudoku_jig.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;
$$ ;

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

psql -f sudoku_jig.sql -d sudoku

問題を書く

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

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');

実行すると

psql -f sudoku_jig_prob.sql -d sudoku

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

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

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

 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)

問題を解く

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

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

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

 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をインストールしておく。

brew install gawk

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

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プログラム

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 {
}

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

chmod +x sudoku_prob_to_sql.awk
chmod +x sudoku_out.awk

下の様に実行

(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

結果

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は予め下の様にインストールしておく。

brew install findutils

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

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?