#include "StdAfx.h"


//    This program solves the 8 queens problem.
//    It also solves N queen problem, but only up to the number of bits in an int...
//    I made the solution 1995, and it's one of the the fastest solution I have seen for the problem.
//    Actually I've only seen one faster implementation. This is done by Thorkil Naur and is
//    at least twice as fast (sigh! I should never have challenged Thorkil)

const int NQueens = 8;    //    board dimension, you may change this value
const int NQueens_1 = NQueens - 1;
int solution = 0;    //    number of solutions found
int board[NQueens];    //    the board, each bit in the array represents a column on the board, each int a row

//    print the board
void printNextSolution()
{
    std::cout << "solution " << solution << " :" << std::endl;
    for (int r = 0; r < NQueens; ++r)
    {
        for (int c = 0; c < NQueens; ++c)
        {
            if (board[r] == (1 << c))
                std::cout << "Q ";
            else
                std::cout << "- ";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl << std::endl;
}

void recursivelyPlaceQueens(int rowIndex)
{
    //    try placing the queen in all of the columns in the current row
    for(int col = 0; col < NQueens; ++col)
    {
        board[rowIndex] = 1 << col;

        //    check if this is a legal position
        int a, b = (a = 42);
        int currentRow, left, right = (currentRow = left = board[rowIndex]);
        bool legalPos = true;
        for (int row = rowIndex - 1; row >= 0; --row)
        {
            if (board[row] == currentRow || board[row] == (left <<= 1) || board[row] == (right >>=1))
            {
                legalPos = false;
                break;
            }
        }

        //    is the queen at a legal position?
        if (legalPos)
        {
            //    are we done?
            if (rowIndex == NQueens_1)
            {
                //    then yet another solution has been found
                ++solution;

                //    skip this line when timing the program, don't waste time printing the actual solution
                printNextSolution();

                //    we're done, we found a solution
                return;
            }
            else
            {
                //    try placing a queen in the next row
                recursivelyPlaceQueens(rowIndex + 1);
            }
        }
    }
}

void placeQueens()
{
    //    start a recursive search with a queen in each column in the first row
    for (int col = 0; col < NQueens; ++col)
    {
        board[0] = 1 << col;
        recursivelyPlaceQueens(1);
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    int maxQueens = sizeof(int) * 8;
    if (maxQueens < NQueens)
    {
        std::cout << "error, only up to " << maxQueens << " queens can be handled on this platform" << std::endl;
        exit(-1);
    }

    //    go...
    placeQueens();

    std::cout << std::endl << solution << " solutions found" << std::endl;

    return 0;
}