八皇后问题 ( C++ ) ( 递归 )

梦里梦外; 2022-05-21 10:11 197阅读 0赞

#include<iostream>  //八皇后问题递归方法
    using namespace std;
    
    int ways = 0;
    int a[8] = { -1,-1,-1,-1,-1,-1,-1,-1 };
    
    bool check(int row, int col) {     // 在row行，col列可以放置皇后吗？
    	for (int i = 0; i < row; i++)  // 判断同列、对角线是否有皇后冲突
    		if (a[i] == col || row - i == col - a[i] || row - i == a[i] - col)
    			return false;          // 返回0表示不能放，有冲突
    	return true;
    }
    
    void place(int n) {
    	if (n == 8) {                  // 递归函数的出口，从0到7行都已经放置完毕，
    		ways++;                    // 并且都是正确的，所以当n=8的时候，方案数加1
    		for (int i = 0; i < 8; i++)
    			cout << a[i] << "  ";  // 输出结果
    		cout << "\n-----------------------\n";
    		return;
    	}
    	else {
    		for (int i = 0; i < 8; i++)
    			if (check(n, i)) {
    				a[n] = i;          // 如果该行可以放的话，就放
    				place(n + 1);      // 放好之后，放下一行
    			}                      // 如果后几行全放完了，或者下一行没地方放，
    								   // 就返回这一层for循环，重新把这一行往下一列放，此处就是回溯
    	}
    }
    
    int main() {
    	place(0); cout << ways << endl;
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关递归-八皇后问题（回溯算法）

一：八皇后问题八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848 年提出：在 8×8 格的国际象棋上摆放八个皇

心已赠人/ 2022年11月07日 04:16/ 0 赞/ 235 阅读

相关八皇后问题（递归实现）

代码： ![Center][] ![Center 1][] ![Center 2][] ![Center 3][] [Center]: /i

阳光穿透心脏的1/2处/ 2022年06月10日 01:38/ 0 赞/ 179 阅读

相关递归应用：八皇后问题

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

朴灿烈づ我的快乐病毒、/ 2022年06月01日 11:28/ 0 赞/ 205 阅读

相关 JavaScript之八皇后问题（递归）

八皇后问题，是一个古老而著名的问题，该问题最早由国际西洋棋棋手马克斯·贝瑟尔(Max Bezzel)于1848年提出。八皇后问题的具体描述为：在8×8的国际象棋上摆放8个皇

冷不防/ 2022年06月01日 00:49/ 0 赞/ 211 阅读

相关八皇后问题 ( C++ ) ( 递归 )

include<iostream> //八皇后问题递归方法 using namespace std; int ways = 0; i

梦里梦外;/ 2022年05月21日 10:11/ 0 赞/ 198 阅读

相关【数据结构算法】递归：八皇后问题

八皇后八皇后问题就是说如下图所示的国际象棋的棋盘中，放入8个皇后，所谓皇后就是国际象棋中的一个角色，它的功能就是能够打掉与它同一行同一列同一斜排的棋子，并且打击距离是整

野性酷女/ 2022年05月21日 03:18/ 0 赞/ 221 阅读

相关八皇后问题（递归回溯算法详解+C代码）

为了理解“递归回溯”的思想，我们不妨先将4位皇后打入冷宫，留下剩下的4位安排进4x4的格子中且不能互相打架，有多少种安排方法呢？现在我们把第一个皇后放在第一个格子

ゝ一纸荒年。/ 2022年03月22日 15:12/ 0 赞/ 308 阅读

相关递归--八皇后

　　八皇后这个典的问题，是每个真正程序员必须经历过的。这也是我第二次来解决这个问题了，第一次应该是学数据结构那时候吧。这次写起来顺利多了，基本没遇到什么卡壳的地方。递归+回溯。

我不是女神ヾ/ 2021年12月17日 02:59/ 0 赞/ 332 阅读

相关用递归实现八皇后问题

定义一个数组下标是列值是皇后放置位置 package com.recursion; / @Auther: 大哥的叔 @Dat

╰+攻爆jí腚メ/ 2021年11月09日 08:34/ 0 赞/ 358 阅读

相关递归解决八皇后问题

一八皇后问题八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，

刺骨的言语ヽ痛彻心扉/ 2021年07月24日 23:08/ 0 赞/ 413 阅读