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.