The Knight's Challenge – Recursive SQL Queries make a move on the Chess board

In my quest to position ‘connect by’ (and its 11g successor, Recursive Subquery) as mechanism for recursive queries rather than just an hierarchical query facility, I stumbled across a simple, fairly meaningless challenge to take on: a knight on a chess board – and the question of finding its way from one square to another.
Recursive querying in general consists of two elements:

• the initial situation, the starting point (the n=1 step)
• the algoritm to get from one stage to the next (the n to n+1 step)

A third, mandatory, element is the termination of the query: when is the journey complete, what is the maximum value for n or what is the exit condition. The challenge I am taking on is simple: the knight is on square B1 (first row, second column, the starting position for a White Knight). In how many moves can it be on square B8 – and what is the path that it should take? The recursive aspect to this challenge is the following:

• The starting position is well known – square B1 on a board that has 8 rows (1-8) and 8 columns (A-H)
• To go from one position (n) to the next (n+1), the knight can make its familiar jump, that entails either two columns and one row or two rows and one column (in any direction as long the knight stays on the board)
• The termination condition in this case is either the knight is on square B8 or the maximum number of moves is reached (set at 10)

In terms of SQL, the start and end conditions can be expressed in a simple in-line query:

with objectives as
( select 'B1' start_square
  ,      'B8' end_square
  ,      10   maximum_number_of_moves
  from   dual
)

These objectives are translated in purely numerical indications of the start and end columns and rows:

, params as
( select to_number(substr(start_square,2,1)) start_row
  ,      ascii(substr(start_square,1,1))-64  start_column
  ,      to_number(substr(end_square,2,1))   end_row
  ,      ascii(substr(end_square,1,1))-64    end_column
  from   objectives
)

The chess board itself, with the 64 squares that we are going to traverse, is created using two inline views, one to create a set of 8 elements, the second that cross joins this set to create the 64 squares – composed from 8 rows and 8 columns.

, octo as
( select level num
  from   dual
  connect by level < 9
)
, board as
( select rw.num rw
  ,      col.num cl
  from   octo rw
         cross join
         octo col
)

To recursively traverse the allowable paths, we use the connect by facility. The algoritm to go from one stage (n) to the next (n+1) is expressed using the PRIOR keyword in the CONNECT BY clause.

  connect
  by     ...
          (
            (abs(rw - prior rw) = 1 and abs(cl - prior cl) =2) -- one row, two columns
          or
            (abs(rw - prior rw) = 2 and abs(cl - prior cl) =1) -- two rows, one column
          )

Also in the CONNECT BY is the termination condition:

  connect
  by      nocycle
           ...
           level <= maximum_number_of_moves
           and not (prior rw = end_row and prior cl = end_column) -- cut off when end square has been reached
  start with rw = start_row and cl = start_column

as well as the start condition (using START WITH and referring to the OBJECTIVES that were expressed in the first inline view).

  connect
  by      ...
  start with rw = start_row and cl = start_column

The paths that are uncovered through the recursive algoritm are traced using the SYS_CONNECT_BY_PATH function, that records every square visited along the way. To make the path more pleasing to the eye, the column indication is translated from the numberic 1-8 value to the more common A-H label.

, paths as
( select  sys_connect_by_path( chr(64+cl)||rw,',') path
  ,       level-1 number_of_moves
  from    board
          cross join
          params
          cross join objectives
  connect
  by      nocycle
            ....

The complete query starts with WITH and is constructed like this:

WITH objectives
,       parameters
,       octo
,       board
,       paths (as recursive traversal of board elements starting at parameters.start_square and ending at parameters.end_square or when level > objectives.maximum_number_of_moves)
select path
,      number_of_moves
from   paths
       cross join
       objectives
where  instr(path, end_square) > 0

It turns out by the way that there are many ways to have the knight go from B1 to B8, the shortest ones take 5 moves:

PATH                      NUMBER_OF_MOVES
------------------------------------------
,B1,D2,B3,D4,C6,B8        5
,B1,D2,B3,A5,C6,B8        5
,B1,D2,F3,D4,C6,B8        5
,B1,D2,C4,E5,D7,B8        5
,B1,D2,C4,B6,D7,B8        5
,B1,D2,E4,F6,D7,B8        5
,B1,A3,B5,A7,C6,B8        5
,B1,A3,B5,C7,A6,B8        5
,B1,C3,A2,B4,A6,B8        5
,B1,C3,A2,B4,C6,B8        5
,B1,C3,E2,D4,C6,B8        5

Challenge to the reader

Having presented my solution, I would now like to challenge the reader to come up with a solution in SQL to find the path a Bishop could traverse from B1 to B8. A solution to that challenge would qualify for a grand prize!