回朔法延伸出来的八皇后问题

墨蓝 2022-08-13 13:44 33阅读 0赞

八皇后的代码如下：

#include<iostream>
    using namespace std;
    
    void fun(int,int[],int);
    bool isPlace(int[],int,int);
    void display(int[],int);
    int main() {
    	int n;
    	
    	while(cin>>n) {
    		int *p = new int[n+1];
    		fun(n,p,1);
    	}
    	return 0;
    }
    
    void fun(int n,int a[],int temp) {
    	if(temp==n+1) {
    		/*经典回朔法的输出
    		for(int i=1;i<=n;i++) {
    			cout<<a[i];
    		}
    		cout<<endl;
    		*/
    		display(a,n);
    		return ;
    	}
    	for(int i=1;i<=n;i++) {
    		a[temp] = i;
    		if(isPlace(a,i,temp))//加了这个条件，判断是否符合八皇后的条件才调用递归
    			fun(n,a,temp+1);
    		/*这段代码也是用回朔法输出类似000 001 010这种二进制的所有情况
    		a[temp] = 0;
    		fun(n,a,temp+1);
    		a[temp] = 1;
    		fun(n,a,temp+1);
    		*/
    	}
    }
    
    bool isPlace(int a[],int i,int temp) {
    	for(int j=1;j<temp;j++) {
    		if((a[j]==i)) {
    			return false;
    		}
    		else if((j+a[j]==temp+i)||(j-a[j]==temp-i)) {
    			return false;
    		}
    	}
    
    	return true;
    }
    
    void display(int a[],int n) {
    	for(int i=1;i<=n;i++) {
    		for(int j=1;j<=n;j++) {
    			if(a[i]==j) {
    				cout<<"1 ";
    			}
    			else cout<<"0 ";
    		}
    		cout<<endl;
    	}
    	cout<<endl;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，33人围观）

还没有评论，来说两句吧...

相关阅读

相关回朔法延伸出来的八皇后问题

八皇后的代码如下： include<iostream> using namespace std; void fun(int,int[],in

墨蓝/ 2022年08月13日 13:44/ 0 赞/ 34 阅读

相关回溯法：八皇后问题

八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横

蔚落/ 2022年08月08日 12:45/ 0 赞/ 224 阅读

相关回朔法浅析

1、概念回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯

小鱼儿/ 2022年07月28日 06:27/ 0 赞/ 166 阅读

相关八皇后问题(回溯法)

问题描述：在8\8的棋盘上，放置8个皇后，使他们互相不攻击；解析：进行逐行放置，皇后肯定不会进行横向攻击，因此只需检查纵向和斜向是否会进行攻击即可代码： C

曾经终败给现在/ 2022年06月12日 12:07/ 0 赞/ 230 阅读

相关八皇后问题

枚举法 include<iostream> using namespace std; int a[9]; int check(int n,

蔚落/ 2022年06月06日 00:38/ 0 赞/ 230 阅读

相关八皇后问题（回溯法）

问题描述 ![70][] 在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上（与水平行轴成45°或135°），问有多少

小灰灰/ 2022年06月05日 12:20/ 0 赞/ 227 阅读

相关回溯法（八皇后）

回溯法(探索与回溯法)是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再

谁践踏了优雅/ 2022年06月05日 08:56/ 0 赞/ 273 阅读

相关八皇后问题

　在国际象棋中，皇后是最强大的一枚棋子，可以吃掉与其在同一行、列和斜线的敌方棋子.八皇后问题是这样一个问题：将八个皇后摆在一张8\8的国际象棋棋盘上，使每个皇后都无法吃掉别的皇

Bertha 。/ 2022年05月18日 05:58/ 0 赞/ 226 阅读

相关回溯法——八 / N 皇后问题

回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点

ゝ一世哀愁。/ 2022年04月13日 05:39/ 0 赞/ 369 阅读

相关八皇后问题

八皇后问题，以国际象棋为背景：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任意两个皇后都不能处于

叁歲伎倆/ 2021年09月25日 15:34/ 0 赞/ 462 阅读