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

成都創(chuàng)新互聯(lián)公司長期為超過千家客戶提供的網(wǎng)站建設服務，團隊從業(yè)經(jīng)驗10年，關注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為哈爾濱企業(yè)提供專業(yè)的成都做網(wǎng)站、成都網(wǎng)站設計，哈爾濱網(wǎng)站改版等技術服務。擁有10多年豐富建站經(jīng)驗和眾多成功案例,為您定制開發(fā)。

問題描述：

八皇后問題，是一個古老而著名的問題，是回溯算法的典型案例：在8X8格的國際象棋棋盤上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。

問題求解：

采用回溯算法，即從第一行開始，依次探查可以放置皇后的位置，若找到，則放置皇后，開始探查下一行；若該行沒有位置可以放置皇后，則回溯至上一行，清除該行放置皇后的信息，從該行原本放置皇后的下一個位置開始探查可以放置皇后的位置。求所有解時，每找到一組解，就清除這一組解最后一個皇后的位置信息，開始探查該行另外一個可以放置皇后的位置，依次回溯求解。

存儲結構：

一維數(shù)組：col[8]：存放第i列有無皇后的標記信息
一維數(shù)組：left[15]：存放每一條左斜線上的有無皇后的標記信息
一維數(shù)組：right[15]：存放每一條右直線上有無皇后的標記信息
一維數(shù)組：Q[8]：存放第i行的皇后的列下標

代碼實現(xiàn)：

#include
#define N 8
int col[N] = { 0 };
int right[2 * N - 1] = { 0 };
int left[2 * N - 1] = { 0 };
int Q[N];
int cnt = 0;
void Print()
{
  int i;
  for (i = 0; i < N; i++)
  {
    for (int j = 0; j < N; j++)
    {
      if (Q[i] == j)
        printf("■");
      else
        printf("□");
    }
    printf("\n");
  }
  printf("==========================\n");
  cnt++;
}
void Queen(int i)
{
  int j;
  for (j = 0; j < N; j++)
  {
    if ((!col[j]) && (!left[i + j]) && (!right[7 + i - j]))
    {
      Q[i] = j;//放皇后
      col[j] = 1;
      left[i + j] = 1;
      right[N - 1 + i - j] = 1;//已有皇后的標記
      if (i < N - 1)
      {
        Queen(i + 1);
      }
      else
      {
        Print();
      }
      col[j] = 0;
      right[N - 1 + i - j] = 0;
      left[i + j] = 0;//清除標記，查找下一組解
    }
  }
}
int main(void)
{
  Queen(0);
  printf("%d", cnt);
  getchar();
  return 0;
}

另外有需要云服務器可以了解下創(chuàng)新互聯(lián)建站www.cdcxhl.com，海內(nèi)外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

本文題目：C語言基于回溯算法解決八皇后問題的方法-創(chuàng)新互聯(lián)
當前URL：http://weahome.cn/article/dcchsg.html