C++实现 八皇后问题及其扩展N皇后问题(经典回溯算法)

C++实现 八皇后问题及其扩展N皇后问题(经典回溯算法)

转载请注明出处:http://hi.baidu.com/ipress/

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名
的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即
任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。       

高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后
来有人用图论的方法解出92种结果。事实上就是有92种解法。

了解了基本的原理后,我们开始分析:

1.我们需要一个数据存放已经放置皇后的位置,用指针表示的一维数据*position,长度为N(N为放置的皇后总数),可能有人会问为什么不用二维数组,用下票i,j准备定位,事实是这样的,因为该问题是每行,每列,每组对角线只可能出现一个皇后,所以用一维数据position+i中的i则能代码第几行,而值*(position+i)则表示该行中的列值,其实质与二维数组无异.

2.判断每行可放置皇后,假设要判断第n行,则从position中从0到n-1每一个已放皇后的位置判断(列,对角线)

具体算法如下:

// 转载请注明出处 http://hi.baidu.com/ipress/

#include <iostream>
#include <math.h>
#include <malloc.h>

using namespace std;

int *position; //放置的位置
int queen; //皇后数目
int count; //第N种可能性

//判断第n行是否放置皇后
bool SignPoint(int n)
{
for (int i=0;i<n;i++)
{
   if (*(position+i) == *(position+n)) //该列已经放置过皇后了
    return false;
   if (abs(*(position+i) - *(position+n)) == n-i) //对角线已经放置过了
    return false;
}
return true;
}

//设置皇后
void SetQueen(int n=0)
{
if (queen==n)
{
   //该处可以改成自己想要的显示方式
   printf("NO.%d: ",++count);
   printf("\n");
   for (int i=0;i<queen;i++)
   {
    for (int j=0;j<queen;j++)
    {
     if (j == position[i])
     {
      printf("* ");
     }
     else
     {
      printf("0 ");
     }
    }
    printf("\n");
   }
   printf("\n");
   return;
}
else
{
   for (int i=0;i<queen;i++)
   {
    position[n] = i;

    if(SignPoint(n))//如果该位置放置皇后正确的话,则到下一行
    {
     SetQueen(n+1);
    }
   }
}
}

int main(int argc, char argv[])
{
cout<<"请输入皇后的总数:"<<endl;
cin>>queen;
position = (int*)malloc(sizeof(int));
SetQueen();
cout<<"摆放完毕"<<endl;
cin.get();
cin.get();
return 0;
}