//
// Name: Sean Bachelder
// Email: bachelde@usc.edu
// Date: 2/4/07
//

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <list>

using namespace std;

const int max_size = 10;

struct Board 
{
  bool board[max_size][max_size];

  Board()
  {
    for (int i = 0; i < max_size; i++) {
      for (int j = 0; j < max_size; j++) {
	board[i][j] = false;
      }
    }
  }
};

struct Node
{
  Board b;
  
  list<Node *> subtree;
};

void initialize_board(struct Board &b);
bool check_piece(bool board[][max_size], int size, int i, int j);
bool valid_board(bool board[][max_size], int size);
void create_tree(Node &root, int size);
void add_piece(Node &n, int column, int size);
void print_board(Node &n, int size);
void output_results(Node &root, int size, ofstream &output);
int find_solutions(Node &n, int size, int count, ofstream &output);

// i know global variables are bad practice, but i was having trouble
// getting the counting to work correctly while traversing the tree
int solutions = 0;

int main(int argc, char *argv[])
{
  /*
   * check parameters to make sure they are valid
   */
  if ( argc < 3 ) {
    cout << "\nUsage: " << argv[0] << " n output.txt" << endl;
    cout << "  - n is an integer between 1 and " << max_size << endl;
    cout << "  - output.txt is the file where the output will be stored\n" << endl;
    return 0;
  }
  
  int size = atoi(argv[1]);
  if (size < 1 || size > max_size) {
    cout << "The size of the board must be between 1 and " << max_size << "." << endl;
    return 0;
  }

  ofstream output(argv[2]);
  if (!output) {
    cout << "Cannot open the specified file. Please use a different filename." << endl;
    return 0;
  }
  /* 
   * done checking parameters
   */

  Node root;
  
  create_tree(root, size);
  
  output_results(root, size, output);

  output.close();
      
  return 0;
}


//
// outputs the results to a file
//
// Node &root - root of the results tree
//
// int size - size of the board
//
// ofstream output - file to send results to
//
void output_results(Node &root, int size, ofstream &output)
{
  int total;
  
  output << "Number of queens: " << size << endl;

  total = find_solutions(root, size, 0, output);
  
  if (total == 0){
    output << "No solutions" << endl;
  }
  
  output << "Total number of solutions: " << total << endl;
}


//
// traverses tree and outputs solutions into specified file
//

int find_solutions(Node &n, int size, int count, ofstream &output)
{
  int c = 0;
  // has a leaf node been reached?
  if (count == size) {
    solutions++;
    output << "Solution " << solutions << ": ";
    for (int i = 0; i < size; i++) {
      for (int j = 0; j < size; j++) {
	if (n.b.board[i][j] == true) {
	  output << "(" << i+1 << "," << j+1 << ") ";
	}
      }
    }
    output << endl;
    return 1;
  }
  else {
    for (list<Node *>::const_iterator it = n.subtree.begin();
	 it != n.subtree.end();
	 ++it) {

      c += find_solutions(**it, size, count + 1, output);
    }

    return c;
  }
}


//
// creates the tree, starting at the root node (which
// contains an empty board), that holds all of the possible
// positions of queens on the chess board of the indicated
// size
//
// Node &root - reference to the root of the tree
// 
// int size - size of the board
//
// returns nothing
//
void create_tree(Node &root, int size)
{
  add_piece(root,0,size);
}


//
// adds a piece to each row of the indicated column and
// calls itself again to add another piece to the next column
// until it reaches the indicated size
//
// Node &n - reference to a node in the tree
//
// int column - the current column that queens are being added to
//
// int size - the size of the board
//
// returns nothing
//
void add_piece(Node &n, int column, int size)
{
  // end condition for the recursive call. if column is the same
  // as size, that means that all columns have been filled with
  // queens
  if (column == size) {
    //print_board(n,size);
    return;
  }
  
  for (int i = 0; i < size; i++) {
    Node *node = new Node();
    // need to first copy previous board to new board
    for (int j = 0; j < size; j++) {
      for (int k = 0; k < column; k++) {
	node->b.board[j][k] = n.b.board[j][k];
      }
    }
    node->b.board[i][column] = true;
    
    // check to see if the piece that was just added is valid or not
    if (check_piece(node->b.board,size,i,column) == true) {
      
      // add the node to the subtree and continue on to the next column
      n.subtree.push_back(node);
      add_piece(*node, column+1, size);
    }
    else {
      delete node;
    }
  }
}


//
// checks to see if the board is valid in it's current state.
// it is valid if the queens on the board cannot attack each
// other
//
// bool **board - the chess board (2d array). true indicates
//    the position of a queen
//
// int size - the size of the board
//
// returns true if board is valid, false otherwise
//
bool valid_board(bool board[][max_size], int size)
{
  // loop through the board
  for (int i = 0; i < size; i++) {
    for (int j = 0; j < size; j++) {
      if (board[i][j] == true) {
	if (check_piece(board,size,i,j) == false) 
	{
	  return false;
	}
      }
    }
  }
  return true;
}


//
// checks to see if the indicated piece is capable of attacking
// any other piece on the board
//
// bool **board - representation of the chess board
//
// int size - the size of the board
//
// int i - the row in which the queen is located
// 
// int j - the column in which the queen is located
//
// returns true if the piece isn't attacking other queens,
// false otherwise.
//
bool check_piece(bool board[][max_size], int size, int i, int j)
{
  for (int k = 0; k < size; k++) {
    // check for other queens in row
    if (board[i][k] == true && k != j) {
      return false;
    }
    // check for other queens in column
    if (board[k][j] == true && k != i) {
      return false;
    }
    
  }

  int newi, newj;
  
  // check for other queens on diagonal
  for (int k = 1; k < size; k++) {
    // check queens to the top left
    newi = i - k;
    newj = j - k;
    if ( newi >= 0 && newj >= 0) {
      if (board[newi][newj] == true) {
	return false;
      }
    }
    
    // check queens to the top right
    newi = i - k;
    newj = j + k;
    if (newi >= 0 && newj < size) {
      if (board[newi][newj] == true) {
	return false;
      }
    }
    
    // check queens to the bottom right
    newi = i + k;
    newj = j + k;
    if (newi < size && newj < size) {
      if (board[newi][newj] == true) {
	return false;
      }
    }
    
    // check queens to the bottom left
    newi = i + k;
    newj = j - k;
    if (newi < size && newj >= 0) {
      if (board[newi][newj] == true) {
	return false;
      }
    }
  }
  
  return true;
}


//
// DEBUG FUNCTIONS
//

void print_board(Node &n, int size)
{
  for (int i = 0; i < size; i++) {
    for (int j = 0; j < size; j++) {
      if (n.b.board[i][j] == true) {
	cout << "Q ";
      }
      else {
	cout << "X ";
      }
    }
    cout << endl;
  }
  cout << endl;
}