數據結構學習之棧求解n皇后問題

0x1 目的

? 深入掌握棧應用的算法和設計

0x2 內容

? 編寫一個程序exp3-8.cpp求解n皇后問題。

0x3 問題描述

即在n×n的方格棋盤上，放置n個皇后，要求每個皇后不同行、不同列、不同左右對角線。

要求：（1）皇后的個數n由用戶輸入，其值不能超過20，輸出所有的解。（2）采用類似于棧求解迷宮問題的方法。

0x4 代碼

#include <iostream> #include <cstdio> #include <cstdlib> #include <string.h> #define MaxSize 100000+7 #define maxsize 20+7 using namespace std;int path[maxsize][maxsize]; int n;int y_pos[maxsize]; int count=0; bool judge(int num) {for(int i=0;i<num;i++){if(y_pos[i]==y_pos[num] || abs(y_pos[num]-y_pos[i])==num-i)return false;}return true; } typedef struct {int x;int y;int di; }Box;typedef struct {Box data[MaxSize];int top; }StType;void InitStack(StType *&s) {s=(StType *)malloc(sizeof(StType));s->top=-1; }void DestroyStack(StType *&s) {free(s); }bool GetTop(StType *&s,Box &e) {if(s->top==-1)return false;e=s->data[s->top];return true; }bool push(StType *&s,Box e) {if(s->top==MaxSize-1)return false;s->top++;s->data[s->top]=e;return true; }bool pop(StType *&s,Box &e) {if(s->top==-1)return false;e=s->data[s->top];s->top--;return true; }int GetLength(StType *s) {return(s->top+1); }bool EmptyStack(StType *s) {return(s->top==-1); }void SetPath(int ex,int ey,int k) {int xi=ex;int yi=ey;for(int i=0;i<n;i++){path[xi][i]+=k;path[i][yi]+=k;}int x1,x2,y1,y2;x1=x2=xi;y1=y2=yi;while(x1>0&&y1>0)path[--x1][--y1]+=k;while(x2<n&&y2<n)path[x2++][y2++]+=k;path[xi][yi]-=k*2; }void printSolution() {for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(y_pos[i]==j)printf("q");elseprintf("*");}printf("\n");}printf("\n"); }void Disp(StType *s) {for(int i=0;i<s->top;i++)printf("\t(%d,%d)",s->data[i].x,s->data[i].y); }void SolveQ(int n) {int x1,y1,di;StType *st;InitStack(st);Box e;e.x=0;e.y=-1;push(st,e);while(!EmptyStack(st)){GetTop(st,e);x1=e.x;y1=e.y;bool find=false;if(x1==n){printSolution();Disp(st);printf("\n");count++;}while(y1<n-1 && !find){y1++;y_pos[x1]=y1;st->data[st->top].y=y1;if(judge(x1)){find=true;e.x=x1+1;e.y=-1;push(st,e);}}if(!find){pop(st,e);}//pop(st,e);} }int main() {printf("please input n:\n");scanf("%d",&n);memset(path,0,sizeof(path));memset(y_pos,0,sizeof(y_pos));SolveQ(n);printf("\n count:%d \n",count);return 0; }

0x5 結果

0x6 總結

? 當時我在寫的時候很糾結從0開始的問題,思想肯定是這樣子的,先遍歷每一行的每一列,然后在回溯。那么就需要做好回溯的標志e.x記錄當前在第幾行,方便下次回溯到e.x-1,這里唯一需要注意的是判斷打印條件,if(x1==n),一開始我以為既然已經讓第七行進棧了,那么說明滿足,但是后面我理解錯了,程序的邏輯是下一行進棧開始的時候y1=-1的,也就是我們要去到第8行才能知道第7行的結果是可以的。

轉載于:https://www.cnblogs.com/xq17dog/p/10694116.html

總結

以上是生活随笔為你收集整理的数据结构学习之栈求解n皇后问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。