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 %+ and shown in this color. (If you do not have the style sheet nqueens.css, the code will be the same color as the comments.)

You do not need to modify this file to compile it. The compiler will only read the marked lines. But do not use a browser to copy the body and paste it into another file. Save this document exactly as it is, as an html file, using the "Save As" menu item in the browser.

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 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 
%+   "collect/listfun";
%+   "collect/string";
%+ %Import

Naming conventions

The tools use 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). =
%+   Make 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.

Position (i,j) is under attack if either the row or column or left-to-right diagonal or right-to-left diagonal containing (i,j) is already occupied. 

%+========================================================
%+ 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