当前位置: 代码迷 >> 综合 >> 洛谷 P1219-八皇后(dfs回溯)
  详细解决方案

洛谷 P1219-八皇后(dfs回溯)

热度:76   发布时间:2024-01-27 04:23:39.0

题目描述

网址传送:https://www.luogu.com.cn/problem/P1219
八皇后问题描述:介是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

题目分析

很显然,这个题目是不能用暴力n重循环来求解的,在网上找了好多解答,主要的思想就是dfs回溯。

进行深度优先搜索时,脑海中要形成自己的一个框架:
1.寻找约束条件,即边界,否则程序就停不下来了~~~
2.确定主要的函数体,即在一遍一遍的递归调用中要去做什么事情 (博主水平有限所以没有太去区分 递归与回溯)

开始回溯:
第一层dfs选择(1,1)作为第一个皇后的位置,标记hang[1]=1,然后判断这个皇后的位置是否符合要求,如果符合要求,则进行第二层dfs;若不符合要求,则更换第一个皇后的位置为(1,2)标记hang[1]=2,再重复上述过程。而进入第二层循环的dfs则把第二个皇后放到(2,1)位置,如上继续进行判断…………等到进行到第八层dfs且这八个皇后都能合法放好后,则记录这一次的合法放置。然后从第八个皇后位置开始进行回溯,取消第八个皇后的标记,回到第七个皇后的放置考虑上来,7的位置加1,然后再次开始判断后面的是否满足。

这个确实比较绕,要想彻底搞懂dfs的回溯需要不断地想 想 想 还有做题 做题 做题!
从第一个皇后开始画多叉树来模拟递归层次便于理解,不过需要准备一张非常大的纸~~

AC代码

#include<iostream>
#include<cmath>
#include<stdio.h>
#include<stdlib.h>
#include<cstdio> 
#include<time.h>
#include<cmath>
#include<algorithm>
using namespace std;int map[15][15]={0};//棋盘,值为0表示没有棋子,为1表示有棋子
int hang[15]={0};//hang的值则表示第i行的那一列放棋子 
bool check(int num,int i)
{ //判断 1-(num-1)行 是否与 将放在第num行第i个的棋子冲突 for(int j=1;j<num;++j){  // 列不重复,不在一条对角线上(即判断斜率,且注意判断斜率时不要写除法,会出现变量为0的情况且不报错!!)if(hang[j]==i || abs(hang[j]-i)==abs(j-num))  return false;}return true;//返回ture,代表(num,i)可以放棋子 
}
int sum,n;
void print()
{ //输出每一行皇后的位置for(int i=1;i<=n-1;i++)cout<<hang[i]<<" ";cout<<hang[n];cout<<endl;
} 
void dfs(int num)
{ //深度优先遍历寻找可以放棋子(皇后)的地方 if(num>n) //如果遍历层数大于棋盘的边长,则停止递归,进行记录/输出{ sum++;    //记录满足条件的皇后放置种类加1if(sum<=3)print();  //这是单独针对 p1219题的~~~return ;}for(int i=1;i<=n;i++){hang[num] = i;   //第num行皇后的放置位置为i,即皇后放置在(num,i)坐标上if(check(num,i)) //第 num行,第 i 列 {map[num][i]=1; //记录皇后位置dfs(num+1); //进行下一层递归map[num][i]=0;  //注意回溯,否则容易错误记录(因为满足条件的种类可能很多,读脏数据!}}
} 
int main()
{cin>>n;dfs(1);cout<<sum;
}