/*

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

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

 * have any questions.

 */

/*

 * This file is available under and governed by the GNU General Public

 * License version 2 only, as published by the Free Software Foundation.

 * However, the following notice accompanied the original version of this

 * file:

 *

 * Written by Doug Lea with assistance from members of JCP JSR-166

 * Expert Group and released to the public domain, as explained at

 * http://creativecommons.org/licenses/publicdomain

 */

/*

 * @test

 * @bug 6865571

 * @summary Solve NQueens using fork/join

 * @run main NQueensCS maxBoardSize=11 reps=1

 * @run main NQueensCS maxBoardSize=11 reps=1 procs=8

 */

import java.util.Arrays;

import java.util.concurrent.ForkJoinPool;

import java.util.concurrent.RecursiveAction;

public class NQueensCS extends RecursiveAction {

    static long lastStealCount;

    static int boardSize;

    static final int[] expectedSolutions = new int[] {

        0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200,

        73712, 365596, 2279184, 14772512, 95815104, 666090624

    }; // see http://www.durangobill.com/N_Queens.html

    static String keywordValue(String[] args, String keyword) {

        for (String arg : args)

            if (arg.startsWith(keyword))

                return arg.substring(keyword.length() + 1);

        return null;

    }

    static int intArg(String[] args, String keyword, int defaultValue) {

        String val = keywordValue(args, keyword);

        return (val == null) ? defaultValue : Integer.parseInt(val);

    }

    /** for time conversion */

    static final long NPS = (1000L * 1000L * 1000L);

    /**

     * Usage: NQueensCS [minBoardSize=N] [maxBoardSize=N] [procs=N] [reps=N]

     */

    public static void main(String[] args) throws Exception {

        // Board sizes too small: hard to measure well.

        // Board sizes too large: take too long to run.

        final int minBoardSize = intArg(args, "minBoardSize",  8);

        final int maxBoardSize = intArg(args, "maxBoardSize", 15);

        final int procs = intArg(args, "procs", 0);

        for (int reps = intArg(args, "reps", 10); reps > 0; reps--) {

            ForkJoinPool g = (procs == 0) ?

                new ForkJoinPool() :

                new ForkJoinPool(procs);

            lastStealCount = g.getStealCount();

            for (int i = minBoardSize; i <= maxBoardSize; i++)

                test(g, i);

            System.out.println(g);

            g.shutdown();

        }

    }

    static void test(ForkJoinPool g, int i) throws Exception {

        boardSize = i;

        int ps = g.getParallelism();

        long start = System.nanoTime();

        NQueensCS task = new NQueensCS(new int[0]);

        g.invoke(task);

        int solutions = task.solutions;

        long time = System.nanoTime() - start;

        double secs = (double) time / NPS;

        if (solutions != expectedSolutions[i])

            throw new Error();

        System.out.printf("NQueensCS %3d", i);

        System.out.printf(" Time: %7.3f", secs);

        long sc = g.getStealCount();

        long ns = sc - lastStealCount;

        lastStealCount = sc;

        System.out.printf(" Steals/t: %5d", ns/ps);

        System.out.println();

    }

    // Boards are represented as arrays where each cell

    // holds the column number of the queen in that row

    final int[] sofar;

    NQueensCS nextSubtask; // to link subtasks

    int solutions;

    NQueensCS(int[] a) {

        this.sofar = a;

    }

    public final void compute() {

        NQueensCS subtasks;

        int bs = boardSize;

        if (sofar.length >= bs)

            solutions = 1;

        else if ((subtasks = explore(sofar, bs)) != null)

            solutions = processSubtasks(subtasks);

    }

    private static NQueensCS explore(int[] array, int bs) {

        int row = array.length;

        NQueensCS s = null; // subtask list

        outer:

        for (int q = 0; q < bs; ++q) {

            for (int i = 0; i < row; i++) {

                int p = array[i];

                if (q == p || q == p - (row - i) || q == p + (row - i))

                    continue outer; // attacked

            }

            NQueensCS first = s; // lag forks to ensure 1 kept

            if (first != null)

                first.fork();

            int[] next = Arrays.copyOf(array, row+1);

            next[row] = q;

            NQueensCS subtask = new NQueensCS(next);

            subtask.nextSubtask = first;

            s = subtask;

        }

        return s;

    }

    private static int processSubtasks(NQueensCS s) {

        // Always run first the task held instead of forked

        s.compute();

        int ns = s.solutions;

        s = s.nextSubtask;

        // Then the unstolen ones

        while (s != null && s.tryUnfork()) {

            s.compute();

            ns += s.solutions;

            s = s.nextSubtask;

        }

        // Then wait for the stolen ones

        while (s != null) {

            s.join();

            ns += s.solutions;

            s = s.nextSubtask;

        }

        return ns;

    }

}