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

Lucas Jellema

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
```

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

```  connect
by      ...
```

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
```

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!

## 3 thoughts on “The Knight's Challenge – Recursive SQL Queries make a move on the Chess board”

1. Hi Anton, That is exactly why I award a grand price to anyone with a solution to that challenge! Well spotted.

Lucas

2. Anton Scheffer says:

??? B1 is a white square, B8 is black. A bishop stays always on the same color. How could a bishop traverse from B1 to B8?
But the Knight’s Challenge is a nice one!

## AMIS Services organiseert op 26 april een kennissessie

Facebook0TwitterLinkedinOp 26 april organiseert AMIS Services een kennissessie, in twee blokken. In het eerste blok met als thema “Testautomatisering is software engineering”, Related posts: Writing a Word Search puzzle solver in SQL Oracle 11gR2 – alternative for CONNECT_BY_ISLEAF function for Recursive Subquery Factoring (dedicated to Anton) Juggling with SQL Types […]