n后问题（回溯法)

青旅半醒 2022-06-18 01:56 165阅读 0赞

//
    //Description: N后问题（回溯法）
    //
    #include <iostream>
    #include <math.h>
    #include <iomanip>
    using namespace std;
    
    int n;//皇后个数
    int x[100];//当前解
    static long sum;//当前已找到的可行方案数
    
    
    bool place(int k)
    {
    	for (int j = 1; j<k; j++)
    	{
    		if ((abs(k - j) == abs(x[j] - x[k])) || (x[j] == x[k]))
    			return false;
    	}
    	return true;
    }
    
    void backtrack(int t)
    {
    	if (t>n)
    	{
    		sum++;
    		cout << " 第 " << setw(2) << sum << "  个可行解：";
    		for (int i = 1; i <= n; i++)
    		{
    			cout << x[i] << "  ";
    		}
    		cout << endl;
    	}
    	else
    	for (int i = 1; i <= n; i++)
    	{
    		x[t] = i;
    		if (place(t))
    			backtrack(t + 1);
    	}
    }
    
    long nQueen(int nn)
    {
    	n = nn;
    	sum = 0;
    	for (int i = 1; i <= n; i++)
    	{
    		x[i] = 0;
    	}
    	backtrack(1);
    	return sum;
    }
    
    void main()
    {
    	cout << "\n\t===============N后问题（回溯法）=================\n";
    	cout << "Please enter the numbers of Queens:" << endl;
    	cin >> n;
    	nQueen(n);
    
    	cout << "欲在" << n << "×" << n << "的棋盘上放置满足条件的" << n << "个皇后，可以得到解的个数为 " << sum << endl;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 DFS + 回溯法：N皇后问题

DFS + 回溯法：N皇后问题问题： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text

骑猪看日落/ 2023年10月06日 16:55/ 0 赞/ 48 阅读

相关 [LeetCode] 51. N-Queens - N皇后问题的解法-回溯法

[\[LeetCode\] 51. N-Queens][LeetCode_ 51. N-Queens] Problem The n-queens puzzle

秒速五厘米/ 2023年06月23日 09:56/ 0 赞/ 46 阅读

相关 N 皇后问题 | 回溯：N排列

> n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 > > 上图为 8 皇后问题的一种解法。 > > 给定一个整数 n，返

﹏ヽ暗。殇╰゛Y/ 2023年03月12日 10:58/ 0 赞/ 66 阅读

相关回溯法-N皇后问题

一、N皇后问题 n皇后问题：要求在一个n×n的棋盘上放置n个皇后，使得任意两个皇后不在同一行或同一列或同一斜线上。二、回溯法回溯法是一类非常重要的算法设计方法

- 日理万妓/ 2022年11月17日 05:08/ 0 赞/ 250 阅读

相关【LeetCode】回溯问题：N 皇后问题

N 皇后 [51. N 皇后][51. N] 难度困难745收藏分享切换为英文接收动态反馈 n 皇后问题研究的是如何将 `n` 个皇后放置在 `n×n` 的棋盘

小鱼儿/ 2022年10月29日 09:13/ 0 赞/ 205 阅读

相关算法设计与分析——回溯法——n皇后问题

一、什么是N皇后问题？在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于再n×n的棋盘上

灰太狼/ 2022年10月20日 12:15/ 0 赞/ 241 阅读

相关 n后问题(回溯法)

一.问题描述: 在n\n格子上放置n个皇后, 按照国际象棋规矩不可让皇后相互攻击, 即如何两个皇后不放在同一列同一行同一斜线上. 二.算法设计: 将问题转化为逐行放置皇后

末蓝、/ 2022年08月18日 02:13/ 0 赞/ 194 阅读

相关 n后问题（回溯法)

// //Description: N后问题（回溯法） // include <iostream> include <math.h>

青旅半醒/ 2022年06月18日 01:56/ 0 赞/ 166 阅读

相关 C程序-回溯法（递归形式）解决01背包和n后问题

1. 0-1背包问题 n=3的0/1背包问题，设物品质量w=\{18,14,16\}; 物品价值v=\{48,30,30\}; 背包容量c=30. 程序如下所示：

分手后的思念是犯贱/ 2022年05月26日 00:58/ 0 赞/ 188 阅读

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

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

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