-->
%+ 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 marked by %+ The compiler will only read the marked lines.
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:>).
The support functions build chessboards, install queens onto the chessboard and check whether positions are under attack.
%+ Expect
|
%+ %Expect
%+ implementation %+ %+ Import %+ "imperative"; %+ "collect/listfun"; %+ "collect/string"; %+ %Import
Naming conventionsThe 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 %+======================================================== |
PrintBoardPrintPos 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 %+======================================================== |
underAttackoccupied?(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 %+======================================================== |
%+ %Package