<![CDATA[
CSE143 Sample Program handout #22
Sample Executions of Queens.java
--------------------------------
This program solves the classic '8 queens'
problem, placing queens on a chessboard so
that no two queens threaten each other.
What size board do you want to use? 8
One solution is as follows:
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - Q - - - - -
----------------------------------------------------------------------
This program solves the classic '8 queens'
problem, placing queens on a chessboard so
that no two queens threaten each other.
What size board do you want to use? 2
No solution.
----------------------------------------------------------------------
This program solves the classic '8 queens'
problem, placing queens on a chessboard so
that no two queens threaten each other.
What size board do you want to use? 4
One solution is as follows:
- - Q -
Q - - -
- - - Q
- Q - -
----------------------------------------------------------------------
Program File Board.java
-----------------------
// Stuart Reges
// 12/7/98
//
// Class Board stores information relevant to solving the n queens problem
// of placing n queens on an n-by-y board. It has the following public
// methods:
// public Board(int size)
// construct an empty board of given size
// public boolean safe(int row, int col)
// is it safe to place a queen at [row, col]?
// public void place(int row, int col)
// place queen at [row, col]
// public void remove(int row, int col)
// remove queen previously placed at [row, col]
// public int size()
// returns size of board
// public void print()
// display board to System.out
public class Board {
private int[] board; // stores board info
private static final int UNASSIGNED = 100; // unassigned column
// pre : size >= 0
// post: constructs a board of the given size
public Board(int size) {
if (size < 0)
throw new IllegalArgumentException();
board = new int[size];
for (int i = 0; i < size; i++)
board[i] = UNASSIGNED;
}
// pre : 1 <= row, col <= size
// post: returns true iff it is safe to place a Queen at [row, col]
public boolean safe(int row, int col) {
// first reset row and col to array range (0..size-1)
row--;
col--;
// next check that row, col are in bounds
if (!legal(row, col))
throw new IllegalArgumentException();
// next check that the current column is empty
if (board[col] != UNASSIGNED)
return false;
// now check for conflicts with other columns
for (int currCol = 0; currCol < board.length; currCol++) {
int distance = col - currCol;
// check for diagonal conflict
if (board[currCol] == row - distance)
return false;
// check for conflict in this row
if (board[currCol] == row)
return false;
// check for other diagonal conflict
if (board[currCol] == row + distance)
return false;
}
return true;
}
// pre : safe(row, col)
// post: places a queen at [row, col]
public void place(int row, int col) {
if (!safe(row, col))
throw new IllegalArgumentException();
board[col - 1] = row - 1;
}
// pre : a queen has been placed at [row, col]
// post: removes the queen at [row, col]
public void remove(int row, int col) {
if (!legal(row - 1, col - 1) || board[col - 1] != row - 1)
throw new IllegalArgumentException();
board[col - 1] = UNASSIGNED;
}
// post: return size of board
public int size() {
return board.length;
}
// post: displays current board to System.out
public void print() {
for (int row = 0; row < board.length; row++) {
for (int col = 0; col < board.length; col++)
if (board[col] == row)
System.out.print(" Q ");
else
System.out.print(" - ");
System.out.println();
}
}
// post: returns true iff row and col are legal for this board
private boolean legal(int row, int col) {
return row >= 0 && row < board.length && col >= 0 && col < board.length;
}
}
Program file Queens.java
------------------------
// Stuart Reges
// 12/7/98
//
// This program solves the classic "8 queens" problem using recursive
// backtracking.
import java.util.*;
public class Queens {
public static void main(String[] args) {
giveIntro();
Scanner console = new Scanner(System.in);
System.out.print("What size board do you want to use? ");
int size = console.nextInt();
System.out.println();
Board b = new Board(size);
solve(b);
}
// post: explains program to user
public static void giveIntro() {
System.out.println("This program solves the classic '8 queens'");
System.out.println("problem, placing queens on a chessboard so");
System.out.println("that no two queens threaten each other.");
System.out.println();
}
// pre : queens have been safely placed in columns 1 through (col - 1)
// post: recursively searchs the board for a solution starting at col,
// returning true iff such a solution occurs and storing the
// solution in board if it exists
public static boolean explore(Board b, int col) {
if (col > b.size())
return true;
else {
for (int row = 1; row <= b.size(); row++)
if (b.safe(row, col)) {
b.place(row, col);
if (explore(b, col + 1))
return true;
b.remove(row, col);
}
return false;
}
}
// post: searches for a solution to the 8 queens problem with this
// board, reporting result
public static void solve(Board solution) {
if (!explore(solution, 1))
System.out.println("No solution.");
else {
System.out.println("One solution is as follows:");
solution.print();
}
}
}
]]>