C語言基于回溯算法解決八皇后問題的方法
本文實(shí)例講述了C語言基于回溯算法解決八皇后問題的方法。分享給大家供大家參考，具體如下：
問題描述：
八皇后問題，是一個(gè)古老而著名的問題，是回溯算法的典型案例：在8X8格的國(guó)際象棋棋盤上擺放八個(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ǔ)大小端問題，文中通過代碼示例給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作有一定的幫助,需要的朋友可以參考下2024-02-02
windows自帶的游戲《掃雷》是陪伴了無數(shù)人的經(jīng)典游戲，本程序參考《掃雷》的規(guī)則進(jìn)行了簡(jiǎn)化，用Matlab實(shí)現(xiàn)，感興趣的小伙伴可以學(xué)習(xí)一下2022-03-03
C語言實(shí)現(xiàn)輸入一個(gè)字符串后打印出該字符串中字符的所有排列
這篇文章主要介紹了C語言實(shí)現(xiàn)輸入一個(gè)字符串后打印出該字符串中字符的所有排列的方法,是數(shù)學(xué)中非常實(shí)用的排列算法,需要的朋友可以參考下2014-09-09
這篇文章主要介紹了Linux下C語言修改進(jìn)程名稱的方法,涉及Linux下使用C語言操作進(jìn)程的相關(guān)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-07-07
C語言實(shí)現(xiàn)自行車存放管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)自行車存放管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-08-08
本篇文章是對(duì)用C語言實(shí)現(xiàn)單鏈表的各種操作進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
深度解析三個(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
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)將簡(jiǎn)單密碼譯回原文的方法
這篇文章主要介紹了C++實(shí)現(xiàn)將簡(jiǎn)單密碼譯回原文的方法,可實(shí)現(xiàn)將簡(jiǎn)單的字母位移類型的密碼譯回原文的功能,涉及C++簡(jiǎn)單字符串操作相關(guān)技巧,需要的朋友可以參考下2016-05-05
這篇文章主要為大家詳細(xì)介紹了如何使用C++獲取邏輯執(zhí)行毫秒數(shù)的方法,文中借助c++11提供的steady_clock,實(shí)現(xiàn)了精確獲取邏輯執(zhí)行時(shí)間的方法,需要的可以參考下2024-02-02