八皇後問題求解

/************************************************************************/
　　/* */
　　/* 問題： 在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;
　　
　　printf( "No.%-5d " , ++iCount);
　　
　　for(i = 0 ; i < QUEENS ; i++)
　　printf( "%d " , Site[i]);
　　
　　printf( " ");
　　}