For this assignment you will write a recursive solution to the N-Queens problem. You may work with one partner on this assignment. Be sure to include your partner's name on your assignment.

The N-Queens problem asks you to place N Queens on a NxN chessboard so that no two queens can attack each other using valid chess moves. A Queen in chess can move one or more squares horizontally, vertically, or diagonally. Thus once a queen is placed on the chessboard, no other queens can be places on the same row, column, or diagonals as the places queen. For an NxN board, you should print out all possible solutions to the problem along with the total number of solutions. One of 92 solutions for the 8x8 chessboard is shown below:

Note there are no solutions on a 2x2 or 3x3 chessboard. Your program should detect this situation and print an appropriate response. You should represent an NxN board as a two dimensional boolean array. Details on how to set up a two dimensional array in Java can be found in section 3.1.5 of the text.

A common solution to this puzzle is to recursively attempt to place a queen in successive rows of the board. A method such as public void placeQueen(int row), will try to recursively place a queen in all rows greater than or equal to the parameter row. Thus, placeQueen(0) will attempt to place one queen in one of the N columns of row 0 and then recursively attempt to place one queen in row 1 by calling placeQueen(1). When attempting to place a queen in row k, you must check for each potential column j in row k if a queen in any of the previously placed rows can attack column j. If so, a queen cannot be placed in column j and the algorithm must attempt to place a queen in another column. If no column is valid in row k, the algorithm must backtrack and change the positions of queens in previous rows. If the algorithm can successfully place a queen in the final row by calling placeQueen(n-1) and finding a successful column, a solution has been found and the board can be printed.

Your program should accept an integer as input to the command line. See RandomDays.java and java.util.Scanner for examples. Your program should take no longer than a five minutes for boards up to size 12x12. If you would like to test you solution for board sizes above 12x12, it is sufficient to simply count and display the number of solutions. Do not try to print out all the solutions. A 13x13 board has over 50,000 solutions and a 15x15 board has over 1 million (exact numbers can be found on Wikipedia). Exact numbers are not known for N>23. Please do not attempt to answer this question using our lab machines and your Java program. A few sample runs are shown below.

cumin[~]$ java NQueens
Usage: java NQueens <board size>


cumin[~]$ java NQueens 4
Sol #: 1
. Q . .
. . . Q
Q . . .
. . Q .

Sol #: 2
. . Q .
Q . . .
. . . Q
. Q . .

Found 2 unique solutions



cumin[~]$ java NQueens 1
Sol #: 1
Q

Found 1 unique solution



cumin[~]$ java NQueens 2
Sorry, no solutions exist

Along with your java source code, you should hand in a file named README. These files will be imported automatically via handin35. Your README should include a brief summary of your results, along with any known problems/bugs in your code. If you worked with a partner on this assignment, be sure to include your partner's name on the assignment. Only one partner need to submit the final solution.

Once you are satisfied with your programs, hand them in by typing handin35 at the unix prompt. You may run handin35 as many times as you like, and only the most recent submission will be recorded. This is useful if you realize after handing in some programs that you'd like to make a few more changes to them.

Home Page

Last updated: Tuesday, September 22, 2020 at 01:07:42 PM