ナップサック問題

再帰with句で組み合わせの列挙

再帰with句で、ナップサック問題を解いてみます。
最大で20kgまでの荷物を持てるとして、Valが最大になるIDの組み合わせを求めます。

create table nimotu(ID primary key,Val,Kg) as
select 1, 7,10 from dual union all
select 2, 2, 4 from dual union all
select 3, 9, 5 from dual union all
select 4, 4, 1 from dual union all
select 5, 9, 7 from dual union all
select 6, 7, 3 from dual union all
select 7, 4, 6 from dual union all
select 8, 5, 3 from dual;

with rec(ID,IDList,sumVal,SumKg) as(
select ID,to_char(ID),Val,Kg
  from nimotu
union all
select b.ID,a.IDList || ',' || to_char(b.ID),
a.sumVal+b.Val,a.SumKg+b.Kg
  from rec a,nimotu b
 where a.ID < b.ID
   and a.SumKg+b.Kg <= 20)
select ID,IDList,sumVal,sumKg
from (select ID,IDList,sumVal,sumKg,
      max(sumVal) over() as maxSumVal
      from rec)
where sumVal = maxSumVal;

出力結果
ID  IDList     sumVal  sumKg
--  ---------  ------  -----
 8  3,4,5,6,8      34     19

再帰with句で20kg以下となる全ての組み合わせを求めてから、分析関数のmax関数でsumValの最大値を求めてます。

▲ ページTOPに戻る

数独

再帰with句で数独を解く

"Oracle Database 11g Release 2に関する10の重要なこと - askTom Live -" の
Point4： Recursive Subquery Factoring 【再帰的副問合せのファクタリング】を意識しながら、再帰with句で数独を解いてみます。

with rec(LV,Val) as(
select 1,'530070000'
      || '600195000'
      || '098000060'
      || '800060003'
      || '400803001'
      || '700020006'
      || '060000280'
      || '000419005'
      || '000080079' from dual
union all
select LV+1,
case when substr(Val,LV,1) = '0'
     then substr(Val,1,LV-1) || to_char(cnt)
       || substr(Val,LV+1) else Val end
from rec a,(select RowNum as cnt from dict where RowNum <= 9) b
where LV <= 81
  and (substr(Val,LV,1) = '0' or cnt=1)
  and (substr(Val,LV,1) !='0'
    or (instr(substr(Val,trunc((LV-1)/9)*9+1,9),to_char(cnt)) = 0 /*横チェック*/
    and instr(substr(Val,mod(LV-1,9)+1   ,1),to_char(cnt)) = 0 /*縦チェック*/
    and instr(substr(Val,mod(LV-1,9)+1+ 9,1),to_char(cnt)) = 0
    and instr(substr(Val,mod(LV-1,9)+1+18,1),to_char(cnt)) = 0
    and instr(substr(Val,mod(LV-1,9)+1+27,1),to_char(cnt)) = 0
    and instr(substr(Val,mod(LV-1,9)+1+36,1),to_char(cnt)) = 0
    and instr(substr(Val,mod(LV-1,9)+1+45,1),to_char(cnt)) = 0
    and instr(substr(Val,mod(LV-1,9)+1+54,1),to_char(cnt)) = 0
    and instr(substr(Val,mod(LV-1,9)+1+63,1),to_char(cnt)) = 0
    and instr(substr(Val,mod(LV-1,9)+1+72,1),to_char(cnt)) = 0
    /*正方形チェック*/
    and instr(substr(Val,trunc(mod(LV-1,9)/3)*3+1+9*(trunc(trunc((LV-1)/9)/3)*3)   ,3),to_char(cnt))=0
    and instr(substr(Val,trunc(mod(LV-1,9)/3)*3+1+9*(trunc(trunc((LV-1)/9)/3)*3)+ 9,3),to_char(cnt))=0
    and instr(substr(Val,trunc(mod(LV-1,9)/3)*3+1+9*(trunc(trunc((LV-1)/9)/3)*3)+18,3),to_char(cnt))=0)))
select Val from rec
where LV = 82;

出力結果
Val
---------------------------------------------------------------------------------
534678912672195348198342567859761423426853791713924856961537284287419635345286179

再帰項で、1から9までの連番のインラインビューとの内部結合を繰り返してます。
結合条件で、その連番でマスを埋めることが可能かをチェックしてます。

参考リソース
マニュアル --- substr関数
マニュアル --- instr関数
OracleSQLパズル --- PL/SQLで数独を解く

参考リソース

マニュアル --- subquery_factoring_clause
@IT --- 新しい業界標準「SQL99」詳細解説

▲ ページTOPに戻る

"図でイメージするOracle DatabaseのSQL全集" インデックスに戻る

山岸 賢治（やまぎし けんじ）
Oracle ACEの1人。
OracleSQLパズルの運営者。

• ＜ 前のページへ
• 1
• 2
• 3
• 4
• 5
• 6