The lab is done in pairs. Please work with a different person than your previous lab partner(s).
We will be writing a solution to the eight queens problem: position eight queens on an 8*8 chess board so that they don't attack each other. There are many different data representations for this problem. We will be using a two-dimensional array of booleans in which "true" represents a queen position.
Below is the starting code. Each group will write one of the conflict-detecting methods. One group will write the two printing methods.
Each group needs to test their code thoroughly. Create a chessboard (or two, or five) with fixed positions of the queens and pass it to your method. Submit all of your testing data with the results (commented out is OK).
Copy your code to the wikipage https://wiki.umn.edu/view/UMMCsci2101Summer10/EightQueens when done.
public class EightQueens {
/**
The program solves the eight queen problem:
position eight queens on an 8*8 chess board
so that they don't attack each other
**/
public static void main(String [] args) {
// true indicates a queen, false indicates an empty
// square. The first index is the row number, the second one
// is the column. The conflict methods assume that 0,0
// square is in the left upper corner.
boolean [][] chessboard = new boolean [8][8];
System.out.println(position(0, chessboard));
printChessboard(chessboard);
printQueensPositions(chessboard);
}
/**
Attempts to position queens in the given row and
the higher-numbered ones,
assuming that queens in all lower-numbered rows are
already positioned
**/
public static boolean position(int row, boolean [][] chessboard) {
// base case
if (row >= 8) return true;
// indicates whether a queen can be successfully positioned
boolean success = false;
// start by positioning a queen in column zero
int column = 0;
while (!success && column < 8) {
// a queen is placed here:
chessboard[row][column] = true;
// check for conflicts
if (conflicts(row, chessboard)) {
// will need to reposition; remove it from the board
chessboard[row][column] = false;
column++;
} else {
// try positioning the rest of the queens
// in higher rows
// if successful, done:
if (position(row + 1, chessboard)) {
return true;
} else {
// if cannot position queens in higher rows, move
// this one:
chessboard[row][column] = false;
column++;
}
}
}
return success;
}
/**
checking for conflicts between this row and lower-level rows
a conflict is when two queens share a column or a diagonal
**/
public static boolean conflicts(int row, boolean [][] chessboard) {
// checking for vertical conflicts
// checking for lower-left diagonal conflicts,
// including the main diagonal
// checking for lower-right diagonal conflicts,
// including the main diagonal
// checking for upper-left diagonal conflicts,
// excluding the main diagonal
// checking for upper-right diagonal conflicts,
// excluding the main diagonal
}
/**
User-friendly print of the board:
prints * for queens, _ for empty squares
**/
public static void printChessboard(boolean [][] board) {
}
/**
Given a chessboard with "true" indicating a queen and false
indicating an empty square, print out the positions
(row, column) of the queens.
**/
public static void printQueensPositions(boolean [][] board) {
}
}
Please copy your code to the Wiki when you are done. At the end of teh lab submit the java file(s) with your testing code by e-mail to me. The subject of the message must be 2101 Lab 3. Make sure to CC your group partner.