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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

    19  * CA 95054 USA or visit www.sun.com if you need additional information or

    20  * have any 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/licenses/publicdomain

    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 

    42 import java.util.Arrays;

    43 import java.util.concurrent.ForkJoinPool;

    44 import java.util.concurrent.RecursiveAction;

    45 

    46 public 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 }