// ----------------------
// Includes
// ----------------------

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>

// ----------------------
// Using Statements
// ----------------------

using std::vector;
using std::string;

// ----------------------
// Constants
// ----------------------

static const int DEFAULT_N_QUEENS = 8;

// ----------------------
// Board
// ----------------------

class Board
{
   public:

      Board(int n) : mN(n), mBoard(n, vector<bool>(n, false))
      {
      }

      bool place(int row, int column)
      {
         if(row < 0 || row >= mN || column < 0 || column >= mN || mBoard[row][column])
            return(false);

         // Trace the diagonals, if we hit another occupied location this isn't a valid solution

         for(int i = 0; i < 4; i ++)
         {
            int rowStep = (i > 1 ? -1 : 1);
            int colStep = (i % 2 ? -1 : 1);

            int r = row    + rowStep;
            int c = column + colStep;

            while(r >= 0 && c >= 0 && r < mN && c < mN)
            {
               if(mBoard[r][c])
                  return(false);

                r += rowStep;
                c += colStep;
            }
         }

         mBoard[row][column] = true;

         return(true);
      }

      void dump() const
      {
         for(auto row : mBoard)
         {
            for(auto c : row)
               std::cout << "[" << (c ? "Q" : " ") << "]";

            std::cout << "\n";
         }
      }

   private:

      int mN;
      vector<vector<bool>> mBoard;
};

// ----------------------
// main
// ----------------------

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

   if(argc > 1)
   {
      int value = atoi(argv[1]);

      if(value > 0)
         nQueens = value;
   }

   vector<int> theVector;
   
   for(int i = 0; i < nQueens; i ++)
      theVector.push_back(i);

   int count = 0;

   do
   {
      // Each entry in our vector is a column - the number in that entry is the row,
      // try to place each queen until we fail or place all queens

      Board theBoard(nQueens);

      bool placedAll = true;

      for(int i = 0; placedAll && i < nQueens; i ++)
         if(!theBoard.place(theVector[i], i))
            placedAll = false;

      if(placedAll)
      {
         std::cout << "---------------------------\n";
         std::cout << "Solution: " << ++count << "\n";
         std::cout << "---------------------------\n\n";

         theBoard.dump();

         std::cout << "\n";
      }

   } while(next_permutation(theVector.begin(), theVector.end()));
}