Your browser does not support JavaScript and this site utilizes JavaScript to build content and provide links to additional information. You should either enable JavaScript in your browser settings or use a browser that supports JavaScript in order to take full advantage of this site.
1 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 [] args) { 10 try { 11 int procs; 12 try { 13 procs = Integer.parseInt(args[0]); 14 boardSize = Integer.parseInt(args[1]); 15 } 16 catch (Exception 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 ex) {} 44 } 45 46 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 { 64 while (board == null) { wait(); } 65 return board; 66 } 67 } 68 69 static final Result result = new Result(); 70 71 74 final int[] sofar; 75 NQueens(int[] a) { this.sofar = a; } 76 77 public void run() { 78 if (result.get() == null) { int row = sofar.length; 80 81 if (row >= boardSize) result.set(sofar); 83 else { 84 for (int q = 0; q < boardSize; ++q) { 85 86 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 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
|