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). Instead of comments being marked as comments and code being unmarked, it is the other way around, with code marked and comments being the bulk of the program.

If you are looking at the HTML source, you will see that each line of code is shown inside a <pre class="code"> tag to mark it as something to be read by the compiler. The style sheet mentioned in the head of this file says to show those tags in this color.

You do not need to modify this file to compile it. The compiler will only read the marked lines. 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. Its name must be nqueens-tools.cmg.html.

Backtracking and variables

To store the chess board you will need to use a 2-dimensional array whose members are variables that can be changed. A changeable variable is a kind of object called a box. If b is a box then @b is the current value stored in box b, and statement 

  Make @b =! v.
stores value v into box b. If box b holds a value of type T then b itself has type [:T:].

We have seen that, for backtracking to work in a reasonable way, the system needs to store a trail so that, when a change to a variable is backtracked over, the change is automatically undone. Cinnameg has two kinds of variables: (1) nonshared boxes are trailed and changes to them are undone automatically; (2) shared boxes are not trailed, and changes to them are not undone on backtracking.

Data structure

The following defines type ChessBoard, the type of a chess board.

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

  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 : Integer -> ChessBoard;

AddQueen

AddQueen(b, i, j) %AddQueen puts a queen at location (i, j) on board b. 

   AddQueen      : (ChessBoard, Integer, Integer) -> ();

underAttack?

underAttack?(b, i, j) returns true if position (i, j) is currently under attack by a queen on board b. 

   underAttack?   : (ChessBoard, Integer, Integer) -> Boolean;

PrintBoard

PrintBoard(b) %PrintBoard prints chess board b. Here is a sample of what it prints. 

       Q . . . .
       . . Q . .
       . . . . Q
       . Q . . .
       . . . Q .

   PrintBoard    : ChessBoard -> ();


%Expect

Implementation of the tools

 implementation

 Import 
   "collect/list";
   "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:]];  %% A row of the board
   i,j,n : Integer
 %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 board. Here, rw is the row itself, not the index of the row. It is a list of boxes.

PrintBoard brd %Printboard prints entire board brd. 

 ========================================================
 Define PrintPos(bx). =
   If @bx then
     Display " Q".
   else
     Display " .".
   %If
 %Define
 ========================================================
 Define PrintRow(rw). =
   For bx from rw do
     PrintPos bx.
   %For
   Displayln.
 %Define
 ========================================================
 Define PrintBoard(brd). =
   For rw from rows(brd) do
     PrintRow rw.
   %For
 %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. It just looks to see if any boxes in the row contain true.

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