PuzzleSolve:

PuzzleTest:

2. Eight-Queens Problem 2.1. Problem Description A chess board is an 8x8 matrix on which chess pieces are placed. A real chess game has a variety of pieces that have different rules defining how each can move and whom they can attack. For example, the queen can attack any other piece on the same row, column, or diagonal. Your program is to find solutions to the Eight Queens Problem. Place eight queens on a standard chess board such that no queen can attack another. There are 92 unique solutions! 2.2. Notes . . You must use the PuzzleSolve class and PuzzleTest interface to solve this problem. Your solution must be recursive. Turn in only your source file: Queens PuzzleSolver.java. It will have an inner class which defines your implementation of PuzzleTest. Make sure your class is not in a package (that is, it is in the default package). . Your output must include the names of all team members. Hint: What is your Universe? The Queen positions 1- 8. Generate all possible combinations of these positions and test each one. Each candidate represents the position of that queen on that row. Therefore, you don't have to worry about queens attacking on rows and columns, that's handled by the nature of your solution. You just need to check diagonals. Determining whether two queens can attach on the diagonal is simpler than you may think. Look at some examples by hand and see if you can determine the simple mathematical relationship 2.3. Required Main Class Queens Puzzle Solver 2.4. Required Input Not applicable 2.5. Required Output Your output should look like the following: Eight-Queens Puzzle - Team Member 1, Team Member 2, Team Member 3, Solution #1 Q Q Solution #2 Q Q ... The other 89 solutions have been left off ... Solution #92 Q Q Q *PuzzleSolve.java X D *PuzzleTest.java 2 import java.util.ArrayList; 3 4 public class PuzzleSolve { 50 public static void solve(int k, ArrayList S, ArrayList U, PuzzleTest t) { 6 for (int i = 0; i { 5 public boolean test(ArrayList candidate); 6 public void foundSolution(ArrayList soution); 7 }