image.png
法一矩阵维护法，思路相对简单的方法
cheese_table为8*8的棋盘，queen数组记录八个皇后各自的列数（前面说过，第N个皇后默认放在第N行，所以行数是隐式记录的），lastqueen记录着最后放置的那个皇后的列数（回溯时候很重要，保证回溯到上一行操作时候不会踏进同一个坑即不会再把皇后放到刚刚放过的地方），solution记录八皇后有几种放的方法。Search_line（i，j）函数将会搜寻第i行从j列开始还有没可以放的格子，set_queen（i，j）就是在可放皇后的(I,j)格子放下皇后，并且在棋盘上对放下的这个皇后的行列和主副对角线的格子进行标记，标记的方法是代表这些格子的数+1（这是本解法很关键的一点，并不是简简单单的对这些不可放置点从一个状态比如0置为1代表不可放置了，而是每次把某个皇后对应影响的这些格子的数都增加1，这么做极大的好处就是你回溯的时候只要逆着过去对拿走的皇后本会影响的格子减1即可，而不需要判断这些格子是否还会被其他在棋盘上的的皇后影响从而决定维持不可放的状态还是变为可放的状态，极大的减少了维护棋盘时候大量调用判断函数的时间，而只要简单的加减即可）。Uptate_queen（i）函数就是拿起第i行的皇后，即本解法的回溯部分，对应set的过程你这做即可。最后看看主函数，初始化不说了，for循环中大致过程就是对每一行search出皇后可放位置，找到可放格子就放下皇后，如果八个皇后都放完了记一次数，并且在最后一行寻找是否有其他放皇后的位置，没有的话往前一行回溯；刚刚在某一行search不到放皇后的格子就只能回溯上一行。如果发现这一行就是第0行没有上一行了还要回溯，证明我们算法结束了，退出循环。这个for循环大概是假的for循环，没有限定i的大小，依靠的其实是想要回溯之前看看还能不能回溯来跳出。
#include <iostream>
using namespace std;
int cheese_table[8][8];
int queen[8];//记录皇后的列数
int lastqueen=-1;
int solution=0;
int search_line(int i,int j) //搜索这一行有没有可以放的位置
{
for(;j<8;j++)
if(cheese_table[i][j]==0)
return j; //返回可放位置位于第几列
return -1; //返回-1说明没有可放的位置
}
void set_queen(int i,int j)//在可放的位置上放置皇后记录下来并对棋盘进行操作
{
cheese_table[i][j]=-1;
queen[i]=j;
int temp;
for(temp=0;temp<8;temp++)//列操作
if(cheese_table[temp][j]!=-1) //为什么有条件cheese_table[temp][j]!=-1，
cheese_table[temp][j]++; //因为不能让它自己的位置加1。
for(temp=0;temp<8;temp++)//行操作
if(cheese_table[i][temp]!=-1)
cheese_table[i][temp]++;
int tempj=j+1,tempi;
for(tempi=i+1;tempi<8&&tempj<8;tempi++)
cheese_table[tempi][tempj++]++;
tempj=j-1;
for(tempi=i+1;tempi<8&&tempj>=0;tempi++)//西南对角线操作
cheese_table[tempi][tempj--]++;
tempj=j+1;
for(tempi=i-1;tempi>=0&&tempj<8;tempi--)//东北对角线操作
cheese_table[tempi][tempj++]++;
tempj=j-1;
for(tempi=i-1;tempi>=0&&tempj>=0;tempi--)//西北对角线操作
cheese_table[tempi][tempj--]++;
return;
}
void uptake_queen(int i) //回溯部分，撤回当前皇后
{
int j=queen[i];
int temp;
for(temp=0;temp<8;temp++)
if(cheese_table[temp][j]!=-1)
cheese_table[temp][j]--;
for(temp=0;temp<8;temp++)
if(cheese_table[i][temp]!=-1)
cheese_table[i][temp]--;
int tempj=j+1,tempi;
for(tempi=i+1;tempi<8&&tempj<8;tempi++)
cheese_table[tempi][tempj++]--;
tempj=j-1;
for(tempi=i+1;tempi<8&&tempj>=0;tempi++)
cheese_table[tempi][tempj--]--;
tempj=j+1;
for(tempi=i-1;tempi>=0&&tempj<8;tempi--)
cheese_table[tempi][tempj++]--;
tempj=j-1;
for(tempi=i-1;tempi>=0&&tempj>=0;tempi--)
cheese_table[tempi][tempj--]--;
cheese_table[i][j]=0;
return;
}
void print_cheese()
{
int i,j;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
if(cheese_table[i][j]==-1)
cout<<"x ";
else
cout<<"0 ";
}
cout<<endl;
}
cout<<endl;
return;
}
int main()
{
int i,j;
for(i=0;i<8;i++)
for(j=0;j<8;j++)
cheese_table[i][j]=0;
//初始化棋盘
for(i=0;;i++)
{
j=search_line(i,lastqueen+1);//判断是否第i行有可放位置，若有返回列数，没有就返回-1，
if(j==-1) //其中若第i行某列是0，但它下一行没有可放的，就要回溯同时用lastqueen将其记录，
{ //然后从第i行lastqueen+1列继续判断是否可放
if(i==0) break;
uptake_queen(i-1); //下一行没有空位置，回到本行刚刚找到的空位置，将其取消，
lastqueen=queen[i-1]; //然后从它的下一个位置开始从新找符合的空位置
i=i-2; //因为执行完后马上要执行i++
}
else
{
lastqueen=-1; //本行有空位置，令lastqueen=-1为下一行从零开始找空位做铺垫
set_queen(i,j); //本行有空位置，开始对本行操作，将它相关的行列和对角线加1.
if(i==7)
{
solution++; //方案+1
print_cheese(); //打印图形
uptake_queen(7); //由于是最后一行，此空位后面的位置可能还有成立的，所以把此位置回溯，继续找他下一个位置看还有没有成立的。
lastqueen=j;
i--;
}
}
}
cout<<solution<<endl;
return 0;
}
92种具体放法，这里是部分截图
image.png
法二
递归法1！这里用了分支修剪的方法。解释不够，思路懂，具体backtrack的实现原理没看懂，找时间查具体原理再好好看。
#include <stdio.h>
#include <stdlib.h>
#define N 8
int column[N+1]; // 同栏是否有皇后，1表示有
int rup[2*N+1]; // 右上至左下是否有皇后
int lup[2*N+1]; // 左上至右下是否有皇后
int queen[N+1] = {0};
int num; // 解答编号
void backtrack(int); // 递回求解
int main(void) {
int i;
num = 0;
for(i = 1; i <= N; i++)
column[i] = 1;
for(i = 1; i <= 2*N; i++)
rup[i] = lup[i] = 1;
backtrack(1);
return 0;
}
void showAnswer() {
int x, y;
printf("\n解答 %d\n", ++num);
for(y = 1; y <= N; y++) {
for(x = 1; x <= N; x++) {
if(queen[y] == x) {
printf(" Q");
}
else {
printf(" .");
}
}
printf("\n");
}
}
void backtrack(int i)
{
int j;
if(i > N) {
showAnswer();
}
else
{
for(j = 1; j <= N; j++)
{
if(column[j] == 1 &&
rup[i+j] == 1 && lup[i-j+N] == 1)
{
queen[i] = j;
// 设定为占用
column[j] = rup[i+j] = lup[i-j+N] = 0;
backtrack(i+1);
column[j] = rup[i+j] = lup[i-j+N] = 1;//如果某一次还没到8但已经没有可放的了，
} //比如执行到第五排有放的，但第六排没有放的了，
} //那么在执行第六排的时候会将整个的for执行完后结束所有第六排的工作，
} //然后跳回第五排执行column[j] = rup[i+j] = lup[i-j+N] = 1;
} //然后第五排继续j+1往下执行，这儿其实就有了自动的回溯！
部分答案截图：
image.png
image.png
递归法2！
//八皇后递归解法
#include<iostream>
using namespace std;
int queen[9]={-1,-1,-1,-1,-1,-1,-1,-1,-1};
int count=0;
bool available(int pointi,int pointj)
{//判断某个皇后是否与已有皇后冲突
for(int i=1;i<pointi;i++)
{
if(pointj==queen[i])return false;//同一列拒绝
if((pointi-i)==(pointj-queen[i]))return false;//同一主对角线拒绝
if((pointi-i)+(pointj-queen[i])==0)return false;//同一副对角线拒绝
}
return true;
}
void printit(int queen[9])
{
int i;
for(i=1;i<9;i++)
{
cout<<queen[i]<<' ';
}
cout<<endl;
}
void findSpace(int queenNumber)
{//在第queenNumber行找能放皇后的位置
for(int i=1;i<9;i++)
{//从1~8遍历这一行的八个空位
if(available(queenNumber,i))
{
//如果可以放这个位置就记录下第queenNumber个皇后的位置
queen[queenNumber]=i;
if(queenNumber==8)
{//如果八个皇后都放满了统计一下
printit(queen);
count++;
return;
}
int nextNumber=queenNumber+1;//还有皇后没放递归放下一个皇后
findSpace(nextNumber);
}
}
queen[--queenNumber]=-1;//如果这一行没有可放的位置说明上一行皇后放的位置不行，要为上一个皇后寻找新的可放位置
return;
}
int main()
{
findSpace(1);//从（1，1）开始递归好理解
cout<<endl;
cout<<count<<endl;
return 0;
}
答案每一行表示八个皇后所在行的列数
部分答案截图
网友评论