| Assigned: | Monday, October 26 |
| Due: | Wednesday, November 4, 11:59pm |
Write a Cinnameg program to solve the n-queens problem using backtracking.
The problem is to place n queens on an n×n 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 contains tools for you to use. Import it in your program. Just write
Import "nqueens-tools".Look at the file to see what it provides.
Now write the program so that it places a queen in every row. Use standard function 'each' to select a column for the queen.
!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, you will need to get the next solution. Make the program fail. That will cause it to backtrack and to look for another solution. You can cause a failure using
Ensure 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 n×n 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.
Submit your program in the usual way, using the submit program. Be sure to indicate that the assignment number is 6.