10-317 階層問い合わせで迷路問題を解く

SQLパズル

matrixテーブル
ID  A  B  C  D  E  F  G  H  I  J
--  -  -  -  -  -  -  -  -  -  -
A   1  1  1  0  0  0  1  0  1  0
B   0  0  0  0  1  1  1  0  1  0
C   0  1  1  1  1  0  0  0  0  1
D   1  0  0  0  1  0  1  0  0  0
E   1  1  0  0  0  0  0  0  0  1
F   0  1  1  0  1  1  0  0  0  0
G   0  1  0  1  1  1  0  1  0  1
H   1  1  0  1  0  0  0  1  0  0
I   0  1  1  1  0  1  1  1  0  1
J   1  0  0  0  0  0  0  1  0  1
K   1  0  0  1  1  1  0  1  1  0
L   0  0  1  0  1  1  0  0  1  0
M   0  0  1  0  0  0  0  1  1  1
N   1  0  1  0  0  0  1  1  1  0
O   1  0  0  1  1  0  1  0  0  0

ID=Aの行のE列を出発点として、ID=Oの行までの経路を求める。
ただし、0と1を交互に訪問しなければならない。

出力結果
PATH
--------------------------------------------------------------------------------
[A,E];[B,E];[B,D];[C,D];[D,D];[D,E];[D,F];[D,G];[C,G];[B,G];[B,H];[B,I];[B,J];
[C,J];[D,J];[E,J];[F,J];[G,J];[G,I];[G,H];[G,G];[G,F];[H,F];[I,F];[J,F];[K,F];
[K,G];[K,H];[L,H];[L,I];[L,J];[M,J];[N,J];[N,I];[O,I]

[A,E];[B,E];[B,D];[C,D];[D,D];[D,E];[D,F];[D,G];[C,G];[B,G];[B,H];[B,I];[C,I];
[C,J];[D,J];[E,J];[F,J];[G,J];[G,I];[G,H];[G,G];[G,F];[H,F];[I,F];[J,F];[K,F];
[K,G];[K,H];[L,H];[L,I];[L,J];[M,J];[N,J];[N,I];[O,I]

こちらを参考にさせていただきました(英語)

データ作成スクリプト

create table matrix(ID,A,B,C,D,E,F,G,H,I,J) AS
select 'A',1,1,1,0,0,0,1,0,1,0 from dual union all
select 'B',0,0,0,0,1,1,1,0,1,0 from dual union all
select 'C',0,1,1,1,1,0,0,0,0,1 from dual union all
select 'D',1,0,0,0,1,0,1,0,0,0 from dual union all
select 'E',1,1,0,0,0,0,0,0,0,1 from dual union all
select 'F',0,1,1,0,1,1,0,0,0,0 from dual union all
select 'G',0,1,0,1,1,1,0,1,0,1 from dual union all
select 'H',1,1,0,1,0,0,0,1,0,0 from dual union all
select 'I',0,1,1,1,0,1,1,1,0,1 from dual union all
select 'J',1,0,0,0,0,0,0,1,0,1 from dual union all
select 'K',1,0,0,1,1,1,0,1,1,0 from dual union all
select 'L',0,0,1,0,1,1,0,0,1,0 from dual union all
select 'M',0,0,1,0,0,0,0,1,1,1 from dual union all
select 'N',1,0,1,0,0,0,1,1,1,0 from dual union all
select 'O',1,0,0,1,1,0,1,0,0,0 from dual;

SQL

select substr(sys_connect_by_path('[' || ID || ',' || X || ']',';'),2) as path
  from matrix UnPivot(vals for X in(A,B,C,D,E,F,G,H,I,J))
 where connect_by_IsLeaf = 1
   and ID = 'O'
start with ID = 'A' and X='E'
connect by nocycle (prior ID,prior X) in((chr(ascii(ID)+1),X),
                                         (chr(ascii(ID)-1),X),
                                         (ID,chr(ascii(X)+1)),
                                         (ID,chr(ascii(X)-1)))
       and mod(Level+1,2) = Vals
       and prior ID != 'O'
order by path;

解説

アルゴリズム講座/応用編/枝刈りをふまえて枝切りしてます。
Oracleの階層問い合わせ6 (枝切りの入門事項)

■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
connect by句のprior ID != 'O'によって、
命題 ID = 'O' ならば connect_by_IsLeaf = 1 が成立するから
where connect_by_IsLeaf = 1 and ID = 'O' は
where ID = 'O' でOKだと後で気付きました・・・
ブール代数パズル 2-2 命題が成立した状態での、論理積

---