完成8皇后问题,若棋盘为5X5
- //完成8皇后问题,若棋盘为5X5或9X9结果如何
- #include
- #include
- #include
- using namespace std;
- //x,y表示放置皇后的坐标,二维数组attack表示棋盘是否可放置皇后
- void put_queen(int x,int y,vector
int > >&attack) - {
- //定义方向数组,周围8个方向
- static const int dx[]={-1,1,0,0,-1,-1,1,1};
- static const int dy[]={0,0,-1,1,-1,1,-1,1};
- attack[x][y]=1;//将皇后位置标记为1
- //将该皇后可能攻击的位置进行标记
- for(int i;i
size();i++) - {
- for(int j=0;j<8;j++)
- //遍历8个方向
- {
- int nx=x+i*dx[j];
- int ny=y+i*dy[j];
- //新位置要在棋盘范围内
- if(nx>=0&&nx
size()&&ny>=0&&nysize()) - {
- attack[nx][ny]=1;
- }
- }
- }
- }
- //回溯法函数,k表示当前的行,n表示n皇后
- //queen储存皇后位置,attack标记皇后攻击位置,solve储存全部解法
- void backtrack(int k,int n,vector
&queen, - vector
int > >&attack, - vector
>&solve) - {
- if(k==n)//找到一组解
- {
- solve.push_back(queen);
- return;
- }
- for(int i=0;i
- {
- if(attack[k][i]==0)
- //判断k行i列能否放皇后
- {
- vector
int> >tmp=attack; - queen[k][i]='Q';
- put_queen(k,i,attack);//更新attack数组
- backtrack(k+1,n,queen,attack,solve);//递归试探k+1行皇后放置
- //如果失败,回溯至此恢复两个数组
- attack=tmp;
- queen[k][i]='.';
- }
- }
- }
- vector
>solveNQueen(int n) - {
- vector
>solve; - vector
int> >attack; - vector
queen; - //初始化attack和queen
- for(int i=0;i
- {
- attack.push_back((std::vector<int>()));
- for(int j=0;j
- {
- attack[i].push_back(0);
- }
- queen.push_back("");
- queen[i].append(n,'.');
- }
- backtrack(0,n,queen,attack,solve);
- return solve;
- }
- int main()
- {
- int n;
- cout<<"请输入皇后数:"<
- cin>>n;
- vector
>result; - result=solveNQueen(n);
- cout<
"皇后有"<size()<<"种解法。"< - for(int i=0;i
size();i++) - {
- cout<<"解法"<1<<":"<
- for(int j=0;j
size();j++) - {
- cout<
c_str()< - }
- cout<
- }
- return 0;
- }
或9X9结果如何
-
相关阅读:
【C进阶】动态内存管理
枚举类型的使用
Ef Core实现数据审计与软删除
2022前端面试题上岸手册-React部分
自动驾驶学习笔记(三)——场景设计
python每日学5:python工程(大型项目)的组织架构:包、模块、类、方法
Ubuntu宝塔显示磁盘被占满的解决方法
mysql root允许远程连接
2022.9.20 go语言课程作业
JS——初始DOM的相关操作练习
-
原文地址:https://blog.csdn.net/Shenrunchen/article/details/126506620