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

const int num_queen = 8;
// set this to true if you want to print just numbers
const bool simple_printout = false;
const int UNASSIGNED = -1, NO_MORE_VAR = -1;
int total_expanded = 0;

struct State {
  int pos[num_queen]; // value stored: -1 if not assigned, 0--7 if assigned
};

// Print out the board s
void print_board(State s) {
  for (int i = 0; i < num_queen; ++i) {
    if (simple_printout)
      cout << s.pos[i] << ' ';
    else {
      for (int j = 0; j < num_queen; ++j)
	cout << (s.pos[i]==j ? 'Q' : '.');
      cout << endl;
    }
  }
  cout << endl;
}

// The trivial variable choosing function
int choose_var(const State &curr) {
  for (int i = 0; i < num_queen; ++i)
    if (curr.pos[i] == UNASSIGNED)
      return i;
  return NO_MORE_VAR;
}

// A simple goal checker
bool check_for_goal(const State &curr) {
  char found[num_queen * 2];
  // Check for clashed columns
  for (int i = 0; i < num_queen; ++i)
    found[i] = 0;
  for (int i = 0; i < num_queen; ++i) {
    int p = curr.pos[i];
    if (found[p])
      return false;
    found[p] = 1;
  }
  // Check for clashed sum-diagonal
  for (int i = 0; i < 2*num_queen; ++i)
    found[i] = 0;
  for (int i = 0; i < num_queen; ++i) {
    int p = i+curr.pos[i];
    if (found[p])
      return false;
    found[p] = 1;
  }
  // Check for clashed difference-diagonal
  for (int i = 0; i < 2*num_queen; ++i)
    found[i] = 0;
  for (int i = 0; i < num_queen; ++i) {
    int p = num_queen-i+curr.pos[i];
    if (found[p])
      return false;
    found[p] = 1;
  }
  return true;
}

// No backtracking or forward checking now, so this function just return true
// after making the needed assignment
bool put_var(State &s, int var, int value) {
  ++total_expanded;
  s.pos[var] = value;
  return true;
}

// The core depth-first-search
bool search(const State &curr, State &result) {
  int var = choose_var(curr);
  if (var == NO_MORE_VAR) { // Recursed to the bottom
    if (!check_for_goal(curr))
      return false;
    result = curr;
    return true;
  }
  State next_state = curr;
  for (int i = 0; i < num_queen; ++i) {
    if (!put_var(next_state, var, i))
      continue;
    if (search(next_state, result)) // Recurse
      return true;
  }
  return false;
}

int main() {
  State init, result;
  for (int i = 0; i < num_queen; ++i)
    init.pos[i] = UNASSIGNED;
  if (!search(init, result))
    cout << "No solution" << endl;
  else
    print_board(result);
  cout << "Expanded " << total_expanded << " states." << endl;
}