DEVELOPING EFFICIENT ALGORITHMS - Introduction to Java Programming: Comprehensive Version - page 847

To see how the algorithm works, go to www.cs.armstrong.edu/liang/animation/
EightQueensAnimation.html .
Listing 22.11 gives the program that displays a solution for the Eight Queens problem.

L ISTING 22.11

EightQueens.java
1 import javafx.application.Application;
2 import javafx.geometry.Pos;
3 import javafx.stage.Stage;
4 import javafx.scene.Scene;
5 import javafx.scene.control.Label;
6 import javafx.scene.image.Image;
7 import javafx.scene.image.ImageView;
8 import javafx.scene.layout.GridPane;
9
10 public class EightQueens extends Application {
11 public static final int SIZE = 8 ; // The size of the chess board

12 // queens are placed at (i, queens[i])

13 // -1 indicates that no queen is currently placed in the ith row

14 // Initially, place a queen at (0, 0) in the 0th row

15 private int [] queens = { -1 , -1 , -1 , -1 , -1 , -1 , -1 , -1 };

queen positions

16
17 @Override // Override the start method in the Application class
18 public void start(Stage primaryStage) {

19 search(); // Search for a solution search for solution

20
21 // Display chess board
22 GridPane chessBoard = new GridPane();
23 chessBoard.setAlignment(Pos.CENTER);
24 Label[][] labels = new Label[SIZE][SIZE];
25 for ( int i = 0 ; i < SIZE; i++)
26 for ( int j = 0 ; j < SIZE; j++) {
27 chessBoard.add(labels[i][j] = new Label(), j, i);
28 labels[i][j].setStyle( "-fx-border-color: black" );
29 labels[i][j].setPrefSize( 55 , 55 );
30 }
31
32 // Display queens
33 Image image = new Image( "image/queen.jpg" );
34 for ( int i = 0 ; i < SIZE; i++)
35 labels[i][queens[i]].setGraphic( new ImageView(image));
36
37 // Create a scene and place it in the stage
38 Scene scene = new Scene(chessBoard, 55 * SIZE, 55 * SIZE);
39 primaryStage.setTitle( "EightQueens" ); // Set the stage title
40 primaryStage.setScene(scene); // Place the scene in the stage
41 primaryStage.show(); // Display the stage
42 }
43
44 /** Search for a solution */
45 private boolean search() {
46 // k - 1 indicates the number of queens placed so far
47 // We are looking for a position in the kth row to place a queen
48 int k = 0 ;
49 while (k >= 0 && k < SIZE) {
50 // Find a position to place a queen in the kth row
51 int j = findPosition(k);
52 if (j < 0 ) {
53 queens[k] = -1 ;
54 k--; // back track to the previous row
55 } else {

create cells

set queen image

find a column

backtrack