nqueens_annotated

//=======================================================================
//
// SAMPLE SOURCE CODE - SUBJECT TO THE TERMS OF END-USER LICENSE AGREEMENT FOR
// INTEL(R) PARALLEL ADVISOR 2011.
//
// Copyright 2009-2010 Intel Corporation
//
// THIS FILE IS PROVIDED "AS IS" WITH NO WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT
// NOT LIMITED TO ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
// PURPOSE, NON-INFRINGEMENT OF INTELLECTUAL PROPERTY RIGHTS.
//
// ========================================================================

// [DESCRIPTION]
// Solve the nqueens problem  - how many positions of queens can fit on a chess board
// of a given size without attacking each other.
// This is the serial version used to find a candidate hotspot function to parallelize.
//
// [BUILD]
// Use a Release configuration to ensure you find a hotspot representative of a final production build.
//
// [RUN]
// To set the board size in Visual Studio, right click on the project,
// select Properies > Configuration Properties > General > Debugging.  Set
// Command Arguments to the desired value.  13 has been set as the default.
//
// [EXPECTED OUTPUT]
//
// Board Size   Number of Solutions
//     4                2
//     5               10
//     6                4
//     7               40
//     8               92
//     9              352
//    10              724
//    11             2680
//    12            14200
//    13            73712
//    14           365596
//    15          2279184

#include <iostream>
#include <windows.h>
#include <mmsystem.h>

#include <advisor-annotate.h>

using namespace std;

int nrOfSolutions=0;  //keeps track of the number of solutions
int size=0;  // the board-size read from command-line
int correctSolution[16]; //array of the number of correct solutions for each board size

/*
Recursive function to find all solutions on a board
represented by the argument "queens", placing the next queen
at location (row, col)

On Return: nrOfSolutions has been increased to add solutions for this board

*/
void setQueen(int queens[], int row, int col) {
    //check all previously placed rows for attacks

    //ADVISOR COMMENT: The accesses to the "queens" array in this function create an incidental sharing correctness issue
    //ADVISOR COMMENT: Each task should have its own copy of the "queens" array
    //ADVISOR COMMENT: Look at the solve() function to see how to fix this issue
    for(int i=0; i<row; i++) {
        // vertical attacks
        if (queens[i]==col) {
            return;
        }
        // diagonal attacks
        if (abs(queens[i]-col) == (row-i) ) {
            return;
        }
    }
    // column is ok, set the queen
    //ADVISOR COMMENT: See comment at top of function
    queens[row]=col;

    if(row==size-1) {


        //ADVISOR COMMENT: Uncomment the following two annotations to lock the access to nrOfSolutions and fix the race condition

        //ANNOTATE_LOCK_ACQUIRE(0);
        //ADVISOR COMMENT: This is a race condition because multiple tasks may try and increment the variable at the same time
        nrOfSolutions++;  //Placed final queen, found a solution!
        //ANNOTATE_LOCK_RELEASE(0);
    }
    else {
        // try to fill next row
        for(int i=0; i<size; i++) {
            setQueen(queens, row+1, i);
        }
    }
}


/*
Function to find all solutions for nQueens problem on size x size chessboard.

On Return: nrOfSoultions = number of solutions for size x size chessboard.
*/
void solve() {

    //ADVISOR COMMENT: Remove the following declaration of the queens array and uncomment the declaration just before the call to setQueen
    //ADVISOR COMMENT: This privatizes the queens array to each task and eliminates the incidental sharing
    int * queens = new int[size]; //array representing queens placed on a chess board.  Index is row position, value is column

    ANNOTATE_SITE_BEGIN(solve);
        for(int i=0; i<size; i++) {
            // try all positions in first row
            // create separate array for each recursion
            ANNOTATE_TASK_BEGIN(setQueen);
                //int * queens = new int[size]; //array representing queens placed on a chess board.  Index is row position, value is column
                //ADVISOR COMMENT: This is incidental sharing because all the tasks are using the same copy of "queens"
                setQueen(queens, 0, i);
            ANNOTATE_TASK_END(setQueen);
        }
    ANNOTATE_SITE_END(solve);
}

int main(int argc, char*argv[]) {
    if(argc !=2) {
        cerr << "Usage: nqueens_annotated boardSize [default is 13].\n";
        size = 13;
    } else {
        size = atoi(argv[1]);
        if (size < 4 || size > 15) {
            cerr << "Boardsize should be between 4 and 15; setting it to 13. \n" << endl;
            size = 13;
        }
    }
    // Set the expected number of solutions for each board-size for later checking.
    correctSolution[0] = 0;
    correctSolution[1] = 0;
    correctSolution[2] = 0;
    correctSolution[3] = 0;
    correctSolution[4] = 2;
    correctSolution[5] = 10;
    correctSolution[6] = 4;
    correctSolution[7] = 40;
    correctSolution[8] = 92;
    correctSolution[9] = 352;
    correctSolution[10] = 724;
    correctSolution[11] = 2680;
    correctSolution[12] = 14200;
    correctSolution[13] = 73712;
    correctSolution[14] = 365596;
    correctSolution[15] = 2279184;

    cout << "Starting nqueens (2_nqueens_annotated) solver for size " << size << "...\n";
    DWORD startTime=timeGetTime();
    solve();
    DWORD endTime=timeGetTime();
    cout << "Number of solutions: " << nrOfSolutions << endl;
    if (nrOfSolutions != correctSolution[size])
        cout << "!!Incorrect result!! Number of solutions should be " << correctSolution[size] << endl << endl;
    else
        cout << "Correct result!" << endl;

    cout << endl << "Calculations took " << endTime-startTime << "ms.\n";

    return 0;
}