// ConsoleApplication2.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

//#include "pch.h"
#include <iostream>
#include <fstream>
#include <string>
#include <stdlib.h> 

using namespace std;

int numberOfQueens;
int howMany = 0;

ofstream g("damesah.out");

bool valid(int vecSolutie[],int numberPartial) {
	for (int i = 1; i < numberPartial; i++) {
		if(vecSolutie[i]==vecSolutie[numberPartial] || abs(i-numberPartial) == abs(vecSolutie[i]-vecSolutie[numberPartial]))
			return false;
	}
	return true;
}

void bkt(int array[], int dim) {
	if (dim == numberOfQueens && howMany==0 ) {
		for (int i = 1; i <= numberOfQueens; i++)
			g << array[i]<<' ';
		g << '\n';
		howMany++;
	}
	else if (dim == numberOfQueens) {
		howMany++;
	}
	else {
		dim++;
		for (int i = 1; i <= numberOfQueens; i++)
		{
			array[dim] = i;
			if (valid(array, dim)) {
				bkt(array, dim );
			}
		}
	}

}


int main()
{

	ifstream f("damesah.in");
	string line;
	while (getline(f, line)) {
		numberOfQueens = stoi(line, nullptr, 10);
	}
	
	int v[25];
	
	bkt(v, 0);

	g << howMany;




}