SQLで数独を解く

Before	After

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

で、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:キャストとかはもう型が合わないとか怒られる度に適当に付けたモノでかなりやっつけですが(^^;