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.
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.
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
If your code runs (and produces the correct answer) for a 14x14 board in under 30 seconds, you will get 10 bonus points. If you code runs in under 60 seconds you will get 5 bonus point.
(But make sure that you don't sacrifice good coding style for speed or you will lose points.)
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.