C語言八皇后問題解決方法示例【暴力法與回溯法】

更新時間：2018年01月08日 09:08:01 作者：handsome_ZHANG

這篇文章主要介紹了C語言八皇后問題解決方法,簡單描述了八皇后問題并結合實例形式分析了C語言基于暴力法與回溯法解決八皇后的具體操作技巧,需要的朋友可以參考下

本文實例講述了C語言八皇后問題解決方法。分享給大家供大家參考，具體如下：

1.概述：

八皇后問題是一個以國際象棋為背景的問題：如何能夠在 8×8 的國際象棋棋盤上放置八個皇后，使得任何一個皇后都無法直接吃掉其他的皇后？為了達到此目的，任兩個皇后都不能處于同一條橫行、縱行或斜線上。

2.暴力法求解:

#include<cstdio>
#include<cmath>
const int maxn=11;
int count=0;
//P為當前排列,hashTable記錄整數(shù)x是否已經在P中
int n,P[maxn] ,hashTable[maxn] = {false};
//當前處理排列的第index號位
void generateP(int index)
{
  if(index==n+1)//遞歸邊界,已經處理完排列的1~n位
  {
  bool flag=true;//flag為true表示當前排列為一個合法方案
  for(int i=1;i<=n;i++)
  {
    for(int j=i+1;j<=n;j++)
    {
      if(abs(i-j)==abs(P[i]-P[j]))//如果在對角線上
      {
        flag=false;//不合法
      }
    }
   }
   if(flag)  count++;//若當前方案合法,count+1
   return ;
 }
 for(int x=1 ; x<=n ; x++)//枚舉1~n,試圖將x填入P[index]
 {
  if(hashTable[x]==false)//如果x不在P[0]~P[index-1]中
  {
    P[index]=x; //令P的第index位為x,即把x加入當前排列
    hashTable[x]=true;//記x已在P中
    generateP(index+1);//處理排列的第index+1號位
    hashTable[x]=false;//已處理完P[index]為x的子問題,還原狀態(tài)
}
}
}
int main()
{
  n=8;
  generateP(1);
  printf("%d\n",count);
  return 0;
}

3.回溯法求解;

#include<cstdio>
#include<cmath>
const int maxn=11;
int count=0;
//P為當前排列,hashTable記錄整數(shù)x是否已經在P中
int n,P[maxn] ,hashTable[maxn] = {false};
//當前處理排列的第index號位
void generateP(int index)
{
  if(index==n+1)
  {
    count++;
    return ;
  }
  for(int x=1;x<=n;x++)//第x行
  {
    if(hashTable[x]==false)//第x行還沒有皇后
    {
      bool flag=true;//flag表示當前皇后不會和之前的皇后沖突
      for(int pre=1;pre<index;pre++)//遍歷之前的皇后
      {//第index行的皇后的行號為x,第pre列皇后的行號為P[pre]
        if(abs(index-pre)==abs(x-P[pre]))
        {
          flag=false;//與之前的皇后在一條對角線,沖突
          break;
         }
       }
       if(flag)//如果可以把皇后放在第x行
       {
        P[index]=x;//令第index列皇后的行數(shù)為x
         hashTable[x]=true;//第x行已經被占用
         generateP(index+1);//遞歸處理第index+1行皇后
         hashTable[x]=false;//遞歸完畢,還原第x行為為占用狀態(tài)
       }
     }
   }
}
int main()
{
  n=8;
  generateP(1);
  printf("%d\n",count);
  return 0;
}

希望本文所述對大家C語言程序設計有所幫助。

您可能感興趣的文章: