八皇后問題求解

2019-11-17 05:38:34

字體：大中小

來源：轉載

供稿：網友

/************************************************************************/
/* */
/* 問題：在8×8的國際象棋棋盤上放置8個皇后，要求任意兩個皇后 */
/* 不能在同一行、同一列或同一條對角線上。 */
/* */
/* 本程序使用遞歸－回溯法求解8皇后問題。Visual C++ 6.0 調試通過。 */
/* 作者晨星 2002年5月9日 */
/* */
/************************************************************************/

#include <stdio.h >
#include <conio.h >
#include <math.h >

#define QUEENS 8

int iCount = 0;

int Site[QUEENS];

void Queen(int n);

void Output();

int IsValid(int n);

/*----------------------------Main：主函數。----------------------------*/
void main()
{
Queen(0);

getch();
}

/*-----------------Queen：遞歸放置第n個皇后，程序的核心!----------------*/
void Queen(int n)
{
int i;

if(n == QUEENS)
{
Output();
return;
}

for(i = 1 ; i <= QUEENS ; i++)
{
Site[n] = i;

if(IsValid(n))
Queen(n + 1);
}
}

/*------IsValid：判定第n個皇后放上去之后，是否合法，即是否無沖突。------*/
int IsValid(int n)
{
int i;

for(i = 0 ; i < n ; i++)
{
if(Site[i] == Site[n])
return 0;

if(abs(Site[i] - Site[n]) == (n - i))
return 0;
}

return 1;
}

/*------------Output：輸出一個解，即一種沒有沖突的放置方案。------------*/
void Output()
{
int i;

for(i = 0 ; i < QUEENS ; i++)
printf( "%d " , Site[i]);

printf( "/n ");
}