Due: July 21, 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, it should tell how many solutions it found.
Package nqueens-tools.ast.html contains tools for you to use. Import it. Just write
Import "nqueens-tools".The tools packages uses a style sheet, nqueens.css. Copy both the tools package and the style sheet.
Now write the program so that it places a queen in each row. Before adding the queen to the board, check that the chosen position is not under attack.
After successfully placing the queens on the board, print the board. There will generally be several boards printed, so do not run them together.
Use standard function 'each' to select a column.
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.
Wrap the entire body of your execute by Try ... %Try to catch the final failure.
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. This means that different branches 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.
Define DrawLine(?n). =
For ? from [1, ..., n] do
Write["--"].
%For
Writeln.
%Define