全彩无修本子fgo:8皇后问题的最优解法是什么?
来源:百度文库 编辑:高校问答 时间:2024/05/08 11:39:16
有图论或构造的方法吗?
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ofstream fout ("checker.out");
long sum = 0, upperlim = 1;
void test(long row, long ld, long rd)
{
if (row != upperlim)
{
long pos = upperlim & ~(row | ld | rd);
for ( ; pos ; )
{
long p = pos & -pos;
pos -= p;
test(row + p, (ld + p) << 1, (rd + p) >> 1);
}
}
else sum++;
}
int main(){
int n ;
cin >> n ;
upperlim = (upperlim << n) - 1;
test(0, 0, 0);
cout << sum << endl ;
}
是"回溯法"!!
下面给出完整解法,此代码本人议编译过,没有问题(在visual stdio.net 2003下用c++实现)请仔细看,毕竟打一边不容易,呵呵
// 国际象棋八皇后问题--回溯法之经典.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <math.h>
#include <iostream>
using namespace std;
int total=0;
int _tmain(int argc, _TCHAR* argv[])
{
int queen[8];
int i,j,k;
for(i=0;i<8;i++)queen[i]=0;
for(i=1;;){
if(queen[i]<8){
k=0;
while(k<i&&(queen[k]-queen[i])&&(abs(queen[k]-queen[i])-abs(k-i)))k++;//逐项检查
if(k<=i-1){
queen[i]++;
continue;
} //有问题改变i位置的queen[i]
i++; //无问题继续下一行
if(i<8)continue; //循环条件!
for(j=0;j<8;j++)cout<<queen[j];
cout<<" ";
total++; //此三行是输出
if(total%6==0)cout<<endl;
queen[7]++;
i=7;
}
else //即i>=8时
{
queen[i]=0;
i--;
if(i<0){
cout<<"总数: "<<total<<endl;
cin.get();
cin.get();
return 0;
}
else queen[i]++;
}
}
cin.get();
cin.get();
return 0;
}