C語言基于回溯算法解決八皇后問題的方法
本文實(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語言實(shí)現(xiàn)輸入一個(gè)字符串后打印出該字符串中字符的所有排列
這篇文章主要介紹了C語言實(shí)現(xiàn)輸入一個(gè)字符串后打印出該字符串中字符的所有排列的方法,是數(shù)學(xué)中非常實(shí)用的排列算法,需要的朋友可以參考下2014-09-09C語言實(shí)現(xiàn)自行車存放管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)自行車存放管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-08-08深度解析三個(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