*Steven Pemberton
CWI, Amsterdam*

I was asked what an Eight Queens program would look like in ABC. The problem is: can you put eight queens on an (8 by 8) chess board board in such a way that they cannot take each other. A queen can take by moving vertically, horizontally or diagonally.

My first version was a fairly traditional version – for
instance see E.W. Dijkstra's version in the book *Structured
Programming* – although of course, I immediately generalised it to any
number of queens:

HOW TO QUEENS n: DISPLAY n filled {}

The command *DISPLAY* just displays the
board, which is represented as a table whose keys are the row numbers (1 to n),
and whose items are the column number of the piece for that row:

HOW TO DISPLAY board: IF board = {}: WRITE "No solution" / FOR p IN board: WRITE "# "^^(p-1), "O " WRITE "# "^^(#board - p) /

The work of finding a solution for the problem is done by the
function *filled* . If the board is already of size n then
an answer has already been found. Otherwise, a piece is added for the next row:
each possible piece is tried, and if one is found that is 'safe'– it can't be
taken by any of the other queens on the board – it is placed on the board (by
*board'* ), and *filled* is called to
fill the next row. If the result of that call is successful, then that result
is returned, otherwise the next piece for the current row is tried. If no piece
is found, then the empty board is returned, to indicate failure.

The check for safeness uses properties of row and column numbers to see if a position is being attacked.

The function uses backtracking and the fact that ABC functions can't produce side-effects. See my article Backtracking in B in the ABC Newsletter 5 for more details about backtracking in ABC.

HOW TO RETURN n filled board: IF #board = n: RETURN board FOR p IN {1..n}: IF safe: PUT n filled board' IN new IF new <> {}: RETURN new RETURN {} safe: REPORT col AND left AND right col: REPORT p not.in board left: REPORT NO r IN keys board HAS r+board[r] = #board+1+p right: REPORT NO r IN keys board HAS r-board[r] = #board+1-p board': PUT p IN board[#board+1] RETURN board

>>> QUEENS 8 O # # # # # # # # # # # O # # # # # # # # # # O # # # # # O # # # # O # # # # # # # # # # # O # # O # # # # # # # # # O # # # #

However, I also decided to try a more direct solution, by simulating what you would do by hand more closely. Here the board is again a table with the row number as key, but with a list of numbers as items. These numbers represent which positions on the current row are not being attacked. So you start out with a full board, which must then be emptied:

HOW TO QUEENS' n: PUT {} IN board FOR i IN {1..n}: PUT {1..n} IN board[i] DISPLAY' 1 emptied board

HOW TO DISPLAY' board: IF board = {}: WRITE "No solution" / FOR row IN board: CHECK #row = 1 PUT min row IN p WRITE "# "^^(p-1), "O " WRITE "# "^^(#board - p) /

The work is done by the function *emptied*.
You no longer have to check if a piece is safe or not: for each row you have
just the list of safe pieces available. When you choose a piece, all the
positions that are attacked by this piece are then removed from the board, and
the next row is tried.

HOW TO RETURN n emptied board: IF n > #board: RETURN board FOR p IN board[n]: PUT (n+1) emptied board' IN new IF new <> {}: RETURN new RETURN {} board': PUT {p} IN board[n] FOR row IN {n+1..#board}: PUT board[row] less {p; p+(row-n); p-(row-n)} IN board[row] RETURN board

This uses a small function to return the difference between two lists:

HOW TO RETURN l1 less l2: FOR i IN l2: IF i in l1: REMOVE i FROM l1 RETURN l1

>>> QUEENS' 8 O # # # # # # # # # # # O # # # # # # # # # # O # # # # # O # # # # O # # # # # # # # # # # O # # O # # # # # # # # # O # # # #

>>> QUEENS' 11 O # # # # # # # # # # # # O # # # # # # # # # # # # O # # # # # # # # # # # # O # # # # # # # # # # # # O # # # # # # # # # # # # O # O # # # # # # # # # # # # O # # # # # # # # # # # # O # # # # # # # # # # # # O # # # # # # # # # # # # O #

As it turns out, this version runs faster than the first version. The reason for this is that you have to search much less to find a candidate piece for a row, and when you reach a row where all positions are attacked, you know it immediately, without having to check each position separately.