1/* 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 3 * 4 * This code is free software; you can redistribute it and/or modify it 5 * under the terms of the GNU General Public License version 2 only, as 6 * published by the Free Software Foundation. 7 * 8 * This code is distributed in the hope that it will be useful, but WITHOUT 9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 10 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 11 * version 2 for more details (a copy is included in the LICENSE file that 12 * accompanied this code). 13 * 14 * You should have received a copy of the GNU General Public License version 15 * 2 along with this work; if not, write to the Free Software Foundation, 16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 17 * 18 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 19 * or visit www.oracle.com if you need additional information or have any 20 * questions. 21 */ 22 23/* 24 * This file is available under and governed by the GNU General Public 25 * License version 2 only, as published by the Free Software Foundation. 26 * However, the following notice accompanied the original version of this 27 * file: 28 * 29 * Written by Doug Lea with assistance from members of JCP JSR-166 30 * Expert Group and released to the public domain, as explained at 31 * http://creativecommons.org/publicdomain/zero/1.0/ 32 */ 33 34/* 35 * @test 36 * @bug 6865571 37 * @summary Solve NQueens using fork/join 38 * @run main NQueensCS maxBoardSize=11 reps=1 39 * @run main NQueensCS maxBoardSize=11 reps=1 procs=8 40 */ 41 42import java.util.Arrays; 43import java.util.concurrent.ForkJoinPool; 44import java.util.concurrent.RecursiveAction; 45 46public class NQueensCS extends RecursiveAction { 47 48 static long lastStealCount; 49 static int boardSize; 50 51 static final int[] expectedSolutions = new int[] { 52 0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 53 73712, 365596, 2279184, 14772512, 95815104, 666090624 54 }; // see http://www.durangobill.com/N_Queens.html 55 56 static String keywordValue(String[] args, String keyword) { 57 for (String arg : args) 58 if (arg.startsWith(keyword)) 59 return arg.substring(keyword.length() + 1); 60 return null; 61 } 62 63 static int intArg(String[] args, String keyword, int defaultValue) { 64 String val = keywordValue(args, keyword); 65 return (val == null) ? defaultValue : Integer.parseInt(val); 66 } 67 68 /** for time conversion */ 69 static final long NPS = (1000L * 1000L * 1000L); 70 71 /** 72 * Usage: NQueensCS [minBoardSize=N] [maxBoardSize=N] [procs=N] [reps=N] 73 */ 74 public static void main(String[] args) throws Exception { 75 // Board sizes too small: hard to measure well. 76 // Board sizes too large: take too long to run. 77 final int minBoardSize = intArg(args, "minBoardSize", 8); 78 final int maxBoardSize = intArg(args, "maxBoardSize", 15); 79 80 final int procs = intArg(args, "procs", 0); 81 82 for (int reps = intArg(args, "reps", 10); reps > 0; reps--) { 83 ForkJoinPool g = (procs == 0) ? 84 new ForkJoinPool() : 85 new ForkJoinPool(procs); 86 lastStealCount = g.getStealCount(); 87 for (int i = minBoardSize; i <= maxBoardSize; i++) 88 test(g, i); 89 System.out.println(g); 90 g.shutdown(); 91 } 92 } 93 94 static void test(ForkJoinPool g, int i) throws Exception { 95 boardSize = i; 96 int ps = g.getParallelism(); 97 long start = System.nanoTime(); 98 NQueensCS task = new NQueensCS(new int[0]); 99 g.invoke(task); 100 int solutions = task.solutions; 101 long time = System.nanoTime() - start; 102 double secs = (double) time / NPS; 103 if (solutions != expectedSolutions[i]) 104 throw new Error(); 105 System.out.printf("NQueensCS %3d", i); 106 System.out.printf(" Time: %7.3f", secs); 107 long sc = g.getStealCount(); 108 long ns = sc - lastStealCount; 109 lastStealCount = sc; 110 System.out.printf(" Steals/t: %5d", ns/ps); 111 System.out.println(); 112 } 113 114 // Boards are represented as arrays where each cell 115 // holds the column number of the queen in that row 116 117 final int[] sofar; 118 NQueensCS nextSubtask; // to link subtasks 119 int solutions; 120 NQueensCS(int[] a) { 121 this.sofar = a; 122 } 123 124 public final void compute() { 125 NQueensCS subtasks; 126 int bs = boardSize; 127 if (sofar.length >= bs) 128 solutions = 1; 129 else if ((subtasks = explore(sofar, bs)) != null) 130 solutions = processSubtasks(subtasks); 131 } 132 133 private static NQueensCS explore(int[] array, int bs) { 134 int row = array.length; 135 NQueensCS s = null; // subtask list 136 outer: 137 for (int q = 0; q < bs; ++q) { 138 for (int i = 0; i < row; i++) { 139 int p = array[i]; 140 if (q == p || q == p - (row - i) || q == p + (row - i)) 141 continue outer; // attacked 142 } 143 NQueensCS first = s; // lag forks to ensure 1 kept 144 if (first != null) 145 first.fork(); 146 int[] next = Arrays.copyOf(array, row+1); 147 next[row] = q; 148 NQueensCS subtask = new NQueensCS(next); 149 subtask.nextSubtask = first; 150 s = subtask; 151 } 152 return s; 153 } 154 155 private static int processSubtasks(NQueensCS s) { 156 // Always run first the task held instead of forked 157 s.compute(); 158 int ns = s.solutions; 159 s = s.nextSubtask; 160 // Then the unstolen ones 161 while (s != null && s.tryUnfork()) { 162 s.compute(); 163 ns += s.solutions; 164 s = s.nextSubtask; 165 } 166 // Then wait for the stolen ones 167 while (s != null) { 168 s.join(); 169 ns += s.solutions; 170 s = s.nextSubtask; 171 } 172 return ns; 173 } 174} 175