This assignment will help you learn about backtracking.
The 8-queens problems asks us to place 8 queens on a chessboard so that no two can capture one another; that is, no two are on the same row, column, or diagonal. One solution (figure from Wikipedia) is:
We can generalize 8-queens to n-queens, where the board is n x n, and we are to place n queens.
As we discussed in class, simply generating all possible queen placements and testing each of them for validity is not practical, since there are just too many possibilities. Instead, at each step we consider all possible choices for a given column, and recursively solve the rest of the puzzle for each feasible choice. The important point is that if a given choice is not feasible (because it somehow conflicts with earlier choices), that choice should be pruned.
Write a method that, given a number n creates a list of all valid placements of n queens on an n x n chessboard so that no two lie on in the same row, column, or diagonal. You should employ a recursive backtracking algorithm to do so.
A solution should be represented as an array, where the kth position in the array contains the position of the queen in the kth column. The values indicate which row (among 1 through n) in that column has a queen. Thus the array {2,4,6,8,3,1,7,5} represents the solution shown above (listing columns left to right and counting rows bottom to top).
Your program should create a list of all possible solutions. For example, when n = 6, your program should return:
[{2,4,6,1,3,5},
{3,6,2,5,1,4},
{4,1,5,2,6,3},
{5,3,1,6,4,2}].
You should construct the lists column by column. For each column
try all values from 1 to
n for the kth queen and eliminate those that are
invalid before calling your function recursively to place the rest of the queens.
When there are no more queens to be placed your array of partial
placements a solution. Make a copy of the array and save it in
your solution list. If your array is arr, then
arr.clone() will make a copy of the array.
Write a driver (i.e., the main method) to test your solver.
The driver should repeatedly prompt the user to enter n
and, if n > 8, print only the number of solutions; if n <= 8, print the number of solutions
as well as the solutions themselves.
When the user enters a non-positive number in response to the prompt for n,
the program should quit.
See Section 1.6 of the text (on page 38) to review how to read input from the keyboard.
Note that the four solutions to the 6-queen problem, given above, are not really different: the first and fourth are mirror images of each other left to right, as are the second and the third (the lists are reversals of each other). For this problem, you are to take the output from the first problem and create a list of solutions, no two of which are symmetrical. There are multiple symmetries here that you must detect: reflections along either a vertical line, a horizontal line, or a diagonal line (either diagonal), as well as rotations by 90, 180, or 270 degrees.
Detecting reflections vertically or horizontally is easy. Detecting diagonal reflections is a bit harder. Detecting rotations is hardest. For detecting diagonals and rotations it may be easiest to convert your list of column values to a list of (row, column) pairs. If you stare at it enough, you'll even see that rotations can be generated by composing other symmetries (though a direct implementation is fine).
Submit via Canvas: