y-kawazの日記 このページをアンテナに追加 RSSフィード Twitter

Google

2009-11-03

SQLで数独を解く

BeforeAfter
f:id:y-kawaz:20091104020144p:imagef:id:y-kawaz:20091104020143p:image

Oracle RDBMS 11gR2 - Solving a Sudoku using Recursive Subquery Factoringという海外の記事を見つけて、これはスゲーwwと思ったんだ。


で、Oracleなんかよりも自分が慣れ親しんだ PostgreSQL でも、8.4で再帰SQLが出来るようになったからやってみたい!ってことでやってみた。

Oracleスペシャルな関数とかが無かったりしたのでちょこちょこと直したけど基本は同じです*1

こうして上手く動くと感動するわー。

WITH RECURSIVE x(s, ind) AS (
  SELECT
    sud,
    position(' ' in sud) AS ind
  FROM
    (SELECT '53  7    6  195    98    6 8   6   34  8 3  17   2   6 6    28    419  5    8  79'::text AS sud) t1
  UNION ALL
  SELECT
    substring( s, 1, ind - 1 ) || z || substring( s, ind + 1 ) AS sud,
    position(' ' in substring(s, ind + 1)) + ind
  FROM
    x,
    (
      SELECT '1' as z UNION ALL SELECT '2' UNION ALL SELECT '3'
      UNION ALL SELECT '4' UNION ALL SELECT '5' UNION ALL SELECT '6'
      UNION ALL SELECT '7' UNION ALL SELECT '8' UNION ALL SELECT '9'
    ) z
  WHERE ind > 0
    AND NOT EXISTS (
      SELECT NULL
      FROM
        (
          SELECT 1 as lp UNION ALL SELECT 2 UNION ALL SELECT 3
          UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6
          UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9
        ) t2
      WHERE z = substring( s, ( trunc( ( ind - 1 ) / 9 ) * 9 + lp)::int, 1 )
         OR z = substring( s, ( ( ind - 1 ) % 9 - 8 + lp * 9 )::int, 1 )
         OR z = substring( s, ( ( trunc( ( ind - 1 ) / 3 )::int % 3 ) * 3 + trunc( ( ind - 1 ) / 27 ) * 27 + lp + trunc( ( lp - 1 ) / 3 ) * 6)::int, 1)
    )
)
SELECT s
FROM x
WHERE position(' ' in s) = 0;

↑コレの実行結果が↓コレです。外側のwhereを外した再帰SQLの内容を見てみるとどんな仕組みで正解を探しているのかが何となく分かるかも。

 s                                         
-----------------------------------------------------------------------------------
 534678912672195348198342567859761423426853791713924856961537284287419635345286179
(1 row)

↓ちなみにEXPLAINの結果はこんな感じでした。

 CTE Scan on x  (cost=319.18..319.46 rows=1 width=32)
   Filter: ("position"(s, ' '::text) = 0)
   CTE x
     ->  Recursive Union  (cost=0.00..319.18 rows=11 width=68)
           ->  Subquery Scan t1  (cost=0.00..0.02 rows=1 width=32)
                 ->  Result  (cost=0.00..0.01 rows=1 width=0)
           ->  Nested Loop Anti Join  (cost=0.19..31.89 rows=1 width=68)
                 Join Filter: ((('1'::text) = "substring"(x.s, (((trunc((((x.ind - 1) / 9))::double precision) * 9::double precision) + ((1))::double precision))::integer, 1)) OR (('1'::text) = "substring"(x.s, ((((x.ind - 1) % 9) - 8) + ((1) * 9)), 1
)) OR (('1'::text) = "substring"(x.s, ((((((((trunc((((x.ind - 1) / 3))::double precision))::integer % 3) * 3))::double precision + (trunc((((x.ind - 1) / 27))::double precision) * 27::double precision)) + ((1))::double precision) + (trunc(((((1) - 1)
 / 3))::double precision) * 6::double precision)))::integer, 1)))
                 ->  Nested Loop  (cost=0.00..1.31 rows=27 width=68)
                       ->  WorkTable Scan on x  (cost=0.00..0.22 rows=3 width=36)
                             Filter: (ind > 0)
                       ->  Append  (cost=0.00..0.18 rows=9 width=0)
                             ->  Subquery Scan "*SELECT* 1"  (cost=0.00..0.02 rows=1 width=0)
                                   ->  Result  (cost=0.00..0.01 rows=1 width=0)
                             ->  Subquery Scan "*SELECT* 2"  (cost=0.00..0.02 rows=1 width=0)
                                   ->  Result  (cost=0.00..0.01 rows=1 width=0)
                             ->  Subquery Scan "*SELECT* 3"  (cost=0.00..0.02 rows=1 width=0)
                                   ->  Result  (cost=0.00..0.01 rows=1 width=0)
                             ->  Subquery Scan "*SELECT* 4"  (cost=0.00..0.02 rows=1 width=0)
                                   ->  Result  (cost=0.00..0.01 rows=1 width=0)
                             ->  Subquery Scan "*SELECT* 5"  (cost=0.00..0.02 rows=1 width=0)
                                   ->  Result  (cost=0.00..0.01 rows=1 width=0)
                             ->  Subquery Scan "*SELECT* 6"  (cost=0.00..0.02 rows=1 width=0)
                                   ->  Result  (cost=0.00..0.01 rows=1 width=0)
                             ->  Subquery Scan "*SELECT* 7"  (cost=0.00..0.02 rows=1 width=0)
                                   ->  Result  (cost=0.00..0.01 rows=1 width=0)
                             ->  Subquery Scan "*SELECT* 8"  (cost=0.00..0.02 rows=1 width=0)
                                   ->  Result  (cost=0.00..0.01 rows=1 width=0)
                             ->  Subquery Scan "*SELECT* 9"  (cost=0.00..0.02 rows=1 width=0)
                                   ->  Result  (cost=0.00..0.01 rows=1 width=0)
                 ->  Materialize  (cost=0.19..0.28 rows=9 width=4)
                       ->  Append  (cost=0.00..0.18 rows=9 width=4)
                             ->  Result  (cost=0.00..0.01 rows=1 width=0)
                             ->  Result  (cost=0.00..0.01 rows=1 width=0)
                             ->  Result  (cost=0.00..0.01 rows=1 width=0)
                             ->  Result  (cost=0.00..0.01 rows=1 width=0)
                             ->  Result  (cost=0.00..0.01 rows=1 width=0)
                             ->  Result  (cost=0.00..0.01 rows=1 width=0)
                             ->  Result  (cost=0.00..0.01 rows=1 width=0)
                             ->  Result  (cost=0.00..0.01 rows=1 width=0)
                             ->  Result  (cost=0.00..0.01 rows=1 width=0)
(41 rows)

*1:キャストとかはもう型が合わないとか怒られる度に適当に付けたモノでかなりやっつけですが(^^;

bleis-tiftbleis-tift 2009/11/04 22:43 はじめまして!再帰 CTE 楽しいですよね。
よかったらどう書く?org(http://ja.doukaku.org/lang/sql/) やブログのエントリ (http://d.hatena.ne.jp/bleis-tift/20090613/1244869567 とか http://d.hatena.ne.jp/bleis-tift/20090612/1244736068) とかどうぞ。
どう書く?org の SQL の未解決問題の中には、再帰 CTE で簡単に解けるやつも残っているので、時間があったら是非挑戦してみるといいかもです。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証