| Assigned: | Nov. 8 |
| Due: | Nov. 15, 11:59pm |
Write a program to solve 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.
At the end, the program should tell how many solutions it found.
Package nqueens-tools.cmg.html contains tools for you to use. Import it in your program. Just write
Import "nqueens-tools".To use this tool, do the following.
Get nqueens-tools.cmg.html. Store it, exactly as it is, as an Html document called nqueens-tools.cmg.html. Do not copy the contents in a browser window and paste to another document, since that will destroy the Html tags. If you ignore this advice, and this tool does not work, you have only yourself to blame.
Get nqueens.css. (If you have trouble, try this one and rename it to nqueens.css.) This is a style sheet. Store it with nqueens-tools.cmg.html.
Now write the program so that it places a queen in every row. Use standard function 'each' to select a column for the queen.
Let x = each [1,2,3,4].causes the current thread to fork into four branches, one where x is 1, another where x is 2, another where x is 3 and a last one where x is 4. Before adding the queen to the board, make sure that the chosen position is not under attack by a queen that is already on the board.
Remember that you need to put one queen in every row, but in a given row, you only want to put a queen in one column. So you need to treat the rows differently from the columns.
After successfully placing all of the queens on the board, print the board. There will generally be several boards printed, so do not run them together. Print a line between them.
After printing a board, fail to get the next solution. You can cause a failure using
MakeSure false.Wrap the entire body of your Execute block by Try ... %Try to catch the final failure. You do not need to say what to do to handle the failure. The default is to do nothing.
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. This means that, when an assignment to one of these boxes is backtracked over, the assignment is undone, and the box is restored to its previous value. So different branches of the backtracking computation will not interfere with one another.
You will want to count the number of solutions. For that, use a shared box, so that changes that you make to it will not be undone. You can create a shared box, initialized to 0, using
Var{--shared--} count =! 0.
DrawLine(n) %DrawLine prints a line made of 2n dashes. You can use it to separate different solutions from one another. This also illustrates a for-loop.
Define DrawLine(n). =
For ? from [1, ..., n] do
Display "--".
%For
Writeln.
%Define
Submit your program in the usual way, using the submit program. Be sure to indicate that the assignment number is 5.