#include <iostream>
#include<ctime>
using namespace std;

void drawboard(int size, int sol);
void AddQueen(int size, int row, int boards, int sol);

int size;
int col[];	                // column with the queen
bool colfree[16];            // is the column free?  
bool upfree[16];            //is the upward diagonal free?
bool downfree[16];       	//is the downward diagonal free?


int main()  //starts main
{

 
int row = -1;	//row whose queen is currently placed
int boards = 0;		//number of positions investigated
int sol = 0;	//number of solutions found

	cout<<"What size board do you want?";
	cin>>size;
  int i;

  for (i = 0; i < size; i++) colfree[i] = true;

  for (i = 0; i < size; i++) {
    upfree[i] = true;
    downfree[i] = true;
  }

  AddQueen(size, row, boards, sol);

				//add function to print board and count # of times ran

  return 0;
}

					//AddQueen: attempt to place a queen
void AddQueen(int size, int row, int boards, int sol)
{					//AddQueen
  int c;		//column being tried for the queen
  float randnum;  //random number for placing if queen
  randnum=rand()%11;
  boards++;
  row++;
  for (c = 0; c < 8; c++)
    if (colfree[c] && upfree[row+c] && downfree[row-c+7]) {
      col[row] = c;	//put a queen in (row,c)
      colfree[c] = false;
      upfree[row+c] = false;
      downfree[row-c+7] = false;
      if (row == 7)		//end condition
        drawboard(size, sol);
      else
        AddQueen(size, row, sol, boards);		
      colfree[c] = true;	//now backtrack by removing the queen
      upfree[row+c] = true;
      downfree[row-c+7] = true;
    }
  row--;
}

//drawboard: print a solution
void drawboard(int size, int sol) 
{
    int i, j;
    sol++;
    cout << "board ran" << sol << " times" <<endl;
    cout << "-----------------" << endl;
    for (i = 0; i < 8; i++) {//for
        for (j = 0; j < col[i]; j++)
            cout << " -";
        cout << " Q";
        for (j++; j < 8; j++)
            cout << " -";
        cout << endl;
    }
    cout << "-----------------" << endl;
}

void drawboard(int size, int sol);
void AddQueen(int size, int row, int boards, int sol);

int size;
int col[];	                // column with the queen
bool colfree[16];            // is the column free?  
bool upfree[16];            //is the upward diagonal free?
bool downfree[16];