8_queen.cpp

#include <iostream>
#include <vector>

using namespace std;

typedef vector<int> vi ;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
vvvi qs;

int print_q(int t){
  cout << "[";
  for(vvvi::const_iterator x = qs.begin(); x != qs.end(); ++x){
    cout << "[\"";
    for(int i = 0; i != t; ++i){
      if(i)
        cout << "\"";
      for(int j = 0; j != t; ++j){
        if((*x)[i][j])
          cout << "Q";
        else
          cout << ".";
      }
      cout << "\",";
    }
    if(x != prev(qs.end()))
      cout << "],";
    else
      cout << "  ]";
  }
  cout << "]";
  return 0;
}

bool is_attacked(int i, int j,  int n, vvi &q){
  // cout << "\n\n ======> checking for " << i << ", " << j << "in   <=========="<< endl;
  // print_q(q, n);
  // cout << "\n\n" << endl;
  for(int x = 0; x != n; ++x){
    if(q[i][x] || q[x][j]) return true;
    for(int y = 0; y != n; ++y)
      if(((x+y) == (i+j)) || ((x-y) == (i-j))) if(q[x][y]) return true;
  }
  // cout << i << ", " << j << " is good" << endl;
  return false;
}

bool backtrack(vvi &q, int n, int c){
  if(n==c){
    qs.emplace_back(q);
    return true;
  } else {
    for(int i = 0; i != n; ++i){
      // cout << "Checking " << i << ", " << c << endl;
      if(is_attacked(i, c, n, q)){
        // cout << "Conflict found " << endl;
      } else{
        // cout << "setting " << i << ", " << c << " to 1" << endl;
        q[i][c] = 1;
        // cout << "backtracking " << n-1 << endl;
        backtrack(q, n, c+1);
        q[i][c] = 0;
      }
    }
  }
  return false;
}

int main(){
  int t;
  cin >> t;
  vvi q(t, vector<int>(t, 0));
  backtrack(q, t, 0);
  print_q(t);
  return 0;
}