PartialSolution.java.html

  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