This package solves the n-queens problem using backtracking. The problem is to place n queens on an nxn chess board in such a way that no two queens are attacking one another. There must be exactly one queen in each row and one queen in each column. Also, there cannot be two queens on the same diagonal.
This program asks the user for n, and shows all possible solutions. For example, if n is 5, one of the solutions that is printed is
Q . . . .
. . Q . .
. . . . Q
. Q . . .
. . . Q .
where a dot represents an empty square and a Q represents a queen.
This program is currently incomplete. You need to complete it. There are three sections, marked below, that you need to fill in. They are the parts that generate the solutions.
This program represents an nxn chess board as a matrix (a two-dimensional array). Each member of the matrix is a box 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 threads 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 content of the box is put back the way it used to be.
You might find the following functions, provided by package matrix, useful.
| nrows | (nrows m) is the number of rows in matrix m. |
| ncols | (ncols m) is the number of columns in matrix m. |
| row | (row n m) is the n-th row of matrix m. Since the members of our matrices are boxes, (row n m) is a list of boxes. Indexing is from 1. (So the top row is row 1.) |
| column | (column n m) is the n-th column of matrix m. Indexing is from 1. |
| diagLR | (diagLR (i,j) m) is the
left-to-right diagonal of matrix m that contains index
(i,j). Indexing is from 1.
For example, the following shows diagLR (2,3) of
a 6x6 matrix. The list is indicated by *'s.
It is the entire diagonal, from top to bottom,
that contains row 2, column 3.
. * . . . . . . * . . . . . . * . . . . . . * . . . . . . * . . . . . . |
| diagRL | This is similar to diagLR, but it gives a right-to-left
diagonal. For example, the following shows
diagRL (3,5) of a 6x6 matrix. Notice that the
diagonal contains the element at row 3, column 5.
. . . . . . . . . . . * . . . . * . . . . * . . . . * . . . . * . . . . |
Important note: When a row, column, etc. is extracted from a matrix of BOXES, the result is a list of boxes. To get the list of the contents of those boxes, you need to map \ onto the list. (Function \ takes the content of an individual box.) Function contents, defined in library package boxes.ast, does that. So the contents of row i of matrix m can be obtained as
contents(row i m)In our case, that will be a list of Boolean values.
%+Package nqueens %+Import %+ "collect/listfun"; %+ "collect/string"; %+ "collect/boxes"; %+ "collect/matrix"; %+%Import
%+ Assume bx: <:Boolean:>. %% bx is a box holding a boolean
%+ Assume brd: Matrix(<:Boolean:>).
%+ %% brd is a matrix of boxes, each holding
%+ %% a boolean value. It represents
%+ %% a chess board.
%+ Assume rw: [<:Boolean:>]. %% rw is a list of boxes holding booleans.
%+ %% It is a row, column, etc of a
%+ %% chess board.
We want to be able to print a chess board with queens. Function PrintBoard prints a dot for each unoccupied position, and a Q for each queen. So a 4x4 board might look like this.
. Q . . . . . Q Q . . . . . Q .Function PrintBoard does that. It uses helpers PrintPos and PrintRow.
PrintPos(bx) prints the contents of box bx as a Q or a dot. True means a Q, false means a dot.
%+========================================================
%+ Define PrintPos(?bx). =
%+ Write[If \bx then " Q" else " ." %If].
%+ %Define
%+========================================================
PrintRow(rw) 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 PrintRow(?rw). =
%+ MapProc (PrintPos), rw.
%+ Writeln[].
%+ %Define
%+========================================================
PrintBoard(brd) print the entire board brd.
%+========================================================
%+ Define PrintBoard(?brd). =
%+ MapProc (PrintRow), (rows brd).
%+ %Define
%+========================================================
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.
%+========================================================
%+ Define occupied?(?rw) = someSatisfy holdsTrue rw |
%+ Let holdsTrue(?b) = \b.
%+ %Define
%+========================================================
The following function checks to see whether position (i,j) of chess board brd is already under attack by a queen. Position (i,j) is under attack if its row, column, left-to-right diagonal or right-to-left diagonal contains a queen.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This function is not written. Write it, and delete
%% this comment. There are three parameters, i, j and brd.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The following finds all solutions to the n-queens problem, and returns them one at a time in separate threads, by backtracking through all of the solutions.
Hint: Pass the chess board as a parameter. Write a for-loop that installs a queen in each row. (You need to install a queen in every row, so just do them all).
Do not use a for-loop to install a queen in a column of a row, since for each row, you only need a queen in one of the columns, not all columns.
To install a queen in a given row, consider each possible column. Get the column numbers in a stream. For example, each(1 _upto_ n) produces a stream, first returning 1, then 2, then 3, etc. When you get a column, just test it to see that there is no attack. If there is, just fail. Let another thread run. Do not try to do another thread's work for it.
When you install a queen, just assign true to the box at the selected row and column. The box at index (i,j) of matrix m is m#(i,j).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This function is not written. Write it, and delete
%% this comment.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
DrawLine(n). prints a line made of 2n dashes.
%+===================================================
%+ Let DrawLine(?n). =
%+ For ? from 1 _upto_ n do
%+ Write["--"].
%+ %For
%+ Writeln[].
%+ %Let
%+===================================================
The main program reads n and prints all solutions to the n-queens problem.
%+ ==================================================
%+ Execute
%+ Assume n: Natural.
%+
%+ Write["How large a board shall I use? "].
%+ Extract [$(?n)] from bxStdin.
%+ DrawLine(n).
-------------------------------------------------
%% Variable bxNsolns counts the number of solutions
%% found. It is a shared box, since it must be
%% updated by all of the successful threads.
--------------------------------------------------
%+ Var{shared} bxNsolns := 0.
--------------------------------------------------------
%% brd is the board. Let's fill it with false, so that
%% there are no queens on the board yet. (You can create
%% the board here or inside the function that fills the board.
%% If you create it inside the other function, delete it
%% here.)
--------------------------------------------------------
%+ Var{nonshared} brdrows(n,n) all := false.
%+ Let brd = matrix(brdrows).
--------------------------------------------------------
%% After each successful solution is found, a failure
%% is caused, forcing backtracking to find the next
%% solution. Finally, after the last solution is found,
%% the n-queens finder will fail. This try catches that
%% last failure.
---------------------------------------------------------
%+ Try
----------------------------------------------
%% Get a solution and print it, and increment
%% the solution count. Print a line between
%% solutions to separate them.
--------------------------------------------
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This part is not written. Write it and delete
%% this comment.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
--------------------------------------------
%% Fail, to force more solutions to be found.
--------------------------------------------
%+ DrawLine(n).
%+ {false}
%+ %Try
------------------------------------------
%% After printing all of the solutions, print
%% the number of solutions found.
--------------------------------------------
%+ Writeln[].
%+ Writeln["There are ", $(\bxNsolns), " solutions."].
%+%Execute
%+%Package
Hand in this program using the handin command as assignment 8.