再帰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);
commit;

SQL

with RowN(X,Y,rn) as(
select X,Y,
cast(digits(smallint(RowNumber() over(order by X,Y))) as varchar(800))
  from ban),
s(X,Y,Level,path,rn,rnList) as(
select X,Y,1,
cast('(' || RTrim(char(X)) || RTrim(char(Y)) || ')' as varchar(800)),
rn,',' || rn
  from RowN
 where X=1 and Y=1
union all
select b.X,b.Y,s.Level+1,
s.path || '(' || RTrim(char(b.X)) || RTrim(char(b.Y)) || ')',
b.rn,s.rnList || ',' || b.rn
  from s,RowN b
 where ((b.X = s.X+2 and b.Y = s.Y+1)
     or (b.X = s.X+2 and b.Y = s.Y-1)
     or (b.X = s.X-2 and b.Y = s.Y+1)
     or (b.X = s.X-2 and b.Y = s.Y-1)
     or (b.X = s.X+1 and b.Y = s.Y+2)
     or (b.X = s.X+1 and b.Y = s.Y-2)
     or (b.X = s.X-1 and b.Y = s.Y+2)
     or (b.X = s.X-1 and b.Y = s.Y-2))
    and LOCATE(b.rn,s.rnList) = 0
    and s.Level <= 25)
select path
  from s
 where Level = 25;

解説

PL/SQL3 ナイト巡回問題

---