n_queen.cpp

N皇后问题的优化版本

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