C語言基于回溯算法解決八皇后問題的方法
更新時間：2018年06月20日 10:46:25 作者：憶之逸之
這篇文章主要介紹了C語言基于回溯算法解決八皇后問題的方法,簡單描述了八皇后問題,并結(jié)合實例形式分析了C語言使用回溯算法解決八皇后問題的相關(guān)操作技巧,需要的朋友可以參考下
本文實例講述了C語言基于回溯算法解決八皇后問題的方法。分享給大家供大家參考，具體如下：
問題描述：
八皇后問題，是一個古老而著名的問題，是回溯算法的典型案例：在8X8格的國際象棋棋盤上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。
問題求解：
采用回溯算法，即從第一行開始，依次探查可以放置皇后的位置，若找到，則放置皇后，開始探查下一行；若該行沒有位置可以放置皇后，則回溯至上一行，清除該行放置皇后的信息，從該行原本放置皇后的下一個位置開始探查可以放置皇后的位置。求所有解時，每找到一組解，就清除這一組解最后一個皇后的位置信息，開始探查該行另外一個可以放置皇后的位置，依次回溯求解。
存儲結(jié)構(gòu)：
一維數(shù)組：col[8]：存放第i列有無皇后的標記信息
一維數(shù)組：left[15]：存放每一條左斜線上的有無皇后的標記信息
一維數(shù)組：right[15]：存放每一條右直線上有無皇后的標記信息
一維數(shù)組：Q[8]：存放第i行的皇后的列下標
代碼實現(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;//已有皇后的標記
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;
}
運行結(jié)果：
一共92組解，前面結(jié)果略去。。
希望本文所述對大家C語言程序設(shè)計有所幫助。
相關(guān)文章
這篇文章主要為大家詳細介紹了C++的inline函數(shù)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
這篇文章主要為大家詳細介紹了C語言的結(jié)構(gòu)體，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
這篇文章主要介紹了基于C++實現(xiàn)的線程休眠代碼,包括了Linux平臺及基于boost庫的兩種實現(xiàn)方法,有不錯的參考借鑒價值,需要的朋友可以參考下2014-10-10
桶排序即是先把每個桶中的元素進行排序然后遍歷桶依次列出元素的算法,桶排序在元素較少的情況下很高效,以下我們就來詳解桶排序算法的思路及C++編程中的代碼實現(xiàn):2016-07-07
線性表，數(shù)據(jù)結(jié)構(gòu)中最簡單的一種存儲結(jié)構(gòu)，專門用于存儲邏輯關(guān)系為"一對一"的數(shù)據(jù)。線性表是基于數(shù)據(jù)在實際物理空間中的存儲狀態(tài)，又可細分為順序表（順序存儲結(jié)構(gòu)）和鏈表2022-04-04
C++ normal_distribution高斯正態(tài)分布函數(shù)的用法示例
高斯分布也稱為正態(tài)分布（normal distribution）,常用的成熟的生成高斯分布隨機數(shù)序列的方法由Marsaglia和Bray在1964年提出,這篇文章主要給大家介紹了關(guān)于C++ normal_distribution高斯正態(tài)分布函數(shù)用法的相關(guān)資料,需要的朋友可以參考下2021-07-07
這篇文章主要為大家詳細介紹了Matlab如何獲取文件夾下所有指定后綴的文件（包含子文件夾），文中的示例代碼講解詳細，感興趣的可以嘗試一下2022-11-11
QStackedWidget是Qt框架中一個非常有用的控件,它允許你堆疊多個窗口部件,本文主要介紹了Qt中QStackedWidget控件的實現(xiàn),具有一定的參考價值,感興趣的可以了解一下2025-04-04
最短時間學會基于C++實現(xiàn)DFS深度優(yōu)先搜索
常見使用深度優(yōu)先搜索(DFS)以及廣度優(yōu)先搜索(BFS)這兩種搜索，今天我們就來講講什么是深度優(yōu)先搜索，感興趣的可以了解一下2021-08-08
這篇文章主要介紹了c++如何實現(xiàn)歸并兩個有序鏈表，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07