KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > NQueens


1 // Adapted from a cilk demo
2
3 import EDU.oswego.cs.dl.util.concurrent.*;
4
5 class NQueens extends FJTask {
6
7   static int boardSize;
8
9   public static void main(String JavaDoc[] args) {
10     try {
11       int procs;
12       try {
13         procs = Integer.parseInt(args[0]);
14         boardSize = Integer.parseInt(args[1]);
15       }
16       catch (Exception JavaDoc e) {
17         System.out.println("Usage: java NQueens <threads> <boardSize>");
18         return;
19       }
20
21       if (boardSize <= 3) {
22         System.out.println("There is no solution for board size <= 3");
23         return;
24       }
25
26                            
27       FJTaskRunnerGroup g = new FJTaskRunnerGroup(procs);
28       NQueens f = new NQueens(new int[0]);
29       g.execute(f);
30
31       int[] board = result.await();
32
33       g.stats();
34
35       System.out.print("Result:");
36
37       for (int i = 0; i < board.length; ++i) {
38         System.out.print(" " + board[i]);
39       }
40       System.out.println();
41
42     }
43     catch (InterruptedException JavaDoc ex) {}
44   }
45
46   /**
47    * Global variable holding the result of search.
48    * FJTasks check this to see if it is nonnull,
49    * if so, returning early because a result has been found.
50    * In a more serious program, we might use a fancier scheme
51    * to reduce read/write pressure on this variable.
52    **/
53
54   static final class Result {
55     private int[] board = null;
56
57     synchronized int[] get() { return board; }
58
59     synchronized void set(int[] b) {
60       if (board == null) { board = b; notifyAll(); }
61     }
62
63     synchronized int[] await() throws InterruptedException JavaDoc {
64       while (board == null) { wait(); }
65       return board;
66     }
67   }
68
69   static final Result result = new Result();
70
71   // Boards are represented as arrays where each cell
72 // holds the column number of the queen in that row
73
74   final int[] sofar;
75   NQueens(int[] a) { this.sofar = a; }
76
77   public void run() {
78     if (result.get() == null) { // check if already solved
79 int row = sofar.length;
80
81       if (row >= boardSize) // done
82 result.set(sofar);
83       else {
84         for (int q = 0; q < boardSize; ++q) {
85           
86           // Check if can place queen in column q of next row
87 boolean attacked = false;
88           for (int i = 0; i < row; i++) {
89             int p = sofar[i];
90             if (q == p || q == p - (row - i) || q == p + (row - i)) {
91               attacked = true;
92               break;
93             }
94           }
95           
96           // Fork to explore moves from new configuration
97 if (!attacked) {
98             int[] next = new int[row+1];
99             for (int k = 0; k < row; ++k) next[k] = sofar[k];
100             next[row] = q;
101             new NQueens(next).fork();
102           }
103         }
104       }
105     }
106   }
107
108 }
109
Popular Tags