CSci 2101 Lab 3. Eight Queens.

Due at the end of the lab (upload to the Wiki page)

25 points

The lab is done in pairs. Please work with a different person than your previous lab partner(s).

Eight Queens problem: recursive solution

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) {

    }

}

How to submit

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.


CSci 2101 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.