Homework 5 Java | Complete Solution

Homework 5
 

This Homework

1. Implementation: (50 Points) 

A chessboard contains 64 squares that form 8 rows and 8 columns. The most powerful piece in the game of chess is the queen because it can attack any other piece within its row, within its column, or along its diagonal. The Eight Queens problem asks you to place eight queens on the chessboard so that no queen can attack any other queen.

Complete all the methods in Queens.java that have a comment saying "To be implemented for Homework 5". You must also write a driver that uses the Queens class to place the queens on the board in a manner that no queen can attack any other queen. Your driver must also make the call to display the chess board with your computed solution(s).

2. Extra Credit: 
   • (5 Points) Revise the program that you just wrote for the Eight Queens problem so that it answers the following questions:

1. How many backtracks occur? That is, how many times does the program remove a queen from the board?
2. How many calls to isUnderAttack are there?
3. How many recursive calls to placeQueens are there?

• (5 Points) 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.

• (10 Points) Instead of using an 8-by-8 array to represent the board in the Eight Queens program, you can use a one-dimensional array to represent only the squares that contain a queen. Let col be an array of eight integers such that
•  
•            col[k] = row index of the queen in column k + 1

For example, if col[2] = 3, then a queen is in the fourth row (square) of the third column that is, in board[3][2] . Thus, you use col[k] to represent a queen.

This scheme requires that you also store information about whether each queen is subject to attack. Because only one queen per column is permitted, you do not have to check columns. To check for a row attack, define an array rowAttack such that rowAttack[k] is nonzero if the queen in column k + 1 can be attacked by a queen in its row.

To check for diagonal attacks, observe that diagonals have either a positive slope or a negative slope. Those with a positive slope are parallel to the diagonal that runs from the lower left corner of the board to the upper right corner. Diagonals with a negative slope are parallel to the diagonal that runs from the upper left corner to the lower right corner.

Convince yourself that if board[i] [j] represents a square, then i + j is constant for squares that are in a diagonal with a positive slope, and i - j is constant for squares that are in a diagonal with a negative slope. You will find that i + j ranges from 0 to 14 and that i - j ranges from -7 to +7. Thus, define arrays posDiagonal and negDiagonal such that posDiagonal[k] is true if the queen in column k + 1 can be attacked by a queen in its positive-sloped diagonal, and negDiagonal[k] is true if the queen in column k + 1 can be attacked by a queen in its negative-sloped diagonal.

Please submit the completed assignment on Blackboard. You must submit your Java programs as a zip file of your Eclipse project.