Question

八皇后递归

八皇后递归
问题描述:
在8×8的国际象棋棋盘上放置8个皇后,然后要求没有皇后能吃掉另一个皇后.即是任意两个皇后都不处于棋盘的同一行,同一列或同一对角线上.

我们规定:棋盘中的i表示行,j表示列.[i,j]表示i行j列..[i,j]是否安全,则要对上睡觉上对角线和下对角线分别进行编号;由于上对角线和下对角线i+j是一个常量,所以用i-j和i+j分别作为上对角线和下对角线的编号.

设a[j]表i列无皇后,b[j]和c[j]分别表示i个上对角线和j个下对角线上无皇后.这样,方格[i,j]是否安全意味着
a[j]&&b[i-j+7]&&c[i+j]
是不是为turn;
而将皇后放置与方格[i,j]或者从方格[i,j]移去皇后就应使a[j], b[i-j], c[i+j]这三个不尔变量同时为false或同时为ture.
此外,设整型数组x[ ]表示八皇后所占方格位置.而x[i]的值表示第i行中皇后所占的列编号.如x[2]=6表示第2行中的皇后位于第6列.
#include<stdio.h>
#include<conio.h>
int a[8],b[15],c[15],x[8];
int sum=0;
main()
{

int k;
for(k=0;k<=7;k++)
a[k]=1;
for(k=0;k<=14;k++)
b[k]=c[k]=1;

clrscr();
try();

printf("sum=%d",sum);
}

void print()
{
int i;
for(i=0;i<=7;i++)
printf("(%d,%d)",i,x[i]);
printf("\n");
sum++;
}

try(int i)
{
int j;
for(j=0;j<=7;j++)
if( a[j]&&b[i-j+7]&&c[i+j])
{
x[i]=j;
a[j]=0;
b[i-j+7]=0;
c[i+j]=0;
if(i<7)
try(i+i);
else
print();
a[j]=1;
b[i-j+7]=1;
c[i+j]=1;
}
}

我把主函数的中的try()括号 中不填数字和填不同数字时 结果是不同 比如 0 或 1 等 但结果都是错误的
为什么??在线等!!!
try(i+i);
else
改成
try(i+1);
else
为什么不顺我的原意，帮我找问题呢？
我用的是tc
你用的是c++吧
我没学c++

Answer 1

1、
#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 ;
}
2、
下面给出完整解法,此代码本人议编译过,没有问题(在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;

}