Due:
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. A queen attacks another queen that is in the same row or same column or same diagonal. So, to solve the problem, 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.
The problem is solved by backtracking. The program forks into different threads, exploring different options in separate threads. Only one thread is active at a time. When a thread finds that the decisions that it has made do not work, it stops. The stopping of one thread automatically activates another one.
You can also think of backtracking as backing up the computation, undoing a decision and trying a different one. Statement
Let x = each [1,2,3,4].causes the current thread to fork into four threads, one where x is 1, another where x is 2, another where x is 3 and a last one where x is 4. The thread that has set x = 1 runs, and the others wait. If the x = 1 thread gives up, then you think of the program backing up and undoing the decision that x = 1. It tries the other thread, where x = 2, and proceeds from the same point as if it had made this decision initially. Each thread, when it runs, works as if it were the first one taken. It does not know that the others have run before it.
This program represents an nxn chess board 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 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 collect/matrix, useful.
| matrix | A matrix is represented by a list of lists, but it is not
the same as its representation, because its type is different.
If L is a list of lists then expression
matrix(L) produces a matrix whose rows are given by
the members of L. For example, matrix [[1,2],[3,4],[5,6]] produces
matrix
1 2
3 4
5 6
For this assignment, you will create a matrix each of whose members is
a box that holds a boolean value. Each box in the matrix can have
its contents changed. See below for how to build the matrix. |
| 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. Astarte does not automatically dereference boxes. To get the list of the contents of those boxes, you need to map operator ! onto the list. (Function ! takes the content of an individual box.) Function contents, defined in library package boxes.ast, does that map. 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, with a true value indicating the presence of a queen and a false value indicating an empty square.
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.
| WARNING. Be sure that each of your code lines begins with %+ Otherwise, the compiler will not read them. |
| WARNING. Edit this document with a text editor, not with an HTML editor. An HTML editor will mess up the line structure. You have been warned. |
Although the code is written in Astarte, the document itself is written in HTML, and can be read by a web browser. When writing code, you will need to be careful. The < and > symbols should be written in HTML form (< and >). The compiler will recognize those as standing for < and >. Quote marks (") are written ".
%+Package nqueens %+Import %+ "collect/listfun"; %+ "collect/string"; %+ "collect/boxes"; %+ "collect/matrix"; %+%Import
The program 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:>. %% 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 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) prints 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. A convenient way to do that is to 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. For example, each(1 _upto_ n) produces several threads, 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. You can make a thread fail by doing statement
{false}
When you install a queen, just assign true to the box at the selected row and column. Use Assign to put something in a box. 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. It is used to separate different solutions from one another.
%+===================================================
%+ 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. Here is the main program.
%+ ==================================================
%+ 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, and changes
to it should not be undone when the program backtracks.
--------------------------------------------------
%+ 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, 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