Package NqueensSupport export
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 shown in this color. (If you do not have the style sheet nqueens.css, the code will be the same color as the comments. It is important to have the style file.)
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.
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:>).
The support functions build chessboards, install queens onto the chessboard and check whether positions are under attack.
Expect
|
%Expect
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:>]; 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 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 ======================================================== |
%Package