回溯算法-八皇后有关问题

回溯算法---八皇后问题

采用上节回溯算法的思想，解决八皇后问题，先看执行结果：

当NUM=4时，有两个解：

回溯算法-八皇后有关问题

当 NUM=5时，有10个解：

回溯算法-八皇后有关问题

当NUM=6时，有4个解：

回溯算法-八皇后有关问题

当NUM为7时，有40个解：

回溯算法-八皇后有关问题

当NUM为8时，有92个解：

回溯算法-八皇后有关问题

当NUM为16时，其中的一个解如下：

回溯算法-八皇后有关问题

当NUM为30时，其中的一个解如下：

回溯算法-八皇后有关问题

源程序：

1）求解单个解

#include "stdafx.h"#include "OneResult.h"BOOL TestNode(int i,int j){// 判断 i行j列  是否满足条件//与之前的行相比for (int k=0;k&lt;=i-1;k++){//同列if(j==A[k])return FALSE;//同斜线if(abs(i-k)==abs(j-A[k]))return FALSE;}A[i]=j;// 到此为止  0--i行 均无冲突// 如果是最后一行  成功找到一个解  将其加如到总解中if(i==NUM-1){OneResult.clear();for (int k1=0;k1&lt;NUM;k1++){OneResult.push_back(A[k1]);}AllResuleVec.push_back(OneResult);return TRUE;}//如果不是最后一行 则判断i+1行// 判断 i+1行  是否存在不冲突的解BOOL bSuit=FALSE;for (int k=0;k&lt;NUM;k++){//第i+1行存在合适位置 if (TestNode(i+1,k)){bSuit=TRUE;//如果找到合适的 直接退出break;}}return bSuit;}static BOOL EightQueen(){//只需判断第一行中  是否有合适位置即可BOOL  bExist=FALSE;for (int j=0;j&lt;NUM;j++){if (TestNode(0,j)){bExist=TRUE;break;}}return bExist;}static void PrintChessBoard(){/* 得到控制台显示句柄 */HANDLE hScreen = GetStdHandle(STD_OUTPUT_HANDLE);for (int num=0;num&lt;AllResuleVec.size();num++){for (int k=0;k&lt;NUM;k++){A[k]=AllResuleVec.at(num).at(k);}int i, j;for (i=0; i&lt;NUM; i++){for (j=0; j&lt;NUM; j++){/* 控制台可显示8种背景颜色和8种字体颜色 *//* 背景颜色为0x0000 - 0x0070，增量为0x0010 *//* 字体颜色为0x0000 - 0x0007，增量为0x0001 *//* 下面这种办法可使背景颜色与字体颜色互为相反色 */WORD bgColor;WORD foColor;if(A[i]==j){// bgColor = 0x0070 - 0x0010 * (A[i] % 8);// foColor = 0x0000 + 0x0001 * (A[i] % 8);bgColor = 0x0070 - 0x0010 * 4;foColor = 0x0000 + 0x0001 * 4;}else{bgColor = 0x0070 - 0x0010*0 ;foColor = 0x0000 + 0x0001*0 ;}SetConsoleTextAttribute(hScreen, foColor | bgColor);/* 要使输出结果矩阵元素对齐，需要补空格 */if (A[i] !=j){cout&lt;&lt;"□";}else{cout&lt;&lt;"■";}}cout&lt;&lt;endl;}cout&lt;&lt;endl&lt;&lt;endl;}/* 重设回原来的颜色 *//* FOREGROUND_RED | FOREGROUND_BLUE | FOREGROUND_GREEN 即为字体白色，对应0x0007 *//* 0 即为背景黑色 */SetConsoleTextAttribute(hScreen, FOREGROUND_RED | FOREGROUND_BLUE | FOREGROUND_GREEN | 0);} void QueenOne(){HANDLE hScreen = GetStdHandle(STD_OUTPUT_HANDLE);COORD coord;coord.X=100;coord.Y=2000;SetConsoleScreenBufferSize(hScreen,coord);EightQueen();int num=AllResuleVec.size();PrintChessBoard();cout&lt;&lt;endl;cout&lt;&lt;num&lt;&lt;endl;}

2）求解所有解

#include "stdafx.h" int A[NUM]={0}; std::vector&lt;int&gt; OneResult; std::vector &lt;std::vector&lt;int&gt;&gt; AllResuleVec;

#include "stdafx.h"#include "AllResult.h" static BOOL TestNode(int i,int j){// 判断 i行j列  是否满足条件//与之前的行相比for (int k=0;k&lt;=i-1;k++){//同列if(j==A[k])return FALSE;//同斜线if(abs(i-k)==abs(j-A[k]))return FALSE;}A[i]=j;// 到此为止  0--i行 均无冲突// 如果是最后一行  成功找到一个解  将其加如到总解中if(i==NUM-1){OneResult.clear();for (int k1=0;k1&lt;NUM;k1++){OneResult.push_back(A[k1]);}AllResuleVec.push_back(OneResult);return TRUE;}//如果不是最后一行 则判断i+1行// 判断 i+1行  是否存在不冲突的解BOOL bSuit=FALSE;for (int k=0;k&lt;NUM;k++){//第i+1行存在合适位置 if (TestNode(i+1,k)){bSuit=TRUE;//return TRUE;//继续下一个测试}}//第i+1行 不存在合适位置if (!bSuit)return FALSE;}static BOOL EightQueen(){//只需判断第一行中  是否有合适位置即可BOOL  bExist=FALSE;for (int j=0;j&lt;NUM;j++){if (TestNode(0,j)){bExist=TRUE;//break;}}return bExist;}static void PrintChessBoard(){/* 得到控制台显示句柄 */HANDLE hScreen = GetStdHandle(STD_OUTPUT_HANDLE);for (int num=0;num&lt;AllResuleVec.size();num++){for (int k=0;k&lt;NUM;k++){A[k]=AllResuleVec.at(num).at(k);}int i, j;for (i=0; i&lt;NUM; i++){for (j=0; j&lt;NUM; j++){/* 控制台可显示8种背景颜色和8种字体颜色 *//* 背景颜色为0x0000 - 0x0070，增量为0x0010 *//* 字体颜色为0x0000 - 0x0007，增量为0x0001 *//* 下面这种办法可使背景颜色与字体颜色互为相反色 */WORD bgColor;WORD foColor;if(A[i]==j){// bgColor = 0x0070 - 0x0010 * (A[i] % 8);// foColor = 0x0000 + 0x0001 * (A[i] % 8);bgColor = 0x0070 - 0x0010 * 4;foColor = 0x0000 + 0x0001 * 4;}else{bgColor = 0x0070 - 0x0010*0 ;foColor = 0x0000 + 0x0001*0 ;}SetConsoleTextAttribute(hScreen, foColor | bgColor);/* 要使输出结果矩阵元素对齐，需要补空格 */if (A[i] !=j){cout&lt;&lt;"□";}else{cout&lt;&lt;"■";}}cout&lt;&lt;endl;}cout&lt;&lt;endl&lt;&lt;endl;}/* 重设回原来的颜色 *//* FOREGROUND_RED | FOREGROUND_BLUE | FOREGROUND_GREEN 即为字体白色，对应0x0007 *//* 0 即为背景黑色 */SetConsoleTextAttribute(hScreen, FOREGROUND_RED | FOREGROUND_BLUE | FOREGROUND_GREEN | 0);} void QueenAll() { HANDLE hScreen = GetStdHandle(STD_OUTPUT_HANDLE); COORD coord; coord.X=100; coord.Y=2000; SetConsoleScreenBufferSize(hScreen,coord); EightQueen(); int num=AllResuleVec.size(); PrintChessBoard(); cout&lt;&lt;endl; cout&lt;&lt;num&lt;&lt;endl; }

源程序资源：http://download.csdn.net/detail/shuilan0066/4401578

回溯算法-八皇后有关问题

热点推荐