Package NqueensSupport export
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.
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.
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:]).
The support functions build chessboards, install queens onto the chessboard and check whether positions are under attack.
|
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 ======================================================== |
%Package