1 import java.util.Arrays;
2
3 /**
4 A partial solution to the eight queens puzzle.
5 */
6 public class PartialSolution
7 {
8 private Queen[] queens;
9 private static final int NQUEENS = 8;
10
11 public static final int ACCEPT = 1;
12 public static final int ABANDON = 2;
13 public static final int CONTINUE = 3;
14
15 /**
16 Constructs a partial solution of a given size.
17 @param size the size
18 */
19 public PartialSolution(int size)
20 {
21 queens = new Queen[size];
22 }
23
24 /**
25 Examines a partial solution.
26 @return one of ACCEPT, ABANDON, CONTINUE
27 */
28 public int examine()
29 {
30 for (int i = 0; i < queens.length; i++)
31 {
32 for (int j = i + 1; j < queens.length; j++)
33 {
34 if (queens[i].attacks(queens[j])) { return ABANDON; }
35 }
36 }
37 if (queens.length == NQUEENS) { return ACCEPT; }
38 else { return CONTINUE; }
39 }
40
41 /**
42 Yields all extensions of this partial solution.
43 @return an array of partial solutions that extend this solution.
44 */
45 public PartialSolution[] extend()
46 {
47 // Generate a new solution for each column
48 PartialSolution[] result = new PartialSolution[NQUEENS];
49 for (int i = 0; i < result.length; i++)
50 {
51 int size = queens.length;
52
53 // The new solution has one more row than this one
54 result[i] = new PartialSolution(size + 1);
55
56 // Copy this solution into the new one
57 for (int j = 0; j < size; j++)
58 {
59 result[i].queens[j] = queens[j];
60 }
61
62 // Append the new queen into the ith column
63 result[i].queens[size] = new Queen(size, i);
64 }
65 return result;
66 }
67
68 public String toString() { return Arrays.toString(queens); }
69 }
70