欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言基于回溯算法解決八皇后問題的方法

 更新時(shí)間:2018年06月20日 10:46:25   作者:憶之逸之  
這篇文章主要介紹了C語言基于回溯算法解決八皇后問題的方法,簡單描述了八皇后問題,并結(jié)合實(shí)例形式分析了C語言使用回溯算法解決八皇后問題的相關(guān)操作技巧,需要的朋友可以參考下

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

問題描述:

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

問題求解:

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

存儲(chǔ)結(jié)構(gòu):

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

代碼實(shí)現(xiàn):

#include<stdio.h>
#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;//已有皇后的標(biāo)記
      if (i < N - 1)
      {
        Queen(i + 1);
      }
      else
      {
        Print();
      }
      col[j] = 0;
      right[N - 1 + i - j] = 0;
      left[i + j] = 0;//清除標(biāo)記,查找下一組解
    }
  }
}
int main(void)
{
  Queen(0);
  printf("%d", cnt);
  getchar();
  return 0;
}

運(yùn)行結(jié)果:

一共92組解,前面結(jié)果略去。。

希望本文所述對(duì)大家C語言程序設(shè)計(jì)有所幫助。

相關(guān)文章

  • 使用C語言判斷當(dāng)前存儲(chǔ)大小端問題

    使用C語言判斷當(dāng)前存儲(chǔ)大小端問題

    這篇文章主要介紹了如何使用C語言判斷當(dāng)前存儲(chǔ)大小端問題,文中通過代碼示例給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作有一定的幫助,需要的朋友可以參考下
    2024-02-02
  • 利用Matlab復(fù)刻掃雷小游戲

    利用Matlab復(fù)刻掃雷小游戲

    windows自帶的游戲《掃雷》是陪伴了無數(shù)人的經(jīng)典游戲,本程序參考《掃雷》的規(guī)則進(jìn)行了簡化,用Matlab實(shí)現(xiàn),感興趣的小伙伴可以學(xué)習(xí)一下
    2022-03-03
  • C語言實(shí)現(xiàn)輸入一個(gè)字符串后打印出該字符串中字符的所有排列

    C語言實(shí)現(xiàn)輸入一個(gè)字符串后打印出該字符串中字符的所有排列

    這篇文章主要介紹了C語言實(shí)現(xiàn)輸入一個(gè)字符串后打印出該字符串中字符的所有排列的方法,是數(shù)學(xué)中非常實(shí)用的排列算法,需要的朋友可以參考下
    2014-09-09
  • Linux下C語言修改進(jìn)程名稱的方法

    Linux下C語言修改進(jìn)程名稱的方法

    這篇文章主要介紹了Linux下C語言修改進(jìn)程名稱的方法,涉及Linux下使用C語言操作進(jìn)程的相關(guān)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下
    2015-07-07
  • C語言實(shí)現(xiàn)自行車存放管理系統(tǒng)

    C語言實(shí)現(xiàn)自行車存放管理系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)自行車存放管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-08-08
  • 用C語言實(shí)現(xiàn)單鏈表的各種操作(二)

    用C語言實(shí)現(xiàn)單鏈表的各種操作(二)

    本篇文章是對(duì)用C語言實(shí)現(xiàn)單鏈表的各種操作進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下
    2013-05-05
  • 深度解析三個(gè)常見的C語言內(nèi)存函數(shù)

    深度解析三個(gè)常見的C語言內(nèi)存函數(shù)

    這篇文章主要深度解析了三個(gè)常見的C語言內(nèi)存函數(shù)memcpy,memmove,memcmp,所以本文將對(duì)memcpy,memmove,memcmp 三個(gè)函數(shù)進(jìn)行詳解和模擬實(shí)現(xiàn),需要的朋友可以參考下
    2023-07-07
  • C++編程之?std::forward使用例子

    C++編程之?std::forward使用例子

    std::forward?是一個(gè)?C++11?中的模板函數(shù),其主要作用是在模板函數(shù)或模板類中,將一個(gè)參數(shù)以“原樣”(forward)的方式轉(zhuǎn)發(fā)給另一個(gè)函數(shù),這篇文章主要介紹了C++編程之?std::forward,需要的朋友可以參考下
    2023-03-03
  • C++實(shí)現(xiàn)將簡單密碼譯回原文的方法

    C++實(shí)現(xiàn)將簡單密碼譯回原文的方法

    這篇文章主要介紹了C++實(shí)現(xiàn)將簡單密碼譯回原文的方法,可實(shí)現(xiàn)將簡單的字母位移類型的密碼譯回原文的功能,涉及C++簡單字符串操作相關(guān)技巧,需要的朋友可以參考下
    2016-05-05
  • 使用C++獲取邏輯執(zhí)行毫秒數(shù)的方法

    使用C++獲取邏輯執(zhí)行毫秒數(shù)的方法

    這篇文章主要為大家詳細(xì)介紹了如何使用C++獲取邏輯執(zhí)行毫秒數(shù)的方法,文中借助c++11提供的steady_clock,實(shí)現(xiàn)了精確獲取邏輯執(zhí)行時(shí)間的方法,需要的可以參考下
    2024-02-02

最新評(píng)論