八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
C语言标准解法之一:
#include<stdlib.h>
#define n 8 //皇后数
int m=0,a[n];//m为摆法数, a[i]是存放第i个皇后的位置
int ok(int i,int j)//检测(i,j)是否能放
{
int i1=i,j1=j,ok1=1;
while ((j1>1)&&ok1)//检查第i行能否放
{
j1-;
ok1=(a[j1]!=i);
}
j1=j;
i1=i;
while ((j1>1)&&(i1>1)&&ok1)//检查对角线
{
j1-;
i1-;
ok1=(a[j1]!=i1);
}
j1=j;
i1=i;
while ((j1>1)&&(i1<n)&&ok1)//检查另一对角线
{
j1-;
i1++;
ok1=(a[j1]!=i1);
}
return ok1;
}
void queen(int j)//从第j列开始检测
{
if (j>n)
{
m++;
printf("m=%d ",m);
for (int i=1;i<=n;i++)
{
printf(" %d",a[i]);
}
printf("\n");
}
else
{
for (int i=1;i<=n;i++)
{
if (ok(i,j))
{
a[j]=i;
queen(j+1);
}
}
}
}
int main()
{
queen(1);
system("pause");
}
IOCCC的一个实现:
#define q(o) a[j]o[j+i+7]o[j-i+31]
int a[39];
void main(int i,int j)
{
for(j=9;-j;i>8?printf("%10d ",a[j]):q(|a)||(q(=a)=i,main(i+1,j),q(=a)=0));
}
