#include<iostream>
#include<stdio.h>
#include <sys/time.h>
#include <cmath>
#include "omp.h"
using namespace std;
//Размерность доски NхN (Количество ферзей - N)
   const int N=12;  int X[N];  int Count;

  bool P(int X[N],int k,int y){  // Поиск позиции для ферзя
	int i=0;
	while ((i<k)&&(y!=X[i])&&(abs(k-i)!=abs(y-X[i]))) {i++;}
	if(i==k)
	return true;
	else return false;  
	}

  void Backtracking(int k){ // Поиск с возвратом позиций
		int i,y;
		for (y=0;y<N;y++)
		if (P(X,k,y)){ 
				X[k]=y;
				if (k==N-1){
					Count++; 
				}
			Backtracking(k+1); 		
		} 
	}	
	
 int main(){ 
	double iv;
	struct timeval st, et;
	gettimeofday(&st, NULL); 
	Count=0;
	cout<<"Doska "<<N<<" na "<<N<<endl;
	omp_set_num_threads(1);
	
	Backtracking(0);
	
   	gettimeofday(&et, NULL);
    iv = (et.tv_sec * 1.0e6 + et.tv_usec) - (st.tv_sec * 1.0e6 + st.tv_usec);
	cout<<"Vsego "<<Count<<" rasstanovok";
   	cout<<"Time: "<< iv / 1e6 <<"sec." << endl;
   }