再帰with句10 数独を解く

SQLパズル

数独を解きます。

SQL

with recursive work(val) as(
values('080701050'
    || '002040900'
    || '930000074'
    || '800104006'
    || '006000100'
    || '700903008'
    || '240000015'
    || '007050300'
    || '050807040')),
rec(LV,Val) as(
select 1,Val from work
union all
select LV+1,
case when substr(Val,LV,1) = '0'
     then overLay(Val placing cnt::text from LV)
     else Val end
from rec a,generate_series(1,9) as b(cnt)
where LV <= 81
  and (substr(Val,LV,1) = '0' or b.cnt=1)
  and (substr(Val,LV,1) !='0'
    or (position(cnt::text in substr(Val,(LV-1)/9*9+1 ,9)) = 0 /*横チェック*/
    and position(cnt::text in substr(Val,(LV-1)%9+1   ,1)) = 0 /*縦チェック*/
    and position(cnt::text in substr(Val,(LV-1)%9+1+ 9,1)) = 0
    and position(cnt::text in substr(Val,(LV-1)%9+1+18,1)) = 0
    and position(cnt::text in substr(Val,(LV-1)%9+1+27,1)) = 0
    and position(cnt::text in substr(Val,(LV-1)%9+1+36,1)) = 0
    and position(cnt::text in substr(Val,(LV-1)%9+1+45,1)) = 0
    and position(cnt::text in substr(Val,(LV-1)%9+1+54,1)) = 0
    and position(cnt::text in substr(Val,(LV-1)%9+1+63,1)) = 0
    and position(cnt::text in substr(Val,(LV-1)%9+1+72,1)) = 0
    and position(cnt::text in substr(Val,((LV-1)%9)/3*3+1+9*(((LV-1)/9)/3*3)   ,3)) = 0 /*正方形チェック*/
    and position(cnt::text in substr(Val,((LV-1)%9)/3*3+1+9*(((LV-1)/9)/3*3)+ 9,3)) = 0
    and position(cnt::text in substr(Val,((LV-1)%9)/3*3+1+9*(((LV-1)/9)/3*3)+18,3)) = 0)))
select * from rec
where LV = 82;

解説

手続き型言語を使ったほうが楽そうですねぇ
C#のサンプル集 8-8 数独
Javaアルゴリズムパズル 3-7 数独
DB2 SQLパズル 再帰with句10 数独を解く

実行結果
684791253572348961931526874823174596496285137715963428248639715167452389359817642

■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
なお条件式は、こう記述してもいいです。

必要条件の論理積を記述していき、必要十分条件にしたのが上記で
必要十分条件を一度に記述したのが下記です。
必要条件の論理積を記述していく方法のほうが条件式がシンプルになることがあります。

where LV <= 81
  and ((substr(Val,LV,1) != '0' and b.cnt=1)
    or (substr(Val,LV,1) = '0'
     and (position(cnt::text in substr(Val,(LV-1)/9*9+1 ,9)) = 0 /*横チェック*/
      and position(cnt::text in substr(Val,(LV-1)%9+1   ,1)) = 0 /*縦チェック*/
      and position(cnt::text in substr(Val,(LV-1)%9+1+ 9,1)) = 0
      and position(cnt::text in substr(Val,(LV-1)%9+1+18,1)) = 0
      and position(cnt::text in substr(Val,(LV-1)%9+1+27,1)) = 0
      and position(cnt::text in substr(Val,(LV-1)%9+1+36,1)) = 0
      and position(cnt::text in substr(Val,(LV-1)%9+1+45,1)) = 0
      and position(cnt::text in substr(Val,(LV-1)%9+1+54,1)) = 0
      and position(cnt::text in substr(Val,(LV-1)%9+1+63,1)) = 0
      and position(cnt::text in substr(Val,(LV-1)%9+1+72,1)) = 0
      and position(cnt::text in substr(Val,((LV-1)%9)/3*3+1+9*(((LV-1)/9)/3*3)   ,3)) = 0 /*正方形チェック*/
      and position(cnt::text in substr(Val,((LV-1)%9)/3*3+1+9*(((LV-1)/9)/3*3)+ 9,3)) = 0
      and position(cnt::text in substr(Val,((LV-1)%9)/3*3+1+9*(((LV-1)/9)/3*3)+18,3)) = 0)))

---