回溯法 8皇后

2024-06-21 04:58
文章标签 皇后 回溯

本文主要是介绍回溯法 8皇后,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

问题太经典,就不描述问题了:

public class HuangHou8 {static int n=8;static int tot=0;static int[] C;static int[][] vis=new int[3][16];public static void main(String[] args) {tot=0;C=new int[8];search(0);System.out.println(tot);tot=0;C=new int[8];search2(0);System.out.println(tot);}public static void search(int cur){if(cur==n){tot++;for (int i = 0; i < C.length; i++) {System.out.print(C[i]+"  ");}System.out.println();}else{for (int i = 0; i < n; i++) {int ok=1;C[cur]=i;for (int j = 0; j < cur; j++) {if(C[cur]==C[j]||cur-C[cur]==j-C[j]||cur+C[cur]==j+C[j]){ok=0;break;}}if(ok==1){search(cur+1);}}}}public static void search2(int cur){if(cur==n){tot++;}else{for (int i = 0; i < n; i++) {if(vis[0][i]==0&&vis[1][cur+i]==0&&vis[2][cur-i+n]==0){C[cur]=i;vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=1;search2(cur+1);vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=0;}}}}
}


这篇关于回溯法 8皇后的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1080268

相关文章

题目1254:N皇后问题

题目1254:N皇后问题 时间限制:1 秒 内存限制:128 兆 特殊判题:否 题目描述: N皇后问题,即在N*N的方格棋盘内放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在同一斜线上。因为皇后可以直走,横走和斜走如下图)。 你的任务是,对于给定的N,求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入

回溯——9.全排列

力扣题目链接 给定一个 没有重复 数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3]输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 解题思路 问题建模:题目要求给出一个数组的所有排列组合,属于典型的全排列问题,这可以用回溯法来解决。回溯法通过递归的方式,依次将数组中的每个元素放入排列中,直到生成

代码训练营 Day26 | 47.排序II | 51. N-皇后 |

47.排序II 1.跟46题一样只不过加一个树层去重 class Solution(object):def backtracking(self,nums,path,result,used):# recursion stopif len(path) == len(nums):# collect our setresult.append(path[:])return for i in range(

风控系统之指标回溯,历史数据重跑

个人博客:无奈何杨(wnhyang) 个人语雀:wnhyang 共享语雀:在线知识共享 Github:wnhyang - Overview 回顾 默认你已经看过之前那篇风控系统指标计算/特征提取分析与实现01,Redis、Zset、模版方法。 其中已经介绍了如何利用redis的zset结构完成指标计算,为了方便这篇文章的介绍,还是在正式开始本篇之前回顾一下。 时间窗口 zset

165-Stamps【回溯】

回溯 给h和k的意思是在k种邮票中选h个邮票 基本的连续邮资问题 15226160 165 Stamps Accepted C++ 0.062 2015-03-27 07:21:37 #include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn = 2

JAVA学习-练习试用Java实现“N皇后 II”

问题: n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。 给定一个整数 n ,返回 n 皇后问题不同的解决方案的数量。 示例 1: 输入:n = 4 输出:2 解释:如上图所示,4 皇后问题存在两个不同的解法。 示例 2: 输入:n = 1 输出:1 提示: 1 <= n <= 9 皇后彼此不能相互攻击,也就是说:任何两个皇后都不能处于同

回溯——8.递增子序列

力扣题目链接 给定一个整型数组, 你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是2。 示例: 输入: [4, 6, 7, 7]输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]] 说明: 给定数组的长度不会超过15。数组中的整数范围是 [-100,100]。给定数组中

【代码随想录|回溯part04】

代码随想录|回溯part04 1、46.全排列2、47.全排列 II3.问题 总结 python 1、46.全排列 46.全排列 class Solution:def permute(self, nums):result = []self.backtracking

代码随想录算法训练营第十九天| 回溯理论、77. 组合、216. 组合总和Ⅲ、17. 电话号码的字母组合

今日内容 回溯的理论基础leetcode. 77 组合leetcode. 216 组合总和Ⅲleetcode. 17 电话号码的字母组合 回溯理论基础 回溯法也叫回溯搜索法,它是一种搜索的方式,而且只要有递归就会有回溯,回溯就是递归的副产品。 回溯说到底并不是什么非常高深的搜索方式,本质上仍然是穷举,穷举所有可能然后选择出我们要的答案。剪枝会使回溯法更加高效一点,但改变不了回溯本质就是穷举

笔试,牛客.kotori和n皇后​,牛客.AOE还是单体

目录 牛客.kotori和n皇后​编辑 牛客.AOE还是单体 牛客.kotori和n皇后  想起来,我之前还写过n皇后的题,但是这个我开始只能想到暴力解法 判断是不是斜对角线,联想y=x+b和y=-x+b,假如在一条线上,那么他们的x和y会对应成比例,这个扫描+判断是一个O(n^2)的操作。 import java.util.*; import java.io.*;//