回溯法——求解N皇后问题

问题描述

 

    八皇后问题是十九世纪著名数学家高斯于1850年提出的。问题是：在8*8的棋盘上摆放8个皇后，使其不能互相攻击，即任意的两个皇后不能处在同意行，同一列，或同意斜线上。可以把八皇后问题拓展为n皇后问题，即在n*n的棋盘上摆放n个皇后，使其任意两个皇后都不能处于同一行、同一列或同一斜线上。

 

 

问题分析

 

    我们以最简单的4皇后问题分析,显然,为了使皇后不相互攻击,首先考虑每一行只能放一个皇后,我们以X[1,2,3….N]代表此问题的解数组,X[N]代表在第N行第X[N]列放了一个皇后,例如,X[2]=1代表在第2行第1列放了一个皇后.然后考虑,在第X[k]位上，什么时候会出现皇后相互攻击的情况？

问题解决

    大致描述：以四皇后为例，我们以一个表格来描述我们放置皇后的过程：

  

    

如上所示，一旦出现本行所有位置都不能放置皇后的情况时，我们要回溯到上一行，重新调整上一行的皇后的位置。

伪代码解读

       首先是判断是否可以放置皇后的代码：

 

      接下来是放置皇后的过程：

时间： 2024-10-31 22:40:59

回溯法——求解N皇后问题的相关文章

回溯法——求解0-1背包问题

         以前研究过一个简单的N皇后问题,对回溯法也有了个模糊的认识,大致理解就是:先一直做某件事,当完成某个条件时或者是触犯某个条件时,再返回到最近的一个类似还原点的地方.        在用回溯法求解0-1背包问题的时候,主要遇到三个相对难解决的问题:1,什么是界限函数:2,什么时候用它:3,回溯到哪儿.    什么是界限函数?         如下图:             当我们身在一棵搜索空间树中,站在一个K点举棋不定的时候,我们可以用它估算如果我们继续向下走,我们走完本段路

javascript递归回溯法解八皇后问题

  javascript递归回溯法解八皇后问题:           网上看到许多关于八皇后算法的文章,很少能看到使用javascript来实现的,今天就给大家使用javascript来解决下这个问题,有需要的小伙伴可以参考下. 下面给大家分享的是回溯法解八皇后, 带详细注解,这里就不多废话了. ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

struct-关于使用回溯法求解迷宫问题

问题描述 关于使用回溯法求解迷宫问题 #include using namespace std ; const int m = 4 , p = 4 ; struct offsets { int a , b ; char *dir ; }; offsets move[8] ; int Maze[m+2][p+2] ; int mark[m+2][p+2] ; int main (){ int i , j; int SeekPath (int x ,int y ) ; offsets move[8]

javascript递归回溯法解八皇后问题_javascript技巧

下面给大家分享的是回溯法解八皇后, 带详细注解,这里就不多废话了. function NQueens(order) { if (order < 4) { console.log('N Queens problem apply for order bigger than 3 ! '); return; } var nQueens = []; var backTracking = false; rowLoop: for (var row=0; row<order; row++) { //若出现ro

并行计算思考----回溯法求解数独问题

 1.Intel Parallel Studio 环境下的并行程序设计 书官方网站的详情页: http://www.wrox.com/WileyCDA/WroxTitle/Parallel-Programming-with-Intel-Parallel-Studio-XE.productCd-0470891653.html 可以下载相关代码 2.在使用并行计算来优化自己的串行程序之前,我们需要思考以下几个方面的问题 什么情况下需要并行? 并行能够带来多少性能的提升? 编码和调试的时间成本?

用试探回溯法解决N皇后问题

学校数据结构的课程实验之一. 数据结构:(其实只用了一个二维数组) 算法:深度优先搜索,试探回溯 需求分析: 设计一个在控制台窗口运行的"n皇后问题"解决方案生成器,要求实现以下功能: 由n*n个方块排成n行n列的正方形称为n元棋盘.如果两个皇后位于n元棋盘上的同一行.同一列或同一对角线上,则称它们在互相攻击.现要找出使棋盘上n个皇后互不攻击的布局. 编制程序解决上述问题,以n=6运行程序,输出结果. 算法解释: 首先试探当前行第一个可用的位置(列.对角线没有被占领),摆放皇后之后,试

java使用回溯法求解数独示例_java

复制代码 代码如下: import java.util.Calendar;import java.util.Date; public class Matrix {  private int matrix[][]; private long timeAfter=0;  private long timeBefore =0; public Matrix(int m[][]) {  matrix = new int[9][9];  for (int i=0; i<9 ; i++)   for(int

读书时间--回溯法浅析：逆向思维领略算法之美

下面将使用回溯思想解决若干经典问题并通过它们来说明使用回溯的基本思路 什么叫回溯法 回溯是一种比较简单.比较常用的搜索策略. 它的基本思想是假设某问题的解决步骤可能有N步,且每一步的解决方法又可能有M种,那么就按照某种顺序依次试探每一步中的各种方法,一旦某一步的所有方法都失效,那么就返回上一步继续试探上一步骤的其他M−1种方法.简而言之就是从一条路往前走,能进则进,不能进则退回来,换一条路再试. 通常用回溯法解决问题的一般步骤为:首先,定义一个解空间,它包含问题的解,也就是每一步所采用的各种方法

C++回溯法实例分析_C 语言

本文实例讲述了C++的回溯法,分享给大家供大家参考之用.具体方法分析如下: 一般来说,回溯法是一种枚举状态空间中所有可能状态的系统方法,它是一个一般性的算法框架. 解向量a=(a1, a2, ..., an),其中每个元素ai取自一个有限序列集Si,这样的解向量可以表示一个排列,其中ai是排列中的第i个元素,也可以表示子集S,其中ai为真当且仅当全集中的第i个元素在S中:甚至可以表示游戏的行动序列或者图中的路径. 在回溯法的每一步,我们从一个给定的部分解a={a1, a2, ..., ak}开始