queen_iter.cpp

这是本人精心搜集的关于常用图论算法的一套源码

#include <math.h>
#include <fstream.h>
# define max_board 30
int sum=0;            // 计数所得解数目
int x[max_board];     // 存放当前解的向量
int board_size;       // 皇后个数
ofstream out("Queen.out");
void Backtrack();
void main()
{ cout << "What is the size of the board? ";
  cin >> board_size;
  if(board_size<0 || board_size>max_board)
     cout<<"The number must be between 0 and "<<max_board<<endl;
  else Backtrack();
}

bool Place(int k) // 检测k皇后能否放在x[k]列(是否与以前的皇后能相互攻击)
{ for(int j=0; j<k; j++)
     if((abs(k-j)==abs(x[j]-x[k])) || x[j]==x[k]) return false;
 return true; 
}
void Backtrack()   //迭代回溯
{ int k=0, sum=0; x[0]= -1;
  while (k >=0 )   //  若k<0，则已搜索完所有的解, 结束回溯
   { x[k]++;
     while((x[k]<board_size) && !(Place(k))) x[k]++;  //为k皇后找安全的位置
     if(x[k]<board_size)   // 确定了皇后的位置 
       if(k==board_size-1)     //找到一组解，输出
	 {  sum++;
	    for(int i=0; i<board_size; i++)out<<"  "<<x[i]; 
            out<<endl;  
         }
       else  x[++k]=-1;  // k增1，为下一皇后找安全的位置
     else k--;          // 回溯
   }
  out<<"\nThe number of solution Queen is "<<sum<<endl;
  out.close(); 
}