再帰with句06 ナイト巡回問題

SQLパズル

バックトラック法

ナイト巡回問題は、与えられたマスを、ナイトが連続して飛び続けることで、
全てのマスを１回ずつ訪れる経路を求める問題である。 

行儀の良くないナイト巡回問題を解いてみます。

データ作成スクリプト

create table ban(
X integer,
Y integer);

insert into ban values
(1,1),(1,2),(1,3),(1,4),(1,5),
(2,1),(2,2),(2,3),(2,4),(2,5),
(3,1),(3,2),(3,3),(3,4),(3,5),
(4,1),(4,2),(4,3),(4,4),(4,5),
(5,1),(5,2),(5,3),(5,4),(5,5);

SQL

with recursive W(X,Y,Level,Path) as(
select X,Y,1,array['(' || X::text || Y::text || ')']
  from ban
 where X=1 and Y=1
union all
select b.X,b.Y,W.Level+1,
W.Path || ('(' || b.X::text || b.Y::text || ')')
  from W,ban b
 where ((b.X = W.X+2 and b.Y = W.Y+1)
     or (b.X = W.X+2 and b.Y = W.Y-1)
     or (b.X = W.X-2 and b.Y = W.Y+1)
     or (b.X = W.X-2 and b.Y = W.Y-1)
     or (b.X = W.X+1 and b.Y = W.Y+2)
     or (b.X = W.X+1 and b.Y = W.Y-2)
     or (b.X = W.X-1 and b.Y = W.Y+2)
     or (b.X = W.X-1 and b.Y = W.Y-2))
    and '(' || b.X::text || b.Y::text || ')' != all(W.Path)
    and Level <= 25)
select array_to_string(path,'-') as path
  from W
 where Level = 25;

解説

上記のSQLは、実行に5分かかりました。

PL/SQL3 ナイト巡回問題

---