queen_rec.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(int); //递归回溯法
void main(void)
{ 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(0);
     out<<"\nThe number of solution Queen is "<<sum<<endl;
     out.close();
  }   
}

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 i) //递归回溯法
{ int j;
  if(i==board_size)      //找到一组解，输出
    {  sum++;
       for(j=0; j<board_size; j++)out<<"  "<<x[j]; 
       out<<endl;  
    }
  for(j=0; j<board_size; j++)  // 从第0列起，逐列测试
     { x[i]=j;
       if(Place(i))Backtrack(i+1);  //确定皇后的位置，找下一皇后位置
     }
}