Class EightQueens

java.lang.Object

EightQueens

public class EightQueens
extends java.lang.Object

A class with two recursive methods attempting to solve the Eight Queens theoretical problem. Eight Queens is a problem posed in which eight queens must be placed on an 8x8 chess board without threatening each other. The addQueen() methods both solve this recursively. The first addQueen() that takes only an ArrayList only finds one solution for this problem. The second addQueen() that also takes two integers finds all of the possible solutions to the addQueen() problem although it does not account for rotation of the board. There is also the isValid() method, which assesses whether a Queen can be placed based off of its row and col values and the current queens already placed. This is used in both addQueen()s. Finally, this class's main method uses both addQueen() methods with the PictureYourSolution graphical interface to display all of the solutions to eight queens using graphics.

Author:

AnneMarie Caballero (annemariecabs)

Field Summary

Fields

Modifier and Type	Field	Description
private static java.util.ArrayList<java.util.ArrayList<Queen>>	allSolutions	An ArrayList of ArrayLists holding Queens that holds all of the possible solutions for the eight queens problem
private static int	PAUSE	The number of milliseconds the program will pause in between each solution.

Constructor Summary

Constructors

Constructor	Description
EightQueens()

Method Summary

Modifier and Type	Method	Description
static boolean	addQueen(int row, int col, java.util.ArrayList<Queen> currentBoard)	This is an expanded version of the other addQueen method in this class.
static boolean	addQueen(java.util.ArrayList<Queen> currentQueens)	Recursively finds a solution to the eight queens thought problem.
static boolean	isValid(int row, int col, java.util.ArrayList<Queen> currentQueens)	Checks the validity of a spot on the board.
static void	main(java.lang.String[] args)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

allSolutions

private static java.util.ArrayList<java.util.ArrayList<Queen>> allSolutions

An ArrayList of ArrayLists holding Queens that holds all of the possible solutions for the eight queens problem

PAUSE

private static final int PAUSE

The number of milliseconds the program will pause in between each solution.

See Also:

Constant Field Values

Constructor Detail

EightQueens

public EightQueens()

Method Detail

addQueen

public static boolean addQueen(java.util.ArrayList<Queen> currentQueens)

Recursively finds a solution to the eight queens thought problem. If currentQueens is equal to eight, returns true because Queens are only placed if they're valid. If not equal to eight, then the program will pick the next row and run through all of the possible columns. If any of the columns are valid spots, then a Queen will be added and the method will call itself for this new array. If that is unsuccessful, it will return false at that level, that queen will be removed, and the next possibility will be tried. NOTE: This method only finds one solution to the eight queens problem.

Parameters:

currentQueens - the Queens that have already been placed

Returns:

true if a solution has been found, false otherwise

addQueen

public static boolean addQueen(int row,
                               int col,
                               java.util.ArrayList<Queen> currentBoard)

This is an expanded version of the other addQueen method in this class. This method actually does find all possible solutions to the eight queens problem. Instead of exiting once one solution (a filled 8 queen array) is found, instead it recurses again. The parameters have been altered so that a spot to start at can be passed in so that progress won't be lost. The successful board has its last item removed from it and then is re-passed to the array to start the process

Parameters:

row - the row to start looking at

col - the column to start looking at

currentBoard - the queens currently placed

Returns:

true, once all 92 solutions have been found, false otherwise NOTE: this will return true at lower levels of the loops just when a solution is found but the whole method will only return true once all 92 solutions to this issue have been found.

isValid

public static boolean isValid(int row,
                              int col,
                              java.util.ArrayList<Queen> currentQueens)

Checks the validity of a spot on the board. If the queen to be placed at that row and column is in the same row, column or diagonal as another queen, then the method will return false because that new position is not valid

Parameters:

row - the row of the spot to be checked

col - the column of the spot to be checked

currentQueens - an ArrayList containing the already-placed Queens

Returns:

true, if a Queen can be placed in this spot without threatening other already-placed Queens, false otherwise

main

public static void main(java.lang.String[] args)
                 throws java.lang.InterruptedException

Throws:

java.lang.InterruptedException