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