/*
author : BlueBlood－－六院一队吴诚堃是也，其学号：200306020093
time
*/
/*
Explanation: There are some special to be used, first we can make the diagnol to be a one dimension list.
Then Symetric is used to cut off half of the cases, so much time was saved, I tested on an 336Mhz server,
It runs out in 0.9 second.
Instead of using backtrack in common way, I used the recursion style, which makes my code to be much more acceptable.
^-^, this problem is the "Checker Challenge" of Usaco Training, I did it many days ago.
*/
#include <ctime>
#include <iostream>
using namespace std;
int nmax;
int * rowok;
int * diag1, * diag2; //with size 2*nmax - 1; diag1 from top-left to down-right
//while diag2 frome down-left to top right;
int * queen;
int * bak;
static int ncount;
static int ntmp;
void init()
{
cin >> nmax;
ncount = 0;
ntmp = 0;
rowok = new int[nmax];
queen = new int[nmax];
bak = new int[nmax];
diag1 = new int[2*nmax -1];
diag2 = new int[2*nmax -1];
int i;
for (i = 0; i < nmax; i++)
{
rowok[i] = 0;
queen[i] = -1;
}
for (i = 0; i < 2*nmax-1; i++)
diag1[i] = diag2[i] = 0;
}
void print()
{
int i;
for (i = 0; i < nmax; i++)
bak[i]= queen[i];
for (i = 0;i < nmax-1; i++)
cout << queen[i] + 1<< ' ';
cout << queen[nmax-1] + 1 << endl;
}
void placequeen(int column) { // place columns 0..nmax-1
if (column == nmax)
{
if (nmax % 2 == 1 && queen[0] == (nmax-1)/2)
ntmp++;
else
ncount++;
if ((ncount + ntmp) <= 3)
print();
return;
}
for (int row = 0; row < nmax; row++) {
if (column == 0)
{
if (row > (nmax-1) /2)
return;
}
if (!rowok[row] && !diag1[nmax-1-column+row] && !diag2[column+row] ) {
rowok[row] = 1;
diag1[nmax-1-column+row] = 1;
diag2[row+column] = 1;
//mark queen placed at column,row;
queen[column] = row;
placequeen(column+1);
//un-mark queen placed at column,row;
queen[column] = -1;
rowok[row] = 0;
diag1[nmax-1-column+row] = 0;
diag2[column+row] = 0;
}
}
}
int main()
{
init();
placequeen(0);
if (ncount == 2)
{
int i;
for (i = 0; i < nmax; i++)
queen[nmax-i-1] = bak[i];
for (i = 0; i < nmax-1; i++)
cout << queen[i] + 1 << ' ';
cout << queen[nmax-1] + 1 << endl;
}
cout << 2*ncount + ntmp<< endl;
//system("pause");
return 0;
}
