Several months ago I used the classic 8-Queens chess puzzle as an illustration of using a little bit of math to determine intractable problems. In that article I teased a code solution for the puzzle but never followed up… until now.
There are 92 distinct solutions, including rotations and reflection duplicates. The package’s demo procedure will produce all of them. Here is an excerpt of the output.
SQL> BEGIN 2 eight_queens.demo; 3 END; 4 / Solution 1 ================================= --------------------------------- | Q | | | | | | | | | | | | | Q | | | | | | | | | | | | Q | | | | | | | Q | | | | | | Q | | | | | | | | | | | | | Q | | | | Q | | | | | | | | | | | Q | | | | | --------------------------------- ================================= Solution 2 ================================= --------------------------------- | Q | | | | | | | | | | | | | | Q | | | | | | | | | | | Q | | | | Q | | | | | | | | | | | | | Q | | | | | | Q | | | | | | | Q | | | | | | | | | | | | Q | | | | --------------------------------- ================================= Solution 3 ================================= --------------------------------- | Q | | | | | | | | | | | | | | | Q | | | | | | Q | | | | | | | | | | | Q | | | | | | | | | | | Q | | | Q | | | | | | | | | | | | Q | | | | | | | Q | | | | | | --------------------------------- ================================= ... 89 other solutions follow ...
The algorithm I used to find the solutions is fairly straight forward. It marches through the rows placing one queen per row. For each row it tries to put the queen on each column and look for any solutions for that position, if the queen is safely put into a column for that row, the procedure then calls itself to search for the next row. When it reaches the 8th row and safely places a queen there, it will then display that solution.
Checking for a safe position is a little tricky. Since we iterate by rows and only put one queen per row, it’s not necessary to check for collisions there, but we do need to check for collisions with other queens on the trial column as well as any queens in prior rows that may attack the trial position via a diagonal. The diagonal checks are accomplished with a bit of arithmetic, taking advantage of patterns in addition or subtraction of the row and column numbering. The comments include a grid of each direction of diagonals to show why the math works.
CREATE OR REPLACE PACKAGE eight_queens
AS
PROCEDURE demo;
END;
/
CREATE OR REPLACE PACKAGE BODY eight_queens AS-- .///.-- (0 o)---------------0000--(_)--0000------------------- Sean D. Stuber-- sean.stuber@gmail.com---- oooO Oooo--------------( )-----( )----------------- \ ( ) /-- \_) (_/SUBTYPE chess_range IS PLS_INTEGER RANGE 1 .. 8; TYPE queenlist IS TABLE OF chess_range INDEX BY chess_range; g_cnt PLS_INTEGER; -- column + row column - row -- 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 -- * * * * * * * * * * * * * * * * -- --------------------------------- --------------------------------- --1 * | 0 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | -- --------------------------------- --------------------------------- --2 * | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| | -1| 0 | 1 | 2 | 3 | 4 | 5 | 6 | -- --------------------------------- --------------------------------- --3 * | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| | -2| -1| 0 | 1 | 2 | 3 | 4 | 5 | -- --------------------------------- --------------------------------- --4 * | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| | -3| -2| -1| 0 | 1 | 2 | 3 | 4 | -- --------------------------------- --------------------------------- --5 * | 6 | 7 | 8 | 9 | 10| 11| 12| 13| | -4| -3| -2| -1| 0 | 1 | 2 | 3 | -- --------------------------------- --------------------------------- --6 * | 7 | 8 | 9 | 10| 11| 12| 13| 14| | -5| -4| -3| -2| -1| 0 | 1 | 2 | -- --------------------------------- --------------------------------- --7 * | 8 | 9 | 10| 11| 12| 13| 14| 15| | -6| -5| -4| -3| -2| -1| 0 | 1 | -- --------------------------------- --------------------------------- --8 * | 9 | 10| 11| 12| 13| 14| 15| 16| | -7| -6| -5| -4| -3| -2| -1| 0 | -- --------------------------------- --------------------------------- FUNCTION safe(p_row IN chess_range, p_col IN chess_range, p_queens IN queenlist) RETURN BOOLEAN IS r PLS_INTEGER := 1; v_safe BOOLEAN := TRUE; BEGIN WHILE v_safe AND (r < p_row) LOOP -- Since we always add the next queen by moving down (i.e. increasing row#) -- we don't need to check for prior row collisions but we do need to check the current column -- as well as the diagonals up/right and up/left -- You can see in the grids above, the sum of the column and row for the up/right diagonals are all the same -- Similarly, the difference of column subtracting row are the same for the up/left diagonals -- So, checking for a diagonal collision is a simple matter of addition or subtraction. IF (p_col = p_queens(r)) OR ((p_col + p_row) = (p_queens(r) + r)) OR ((p_col - p_row) = (p_queens(r) - r)) THEN v_safe := FALSE; END IF; r := r + 1; END LOOP; RETURN v_safe; END safe; PROCEDURE drawboard(p_queens IN queenlist) IS BEGIN g_cnt := g_cnt + 1; DBMS_OUTPUT.put_line('Solution ' || TO_NUMBER(g_cnt, '999')); DBMS_OUTPUT.put_line(RPAD('=', 33, '=')); DBMS_OUTPUT.put_line(RPAD('-', 33, '-')); FOR r IN 1 .. 8 LOOP FOR c IN 1 .. 8 LOOP DBMS_OUTPUT.put('| '); IF p_queens(r) = c THEN DBMS_OUTPUT.put('Q '); ELSE DBMS_OUTPUT.put(' '); END IF; END LOOP; DBMS_OUTPUT.put_line('|'); DBMS_OUTPUT.put_line(RPAD('-', 33, '-')); END LOOP; DBMS_OUTPUT.put_line(RPAD('=', 33, '=')); END drawboard; PROCEDURE solve(p_queens IN OUT queenlist, p_row IN chess_range) IS BEGIN IF p_row BETWEEN 1 AND 8 THEN -- Try the queen for this row in each column of the board FOR c IN 1 .. 8 LOOP IF safe(p_row, c, p_queens) THEN p_queens(p_row) := c; IF p_row = 8 THEN -- If we safely placed a queen on the 8th row then we've found a solution -- show the board and exit drawboard(p_queens); ELSE -- We haven't placed all the queens, move to the next row and keep searching solve(p_queens, p_row + 1); END IF; END IF; END LOOP; END IF; END solve; PROCEDURE demo IS v_queens queenlist; BEGIN g_cnt := 0; solve(v_queens, 1); END demo; END; /
For those curious about performance, but don’t have access or time to try it on a db, the demo completes in less than two one-hundredths of a second on one of my Oracle cloud Free Tier databases. It takes much longer to display and scroll through the results than it does to generate them.
This was a fun little puzzle. When I first encountered this as a coding challenge it was part of an introductory coding class in college. There we used a non-recursive method for searching for a single solution. Here I’ve chosen recursion as it’s, I think, a more intuitive approach to the problem as well as being relatively compact code. Also, I extended the code to return all of the boards not just the first one it finds.