Using recursion and backtracking, write a program in Java to solve the Eight Queens problem as discussed in Section 6.1 by completing Queens.java. The output of your program should include the display of a board that solves the puzzle. Note: the display can be neatly formatted text such as:

1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1

OR

_______________
Q|_|_|_|_|_|_|_|
_|_|_|Q|_|_|_|_|
_|_|_|_|_|_|Q|_|
_|_|Q|_|_|_|_|_|
_|_|_|_|_|Q|_|_|
_|Q|_|_|_|_|_|_|
_|_|_|_|Q|_|_|_|
_|_|_|_|_|_|_|Q|

Note: the above boards do not represent a correct solution because the queen in the upper left corner is under attack by the queen in the lower right corner and vice-versa.

Extra Credit: Programming Problem 3 (Chapter 6):

You can begin the Eight Queens problem by placing a queen in the second square of the first column instead of the first square. You can then call placeQueens to begin with the second column. This revision should lead you to a new solution. Write a program that finds all solutions to the Eight Queens problem, displays the boards that represent solutions, and prints at the end the total number of solutions found.

Follow the documentation and style guidelines as discussed in class and in the book.

The assignment should be done individually.