queen.c

一个简单的递归实现八皇后算法

//八皇后问题
//编写：杨家宁

//--------------------------------------------------------------------------------

//问题简介

#ifndef boolean
enum boolean {false,true};
#ifndef word
typedef unsigned int word;
#include<stdio.h>
boolean Col[8],LeftCr[14],RightCr[14];
word Answer[8],Count=0;

/*Col{行标志定义}
Answer{列标志定义}
LeftCr{左斜对角线标志定义}
RightCr{右斜对角线标志定义}
{Count:解的个数纪录}
*/
//-------------------------判断一个位置是否可以置一个皇后-----------------------
boolean IfSafe(word x,word y)
{
   return ((Col[y]==true)
       || (LeftCr[x-y+7]==true)
       || (RightCr[x+y]==true))?false:true;
}
//-----------------------------从当前位置删除一个皇后--------------------------
void CutQueen(word x,word y)
{
  Col[y]=false;
  LeftCr[x-y+7]=false;
  RightCr[x+y]=false;
}

//---------------------------------打印一组解----------------------------------
void PrintAnswer()
{
 int CurAns;
 printf("\nCOUNT[%4d]    ",++Count);
 for (CurAns=0;CurAns<8;CurAns++)
   printf("%4d",Answer[CurAns]+1);
}
//---------------------------------置皇后(核心部分)----------------------------
void PutQueen(word x)
{
 word y;
 for (y=0;y<8;y++)
 {
   if (IfSafe(x,y))
   {
    Answer[x]=y;
    Col[y]=true;
    LeftCr[x-y+7]=true;
    RightCr[x+y]=true;
    if (x<7) PutQueen(x+1);
    else PrintAnswer();
    CutQueen(x,y);
   }
  }
}

//--------------------主程序体--------------------------------------------
int main()
{
for (int i=0;i<8;i++)
  Answer[i]=0;
PutQueen(0);
return 0;
}