八皇后问题并输出棋盘（回溯法）

本文主要是介绍八皇后问题并输出棋盘（回溯法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

八皇后问题并输出棋盘

题目：

在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
并将答案按照国际象棋棋盘样式输出

解题思路：

1.求解决方案
输入：皇后的个数 n
输出：n 皇后的解的棋盘
初始化解向量 x[n]=-1
解：

1、K=1
2、While(k>=1)3、把皇后摆放在下一列的位置，x[k]++4、从 x[k]开始依次考察下一列，如果皇后 k 摆放在 x[k]位置不发生冲突，转 5，否则 x[k]++试探下一列5、若 n 个皇后都已全部摆放，则输出一个解，算法结束；6、若尚有皇后没摆放，k++，转步骤 5 转下一个皇后7、若 x[k]出界，回溯，x[k]=-1，k--，转步骤 3 重新摆放皇后 k8、退出循环，说明 n 皇后问题无解

2.输出棋盘
从国际象棋棋盘可以看出，黑格和白格交替分布，相邻两行分布错位，所以按照这个规律，写出如下函数：

void printChess(int *a) {for (int i = 0; i < N; ++i) { //遍历每一行for (int j = 0; j < N; ++j) { //遍历每一列if (i%2==0 && j%2==0)cout << (a[i] == j ? "K" : "+");else if (i%2==1 && j%2==0)cout << (a[i]== j ? "`" : ">");else if (i%2==0 && j%2==1)cout << (a[i] == j ? "`" : ">");else if (i%2==1 && j%2==1)cout << (a[i] == j ? "K" : "+");} //如果标记数组中这一行的皇后放在j位置，则输出X，否则输出-，cout << endl; //每一行输出一个换行}cout << endl;
}

这里用的字体是Chess Adventure，用户需要自行下载并安装到自己的电脑中，链接如下：http://www.fontsaddict.com/font/chess-adventurer.html
如果无法下载请私信我。

其中‘K’，‘+’，‘`’，‘>’代表着白底皇后，白格，黑底皇后，黑格，当然也可以选择其他符号

源代码

#include<iostream>
#include <math.h>  
using namespace std;          
const int N = 8;                       
int x[N] = {-1};               //将数组x[N]初始化为-1int Place(int k)                    //考察皇后k放置在x[k]列是否发生冲突
{for (int i = 0; i < k; i++)   if (x[i] == x[k] || abs(i - k) == abs( x[i] - x[k]))  //冲突，返回1return 1;                                          return 0;                                            //不冲突，返回0
}void printChess(int *a) {for (int i = 0; i < N; ++i) { //遍历每一行for (int j = 0; j < N; ++j) { //遍历每一列if (i%2==0 && j%2==0)cout << (a[i] == j ? "K" : "+");else if (i%2==1 && j%2==0)cout << (a[i]== j ? "`" : ">");else if (i%2==0 && j%2==1)cout << (a[i] == j ? "`" : ">");else if (i%2==1 && j%2==1)cout << (a[i] == j ? "K" : "+");} //如果标记数组中这一行的皇后放在j位置，则输出X，否则输出-，cout << endl; //每一行输出一个换行}cout << endl;
}void Queue(int n)                      
{int k = 0;  int solution=0;                         while (k >= 0)                               //摆放皇后{x[k]++;                                       //在下一列摆放皇后kwhile (x[k] < n && Place(k) == 1)                           //发生冲突x[k]++;                                       //皇后k试探下一列if (x[k] < n && k == n - 1 )                         //得到一个解，输出{cout<<"Solutions："<<solution+1<<endl;printChess(x);solution++;x[k--] = -1;                  //重置x[k]，回溯，重新摆放皇后k}else if (x[k] < n && k < n - 1)                         //尚有皇后未摆放k = k + 1;                               //准备摆放下一个皇后elsex[k--] = -1;                  //重置x[k]，回溯，重新摆放皇后k}cout<<"Solutions="<<solution<<endl;cout<<"end"<<endl;
}int main( )
{Queue(8);         return 0;                      
}