Support Tools for the N-Queens Program

%+ Package NqueensSupport export

About this program

This program is written in a style called literate programming, where the focus is on the comments (such as this one) and the code is marked. Each line of code is marked by %+ The compiler will only read the marked lines.

Data structure

An nxn chess board is represented as a matrix (a two-dimensional array). Each member of the matrix is a box, or variable, that holds a boolean value, with value true indicating the presence of a queen, and false indicating the absence of a queen.

The boxes in the array are nonshared, so that different branches in a backtrack search automatically work with different copies of the boxes, and they do not interfere with one another. When the program backtracks over an assignment to a nonshared box, the assignment is undone, and the content of the box is put back the way it used to be. You do not have to do that yourself.

%+  Import "collect/matrix".
%+  Abbrev ChessBoard = Matrix(<:Boolean:>).

Support functions

The support functions build chessboards, install queens onto the chessboard and check whether positions are under attack.

%+ Expect

newChessBoard newChessBoard(n) returns a new nxn chess board. There are no queens on it initially. %+ newChessBoard : Natural -> ChessBoard; AddQueen AddQueen(b,i,n) %AddQueen puts a queen at location (i,j) on board b. %+ AddQueen : (ChessBoard, Natural, Natural) -> (); underAttack underAttack(b,i,j) returns true if position (i,j) is currently under attack by a queen on board b. %+ underAttack : (ChessBoard, Natural, Natural) -> Boolean; PrintBoard PrintBoard(b) %PrintBoard prints chess b. Here is a sample of what it prints. Q . . . . . . Q . . . . . . Q . Q . . . . . . Q . %+ PrintBoard : ChessBoard -> ();

%+ %Expect

Implementation of the tools

%+ implementation
%+
%+ Import 
%+   "imperative";
%+   "collect/listfun";
%+   "collect/string";
%+ %Import

Naming conventions The tools uses the naming conventions shown here. For example, Every occurence of the name bx stands for a box that holds a boolean value. %+======================================================== %+ Assume %+ bx : <:Boolean:>; %+ brd : ChessBoard; %+ rw : [<:Boolean:>]; %+ i,j,n : Natural %+ %Assume %+========================================================

newChessBoard %+======================================================== %+ Define newChessBoard(?n) = matrix brdArray | %+ Var{nonshared} brdArray(n,n) all := false. %+ %Define %+========================================================

AddQueen %+======================================================== %+ Define AddQueen(?brd,?i,?j). = %+ Assign brd#(i,j) := true. %+ %Define %+========================================================

PrintBoard PrintPos bx %PrintPos prints the contents of box bx as a Q or a dot. True means a Q, false means a dot. PrintRow rw %PrintRow prints row rw of the array. Here, rw is the row itself, not the index of the row. It is a list of boxes. %+======================================================== %+ Define PrintPos(?bx). = %+ Write[If !bx then " Q" else " ." %If]. %+ %Define %+======================================================== %+ Define PrintRow(?rw). = %+ MapProc (PrintPos) &, rw. %+ Writeln. %+ %Define %+======================================================== %+ Define PrintBoard(?brd). = %+ MapProc (PrintRow) &, (rows brd). %+ %Define %+========================================================

underAttack occupied?(rw) tells whether list rw contains a queen. rw might be a row, column or diagonal of the chess board. It is a list of boxes. %+======================================================== %+ Define occupied?(?rw) = someSatisfy (!) rw. %+======================================================== %+ Define underAttack(?brd,?i,?j) = %+ someSatisfy occupied? %+ [row i brd, %+ column j brd, %+ diagLtoR(i,j) brd, %+ diagRtoL(i,j) brd] %+ %Define %+========================================================

End package

%+ %Package