【C】八皇后问题

问题描述

---

把8个皇后放在8*8的棋盘上，它们中的任何一个都无法攻击其它皇后，攻击规则：同一行，同一列，对角线

 

算法

---

回溯法

把一个皇后放在第一列的位置1

如果合法，继续在第二列放第二个皇后，否则就尝试位置2，以此类推

直至所有的皇后都放在棋盘上

 

程序

---

zz：

 

int result = 1;//记录第几个解

 

int main()

{

    printf("the following are the solutions:\n");

    putchess(1);//初始化，放在第一列的位置1

}

 

putchess(int n)

{

    int i;

    if(n<=8)

    {

      for(i=1;i<=8;i++) //遍历每一列的所有位置

      {

        chess[n]=i; //标示位置

        if(check(n)==1) //检查此位置是否合法

        {

           if(n==8)

              showchess(); //棋子放置完毕，打印结果

           else

               putchess(n+1); //放置下一个棋子

        }

       //尝试下一个位置

      }

     }

 }

 

//检查位置n是否符合攻击规则，不符合返回1

int check(int n)

{

    int i;

    for(i=1;i<=n-1;i++)

    {

       int i1 = (chess[n]==chess[i]); //同一行

       int i2 = (chess[n]==chess[i]+n-i); //对角线

       int i3 = (chess[n]==chess[i]-n-i); //对角线

       if(i1 || i2 || i3)

           return 0;

    }

    return 1;

}

 

showchess()

{

    printf("the %d result is :\n",result);

    int i;

    for(i=1;i<=8;i++)

      printf("%d ",chess[i]);

    printf("\n");

    result++;

}