ITEC 120
HW8: Queens Puzzle (150 points)
Academic Integrity
Be reminded that this homework assignment must be your own work.
- You may not work on any homework assignment with another student.
- You may not copy material from another source.
- If you receive help from a tutor, you must include the name of the tutor in the header of your submitted code.
- For a more complete explanation of the Honor code, see the syllabus.
Objectives
After successfully completing this assignment you will be able to work with a two dimensional array.
Assignment
Back before computers existed, some mathematicians created and worked with a puzzle called the Eight Queens puzzle. In this assignment, you'll work with version of this problem.
You don't need to be a chess player to understand this problem. All you need to know is how a Queen is allowed to move on a chessboard. A Queen may move any distance in any horizontal, vertical or diagonal direction, as shown in this diagram:
The Eight Queens Puzzle is the problem of placing 8 queens on an 8x8 chessboard so that no two queens threaten each other. In other words, if a queen moved in any of her allowed directions and hit another queen, they would be threatening each other.
There are algorithms to solve the problem of actually placing eight non-attacking queens on the chessboard. These algorithms involve backtracking, which is non-trivial. This is NOT the problem you will be solving for this assignment (perhaps you'll do that in a later class).
For this project, you will model a chessboard that can be any rectangular size that may have some queens placed on it. You'll write a method that will answer if any of the queens threaten each other.
The QueensPuzzle class
Download: QueensPuzzle.java
The board
Look at the code in the QueensPuzzle class. Notice the instance data board which is a two dimensional array of boolean. A given square on the board will be true if there is a queen there, false otherwise.
Notice the constants DARK_SQUARE, LIGHT_SQUARE, and QUEEN, which are all Strings. These are to help you write the toString method. If you use these, your toString can return Strings that look like this:
Hint: make the first square, the upper left one, a DARK_SQUARE so that your toString methods will pass the tests in the test driver which will be used to grade your work.
You'll write a constructor which will create a rectangular board given the two dimensions of the board. For example, 4x7, 8x8, and 12x6 are all rectangles.
Write a getter for board.
Other methods in the class
Complete placeQueen, clearBoard, and allQueensSafe as directed in the comments in QueensPuzzle.java.
Don't change the method signatures, or your methods won't pass the tests used to grade your work. You are encouraged to add helper methods to this class.
HW8Drv.java
Write a driver to create a QueensPuzzle object and test your methods. You will submit your driver with your QueensPuzzle class.
Test your methods in whatever way makes sense to you, but do test them thoroughly because they will be thoroughly tested when they are graded.
Submit Your Assignment
Submit your QueensPuzzle.java and your HW8Drv.java to the HW8 dropbox on D2L.