text1.cpp

N皇后问题的回溯算法

#include <iostream>
using namespace std;
int x[20]; 
int COUNT = 0;

bool place(int k)
   {  int i;   
       i = 1;   
   while (i<k)  
   {     
	   if (x[i] == x[k] || (abs(x[i] - x[k]) == abs(i-k)))     
		   return false;    
	   i = i + 1;  
   }    
   return true;
   }

   void queen(int N)
   {    int k;   
   int n = N;   
   x[1] = 0;    
   k = 1;  
   while (k>0)   
   {        
	   x[k] = x[k] + 1;    
	   while (x[k] <= n && place(k) == false)    
		   x[k] = x[k] + 1;
        if (x[k] <= n)      
			if (k == n)    
			{                
				for(int i = 1; i <= n; i++)  
				{     cout<<x[i]<<" ";    }
                cout<<endl;    
	             return ;        
	             COUNT++;          
             }        
			else    
			{         
				k = k + 1;         
				x[k] = 0;            
			}      
			else          
				k = k - 1;    
   }
}
   int main()
   { int n ;
   cin>> n ;
   queen(n); 
   return 0 ;}