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

SQLパズル

バックトラック法

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

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

データ作成スクリプト

create table ban(X,Y) as
select 1,1 from dual union
select 1,2 from dual union
select 1,3 from dual union
select 1,4 from dual union
select 1,5 from dual union
select 2,1 from dual union
select 2,2 from dual union
select 2,3 from dual union
select 2,4 from dual union
select 2,5 from dual union
select 3,1 from dual union
select 3,2 from dual union
select 3,3 from dual union
select 3,4 from dual union
select 3,5 from dual union
select 4,1 from dual union
select 4,2 from dual union
select 4,3 from dual union
select 4,4 from dual union
select 4,5 from dual union
select 5,1 from dual union
select 5,2 from dual union
select 5,3 from dual union
select 5,4 from dual union
select 5,5 from dual;

SQL

with rec(X,Y,LV,path) as(
select X,Y,1,'(' || to_char(X) || to_char(Y) || ')'
  from ban
 where X=1 and Y=1
union all
select b.X,b.Y,a.LV+1,a.path || '(' || to_char(b.X) || to_char(b.Y) || ')'
  from rec a,ban b
 where (b.X,b.Y) in((a.X+2,a.Y+1),
                    (a.X+2,a.Y-1),
                    (a.X-2,a.Y+1),
                    (a.X-2,a.Y-1),
                    (a.X+1,a.Y+2),
                    (a.X+1,a.Y-2),
                    (a.X-1,a.Y+2),
                    (a.X-1,a.Y-2)))
CYCLE X,Y SET IsLOOP TO 'Y' DEFAULT 'N'
select path
  from rec
 where IsLOOP = 'N'
   and LV = 25;

解説

上記のSQLは、10分たっても終了しませんでした。

PL/SQL3 ナイト巡回問題