V22.0101 ..... Homework 3 ..... Fall 2006
Chess Queens (instead of TicTacToe)
Assigned: Wed Oct 4
Due: Tue Oct 10 at midnight.
This is an exercise with 2D arrays that we will extend to
a more interesting problem later in the semester. It is based
on chess but involves only one kind of piece, a queen. We are allowed
to put a queen on the board only if it does not share the same row, the
same column, the same left diagonal, or the same right diagonal, as
another queen that is already on the board.
Write a queens class that has the following private data fields
(instance variables):
- an integer N indicating the size of the board
- a two-dimensional boolean array board
that indicates where queens have been placed on the board.
The class should have a constructor that assigns a value for N
and constructs an N by N array board, initalizing it to have all
elements set to false. Also write the following methods for the class:
- A method to display the current configuration of board in
a readable fashion, using suitable character output such as Q's and blanks,
either with System.out.println and System.out.print (which
prints a value without generating a "newline"), or, if you prefer,
suitable methods from JOptionPane.
- A method legal that has two parameters I and J
and returns a boolean value indicating whether it is legal to place a queen
in row I, column J, given the current configuration of board.
Remember that I and J range from 0 to N-1. It is legal to place
a queen in position I,J if and only if there is no queen already
in the same row, the same column, the same left diagonal, or the
same right diagonal, as indicated by the current boolean values
in board. The only thing that is tricky about this is checking
the board values while making sure that you don't evaluate the
board outside the range 0,...N-1.
- a method setQueen that has two parameters I and J
and sets the corresponding element of the array to true
(whether or not the move is legal).
The main method should prompt the user for values of N, and for
each choice, do the following
- construct an N by N queens object
- repeatedly prompt the user for integers I and J that specify
a row and column to attempt to place a queen on the board,
calling legal
to determine whether such a move is legal. If it is legal,
the main method should call setQueen to place the queen
accordingly and display the new board configuration;
otherwise, it should reject the request and ask
for another choice of I and J
- this should continue until the user gives up trying to
place a queen. The user should then be given the option of trying
a new board (with a new value of N) or quitting.
If the user chooses N to be zero or negative, the program should
reject it and insist on a positive value for N.
You can have fun seeing how many queens you can place on a board
for N = 3, 4 and 5 (the answer for N = 1 and 2 is obvious).
Later, we will find a systematic way to try to place N queens on
an N by N board, but this is possible only for certain values of N.
Don't try to do this yet.