回溯法-N皇后问题-C++算法
2022/4/11 11:12:48
本文主要是介绍回溯法-N皇后问题-C++算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
- N皇后问题要求:
在一个N×N的矩阵中,任意两个皇后不能同行、不能同列或不能位于同一条对角线上。
- 算法思路:
按照每一行对单个皇后位置进行遍历,此时限制条件转变为了不能同列或不能位于同一条对角线。
以此为限制条件实现回溯,当满足达到最后一行时输出当前结果。
- 代码实现:
#include <iostream> using namespace std; void Select(int **pos, int n, int num); int main (){ int num; //皇后数 cin >> num; int **pos; //皇后摆放矩阵 pos = new int *[num]; for(int i =0; i<num; i++){ pos[i] = new int [num]; for(int j =0; j<num; j++) pos[i][j]= 0; } Select(pos,1,num); } void Select(int **pos, int n, int num){ if(n<=num){ for(int i = 0; i<num; i++){ //每一行进行遍历 bool flag = false; for(int j = 1; j<n; j++){ if(pos[n-1-j][i] || ((i-j>=0)&&(pos[n-1-j][i-j])) || (i+j<num)&&(pos[n-1-j][i+j])){ //回溯条件,判断同一列 ||左上方 ||右上方 flag = true; break; } } if(!flag && n==num){ //最后一行输出结果 pos[n-1][i] = 1; for(int i = 0; i<num; i++){ for(int j = 0; j<num; j++){ cout << pos[i][j] << " "; } cout <<endl; } cout <<endl; pos[n-1][i] = 0; return; } if(!flag && n<num){ //无冲突判断下一皇后 pos[n-1][i] = 1; Select(pos,n+1,num); pos[n-1][i] = 0; } } } }
这篇关于回溯法-N皇后问题-C++算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升