/*
 * nqueens.hj was ported from the BOTS nqueens.c benchmark.  See below for provenance.
 *
 * @author Jun Shirako, Rice University
 * @author Vivek Sarkar, Rice University
 * 
 * This program computes all solutions to the n-queens problem where n is specified in argv[0] (default = 12),
 * and repeats the computation "repeat" times where "repeat" is specifies in argv[1] (default = ).
 * There is a cutoff value specified as an optional third parameter in argv[1] (default = 3)
 * that is used in the async seq clause to specify when a new async should be created.
 *
 * The program uses the count of the total number of solutions as a correctness check and also prints the execution time for each repetition.
 *
 * Note the use of single "finish" statement in find_queens() that awaits termination of all
 * async's created by the recursive calls to nqueens_kernel.
 * 
 * This program is a good example to illustrate the performance benefits of work-stealing vs. work-sharing schedulers.
 * Try "hjc nqueens.hj" to create a work-sharing implementation (default) and "hjc -rt w nqueens.hj" to create a work-stealing
 * implementation, and compare their performance by executing "hj nqueens 12 5 3" to solve a 12-queens problem with 5 repetitions and a cutoff at depth 3.
 * To study scalability on a multicore processor, you can execute "hj -places 1:<w> nqueens 12 5 3", where <w> is the number of worker threads.
 * Since "12 5 3" are default values, you can obtain the same measurements by executing "hj nqueens" and "hj -places 1:<w> nqueens"
 */

/**********************************************************************************************/
/*  This program is part of the Barcelona OpenMP Tasks Suite                                  */
/*  Copyright (C) 2009 Barcelona Supercomputing Center - Centro Nacional de Supercomputacion  */
/*  Copyright (C) 2009 Universitat Politecnica de Catalunya                                   */
/*                                                                                            */
/*  This program is free software; you can redistribute it and/or modify                      */
/*  it under the terms of the GNU General Public License as published by                      */
/*  the Free Software Foundation; either version 2 of the License, or                         */
/*  (at your option) any later version.                                                       */
/*                                                                                            */
/*  This program 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 for more details.                                              */
/*                                                                                            */
/*  You should have received a copy of the GNU General Public License                         */
/*  along with this program; if not, write to the Free Software                               */
/*  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA            */
/**********************************************************************************************/

/*
 * Original code from the Cilk project (by Keith Randall)
 * 
 * Copyright (c) 2000 Massachusetts Institute of Technology
 * Copyright (c) 2000 Matteo Frigo
 */


public class nqueens {
    // STATIC FIELDS
    static final int [] solutions = {
        1,
        0,
        0,
        2,
        10, /* 5 */
        4,
        40,
        92,
        352,
        724, /* 10 */
        2680,
        14200,
        73712,
        365596,
    };
    static final int MAX_SOLUTIONS =  14;

    private static int size; // Problem size
    private static int cutoff_value; // Used to specify cutoff threshold in async seq clause

    // NON-STATIC FIELDS
    private int total_count;

    // STATIC METHODS
    public static void main(String[] args) {
        size = (args.length > 0) ? Integer.parseInt(args[0]) : 12; // Default value = 12
        int repeat = (args.length > 1) ? Integer.parseInt(args[1]) : 5; // Default value = 5
        cutoff_value = (args.length > 2) ? Integer.parseInt(args[2]) : 3; // Default value = 3

        if (size < 1) {
            size =  1;
            System.out.println("Size was modified to 1");
        } else if (size > MAX_SOLUTIONS) {
            size = MAX_SOLUTIONS;
            System.out.println("Size was modified to " + MAX_SOLUTIONS);
        }

        for (int i = 0; i < repeat; i++) {
            nqueens q = new nqueens();

            // Timing for parallel run
            long s = System.currentTimeMillis();
            q.find_queens();
            long e = System.currentTimeMillis();
            System.out.println("Time: " + (e-s) + " [ms]");

            q.verify_queens();
        }
    }

    // NON-STATIC METHODS
    void find_queens () {
        final accumulator ac = accumulator.factory.accumulator(accumulator.Operator.SUM, int.class);

        finish (ac) {
            int [] a = new int [0];
            nqueens_kernel(a, 0, ac);
        }

        total_count = ac.get().intValue();
    }

    void nqueens_kernel(int [] a, int depth, accumulator ac) {

        if (size == depth) {
            ac.put(1);
            return;
        }

        /* try each possible position for queen <depth> */
        for (int i =  0; i < size; i++) {
            async seq(depth >= cutoff_value) {
                /* allocate a temporary array and copy <a> into it */
                int [] b = new int [depth+1];
                System.arraycopy(a, 0, b, 0, depth);
                b[depth] = i;
                if (ok( (depth +  1), b))
                    nqueens_kernel(b, depth+1, ac);
            }
        }
    }

    /*
     * <a> contains array of <n> queen positions.  Returns 1
     * if none of the queens conflict, and returns 0 otherwise.
     */
    boolean ok( int n,  int [] a) {
        int i, j;
        int p, q;

        for (i =  0; i < n; i++) {
            p = a[i];

            for (j =  (i +  1); j < n; j++) {
                q = a[j];
                if (q == p || q == p - (j - i) || q == p + (j - i))
                    return false;
            }
        }

        return true;
    }

    void verify_queens() {
        if ( total_count == solutions[size-1] )
            System.out.println("OK");
        else
            System.out.println("Incorrect answer");
    }
}