N_Queen.rar_N_queen_N皇后问题_queen

/* 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; }