// -----------------------------------------------------------------
// queens.cpp - Solving the 'n' queens problem
//
// This program is a generalization of the classic computer
// science problem:
//
//    How many ways can 8 queens be arranged on a chess board
//    such that no queen can capture any of the others?
//
// Here is an example of a solution to the 8 queens problem
//
//    [ ][ ][ ][ ][Q][ ][ ][ ]
//    [ ][ ][ ][ ][ ][ ][Q][ ]
//    [ ][Q][ ][ ][ ][ ][ ][ ]
//    [ ][ ][ ][ ][ ][Q][ ][ ]
//    [ ][ ][Q][ ][ ][ ][ ][ ]
//    [Q][ ][ ][ ][ ][ ][ ][ ]
//    [ ][ ][ ][Q][ ][ ][ ][ ]
//    [ ][ ][ ][ ][ ][ ][ ][Q]
//
// Note that no row or column contains more than one queen
// and that there are no diagonal collisions either.
//
// The "no row or column contains more than one queen" gives a
// hint as to how to attack this problem.  Consider a row
// of cells containing the numbers from 1 -> 8.
//
//              [3][6][4][2][8][5][7][1]
// cell number:  1  2  3  4  5  6  7  8
//
// Treating the cell number as the column and the contained
// value as the row, we can see that the above cells correspond
// the the 8 queens solution shown above.
//
// Note that the row of cells is simply a permutation of
// the numbers from 1 -> 8.  Given that no two queens
// can share a row or a column, the set of all permutations
// of the numbers from 1 -> 8 represent a set of possible
// solutions to the 8 queens puzzle.
//
// Of course, we'll have to ensure that each permutation
// does not produce diagonal queen collisions but we've
// now reduced this problem from a truly staggering number
// of possible solutions:
//
//    (64 * 63 * 62 * 61 * 60 * 59 * 58 * 57)
//    --------------------------------------- => 4,426,165,368
//           (8 * 7 * 6 * 5 * 4 * 3 * 2)
//
// To a far more manageable number:
//
//    8! => (8 * 7 * 6 * 5 * 4 * 3 * 2) => 40,320
//
// So, instead of investigating more than 4 billion possible
// solutions, we've reduced that number down by more than 100,000
// times to a more manageable 40,320.
//
// For each candidate solution, to check the diagonals
// we start with an empty chess board:
//
//    [ ][ ][ ][ ][ ][ ][ ][ ]
//    [ ][ ][ ][ ][ ][ ][ ][ ]
//    [ ][ ][ ][ ][ ][ ][ ][ ]
//    [ ][ ][ ][ ][ ][ ][ ][ ]
//    [ ][ ][ ][ ][ ][ ][ ][ ]
//    [ ][ ][ ][ ][ ][ ][ ][ ]
//    [ ][ ][ ][ ][ ][ ][ ][ ]
//    [ ][ ][ ][ ][ ][ ][ ][ ]
//
// And as we examine the position of each queen we "mark off"
// all the diagonals representing spaces she could capture.
// Using our earlier solution, going position-by-position
// where 'x' represents a capturable position ...
//
//    [ ][ ][ ][ ][ ][x][ ][ ]
//    [ ][ ][ ][ ][x][ ][ ][ ]
//    [ ][ ][ ][x][ ][ ][ ][ ]
//    [ ][ ][x][ ][ ][ ][ ][ ]
//    [ ][x][ ][ ][ ][ ][ ][ ]
//    [Q][ ][ ][ ][ ][ ][ ][ ]
//    [ ][x][ ][ ][ ][ ][ ][ ]
//    [ ][ ][x][ ][ ][ ][ ][ ]
//
//    [ ][ ][ ][x][ ][x][ ][ ]
//    [x][ ][x][ ][x][ ][ ][ ]
//    [ ][Q][ ][x][ ][ ][ ][ ]
//    [x][ ][x][ ][ ][ ][ ][ ]
//    [ ][x][ ][x][ ][ ][ ][ ]
//    [Q][ ][ ][ ][x][ ][ ][ ]
//    [ ][x][ ][ ][ ][x][ ][ ]
//    [ ][ ][x][ ][ ][ ][x][ ]
//
// and so on through all 8 positions.  Because no queen's
// position lands on an 'x', we've found a solution.
//
// To compile this program:
//
//    unix:
//       g++ -W -Wall -o queens queens.cpp
//
//    win32:
//       cl -W3 -GX queens.cpp
//
// Running the program without arguments presents solutions
// to the 8 queens problem, if run with a positive integer
// argument 'N' then solutions to the 'N' queens problem
// are presented.
// -----------------------------------------------------------------

/*****************************************************************
 * C/C++ Headers
 *****************************************************************/

#include <vector>
#include <string>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>

/*****************************************************************
 * Local Defines
 *****************************************************************/

#define SIZE(x) (sizeof(x) / sizeof(x[0]))

/*****************************************************************
 * Using Declarations
 *****************************************************************/

using std::vector;
using std::string;
using std::cout;
using std::endl;

/*****************************************************************
 * Declaration Of Class: Permutation
 *****************************************************************/

class Permutation
{
   public:
      Permutation(vector<int> items);
      int getTotalPermutations();
      vector<int> next();
      static vector<int> fromArray(int *items, int nItems);
      static string toString(vector<int> items);
      static void test(int *items, int nItems);
      static void doTest();

   private:
      vector<int> mItems;
      int         mTotalPermutations;
      vector<int> mFactorial;
      int         mCurrent;
};

/*****************************************************************
 * Definition Of Class: Permutation
 *****************************************************************/

Permutation::Permutation(vector<int> items) :
   mItems(items),
   mCurrent(0)
{
   mFactorial.push_back(0);
   mFactorial.push_back(1);

   int value = 1;
   int n     = mItems.size();

   for(int i = 2; i < n; i ++)
   {
      value *= i;
      mFactorial.push_back(value);
   }

   mTotalPermutations = value * n;
}

int Permutation::getTotalPermutations()
{
   return(mTotalPermutations);
}

vector<int> Permutation::next()
{
   if(mCurrent > 0)
   {
      int value = 1;
      int n     = mFactorial.size();

      while(mCurrent % mFactorial[value] == 0)
         if(++value == n)
            break;

      for(int i = 0, j = value - 1; i < j; i ++, j --)
      {
         int tmp   = mItems[i];
         mItems[i] = mItems[j];
         mItems[j] = tmp;
      }
   }

   if(++mCurrent == mTotalPermutations)
      mCurrent = 0;

   return(mItems);
}

vector<int> Permutation::fromArray(int *items, int nItems)
{
   vector<int> vItems;

   for(int i = 0; i < nItems; i ++)
      vItems.push_back(items[i]);

   return(vItems);
}

string Permutation::toString(vector<int> items)
{
   string theString = "";
   char buffer[255] = { '\0' };

   for(int n = items.size(), i = 0; i < n; i ++)
   {
      sprintf(buffer, "%s%d", i == 0 ? "" : ", ", items[i]);
      theString += buffer;
   }

   return(theString);
}

void Permutation::test(int *items, int nItems)
{
   Permutation p(Permutation::fromArray(items, nItems));

   for(int n = p.getTotalPermutations(), i = 0; i < n; i ++)
      cout << Permutation::toString(p.next()) << endl;
}

void Permutation::doTest()
{
   int values[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
   Permutation::test(values, SIZE(values));
}

/*****************************************************************
 * Declaration Of Class: DiagonalFlags
 *****************************************************************/

class DiagonalFlags
{
   public:
      DiagonalFlags(int nQueens);
      ~DiagonalFlags();
      void reset();
      int collisionFound(int row, int column);

   private:
      int mNQueens;
      int **mFlags;
};

DiagonalFlags::DiagonalFlags(int nQueens) :
   mNQueens(nQueens)
{
   mFlags = new int *[mNQueens];

   for(int i = 0; i < mNQueens; i ++)
      mFlags[i] = new int[mNQueens];

   reset();
}

DiagonalFlags::~DiagonalFlags()
{
   for(int i = 0; i < mNQueens; i ++)
   {
      delete [] mFlags[i];
      mFlags[i] = NULL;
   }

   delete [] mFlags;
   mFlags = NULL;
}

void DiagonalFlags::reset()
{
   for(int i = 0; i < mNQueens; i ++)
      for(int j = 0; j < mNQueens; j ++)
         mFlags[i][j] = 0;
}

int DiagonalFlags::collisionFound(int row, int column)
{
   if(mFlags[row][column])
      return(1);

   int steps[][2] = {
      {  1,  1 },
      {  1, -1 },
      { -1, -1 },
      { -1,  1 }
   };

   int nSteps = SIZE(steps);

   for(int i = 0; i < nSteps; i ++)
   {
      int r = row;
      int c = column;

      while(r >= 0 && c >= 0 && r < mNQueens && c < mNQueens)
      {
         mFlags[r][c] = 1;

         r += steps[i][0];
         c += steps[i][1];
      }
   }

   return(0);
}

/*****************************************************************
 * main
 *****************************************************************/

int main(int argc, char **argv)
{
   int nQueens = 8;

   if(argc > 1)
   {
      char *pEnd     = NULL;
      long int value = strtol(argv[1], &pEnd, 10);

      if(*pEnd != '\0' || value <= 0L)
      {
         cout << "Usage: " << argv[0] << " positiveInteger" << endl;
         return(1);
      }

      nQueens = (int)value;
   }

   vector<int> items;
   int i = 0;

   for(i = 0; i < nQueens; i ++)
      items.push_back(i);

   Permutation p(items);
   DiagonalFlags flags(nQueens);

   int nPermutations  = p.getTotalPermutations();
   int solutionNumber = 1;

   for(i = 0; i < nPermutations; i ++)
   {
      vector<int> current = p.next();
      int isSolution      = 1;
      int j               = 0;

      flags.reset();

      for(j = 0; isSolution && j < nQueens; j ++)
      {
         if(flags.collisionFound(j, current[j]))
            isSolution = 0;
      }

      if(isSolution)
      {
         cout << "Solution Number: " << solutionNumber << endl;
         solutionNumber++;

         for(j = 0; j < nQueens; j ++)
         {
            for(int k = 0; k < nQueens; k ++)
               cout << "[" << (k == current[j] ? "Q" : " ") << "]";

            cout << endl;
         }

         cout << endl;
      }
   }

   return(0);
}