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!
- Oracle 11gR2 – alternative for CONNECT_BY_ISLEAF function for Recursive Subquery Factoring (dedicated to Anton)
- Oracle RDBMS 11gR2 – new style hierarchical querying using Recursive Subquery Factoring
- Oracle RDBMS 11gR2 – Solving a Sudoku using Recursive Subquery Factoring
- Database Transaction Recorder – Adding Who to When and What to make Flashback take over from Journalling tables
- Bill of Materials and Hierarchical Queries – Which Component contains a component that…
- World Base Post » Blog Archive » The Knight’s Challenge – Recursive SQL Queries make a move on the Chess board
- The AMIS Summary of Oracle OpenWorld 2013 is available for download – 60-page white paper
- On the integrity of data in Java applications – presentation from JFall 2013
- Enriching XMLType data using relational data – XQuery and fn:collection in action
- Java 8 – Collection enhancements leveraging Lambda Expressions – or: How Java emulates SQL
- Oracle Database SQL – Recursive Subquery to inspect events in football matches – find the MVP
- Oracle Database 12c: Find most valuable player using MATCH_RECOGNIZE in SQL
- Oracle Database 12c: Pattern Matching through MATCH_RECOGNIZE in SQL
- Oracle Database 12c: joining and outer joining with collections
- Oracle Database 12c: PL/SQL package UTL_CALL_STACK for programmatically inspecting the PL/SQL Call Stack
- Oracle Database 12c: In Line PL/SQL Functions in SQL queries