八皇后問題，是一個(gè)古老而著名的問題觉啊，是回溯算法的典型案例拣宏。該問題是國際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在8×8格的國際象棋上擺放八個(gè)皇后，使其不能互相攻擊杠人，即任意兩個(gè)皇后都不能處于同一行勋乾、同一列或同一斜線上，問有多少種擺法嗡善。 高斯認(rèn)為有76種方案辑莫。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來有人用圖論的方法解出92種結(jié)果罩引。計(jì)算機(jī)發(fā)明后各吨，有多種計(jì)算機(jī)語言可以解決此問題。
/* Code by Slyar */
#include <stdio.h>
#include <stdlib.h> //使用abs()函數(shù)
#define max 8
int queen[max], sum=0; /* max為棋盤最大坐標(biāo) */
void show() /* 輸出所有皇后的坐標(biāo) */
{
int i;
for(i = 0; i < max; i++)
{
printf("(%d,%d) ", i, queen[i]);
}
printf("\n");
sum++;
}
int check(int n) /* 檢查當(dāng)前列能否放置皇后 */
{
int i;
for(i = 0; i < n; i++) /* 檢查橫排和對(duì)角線上是否可以放置皇后 */
{
if(queen[i] == queen[n] || abs(queen[i] - queen[n]) == (n - i))
{
return 1;
}
}
return 0;
}
void put(int n) /* 回溯嘗試皇后位置,n為橫坐標(biāo) */
{
int i;
for(i = 0; i < max; i++)
{
queen[n] = i; /* 將皇后擺到當(dāng)前循環(huán)到的位置 */
if(!check(n))
{
if(n == max - 1)
{
show(); /* 如果全部擺好袁铐，則輸出所有皇后的坐標(biāo) */
}
else
{
put(n + 1); /* 否則繼續(xù)擺放下一個(gè)皇后 */
}
}
}
}
int main()
{
put(0); /* 從橫坐標(biāo)為0開始依次嘗試 */
printf("%d\n", sum);
return 0;
}
