`
美丽的小岛
  • 浏览: 309409 次
  • 性别: Icon_minigender_1
  • 来自: 大连
社区版块
存档分类
最新评论

位运算求解N皇后的过程

 
阅读更多

 8皇后可以用位运算来求,有点好奇的,不过,位运算这个强大的逻辑,没有怀疑,用了n为4的,对于太大的控制台放不下。 

#include<stdio.h>
#define N 4
int result = 0 ;
int count = 1 ;
int upperlim = (1 << N) -1 ;
void com(int row,int ld, int rd) ;
void print_bin(int n);
int main(){
    com(0,0,0) ;
   printf("结果为:%d",result) ;
    return 0 ;
}

void com(int row ,int ld , int rd){
    int pos,p ;
    printf("count = %d \nrow = ",count++) ;
    print_bin(row) ;
    printf(" ") ;
    printf("ld = ") ;
    print_bin(ld) ;
    printf(" ") ;
    printf("rd = ") ;
    print_bin(rd) ;
    printf("\n") ;
    if(row != upperlim){
        pos = upperlim & ~(row | ld | rd) ;
        printf("pos = ") ;
        print_bin(pos) ;
        printf("\n") ;
        while( pos != 0 ){
            p = pos & ( - pos ) ;
            pos = pos - p ;
            com(row + p, (ld + p) << 1 , (rd + p) >> 1) ;
        }
        printf("回溯\n") ;
    }else{
       result++ ;
       printf("第%d个解产生\n",result) ;
    }
}

void print_bin(int n){
   if(n < 2 ){printf("%d",n);}
    else{
        print_bin(n/2) ;
        printf("%d",n%2) ;
    }
}

 输出结果:

 
其实,想作一个图出看看效果,时间有限。
 

参考:http://www.matrix67.com/blog/archives/266

  • 大小: 14 KB
  • 大小: 4.8 KB
1
2
分享到:
评论

相关推荐

    n皇后问题(队列分支限界法)

    n皇后问题是一个经典的计算机科学问题,它在棋盘上放置n个皇后,要求任何两个皇后不能在同一行、同一列或同一斜线上。这个问题是回溯算法和分支限界法的良好应用实例,旨在展示如何在有限的搜索空间中找到所有可能的...

    c++代码运用回溯与位运算算法实现N-皇后问题

    本资源使用c++代码实现N-皇后问题并附上研究小论文,实现算法有:回溯法(递归),回溯法(递归)的镜像优化,回溯法(非递归),回溯法(非递归)的镜像优化,位运算算法,位运算算法的镜像优化。N-皇后问题是八皇后问题的...

    用栈求解n皇后问题-参考价值不大,需要的下.docx

    《用栈求解n皇后问题》 n皇后问题是一个经典的回溯算法问题,它要求在n×n的棋盘上放置n个皇后,使得皇后彼此之间不能在同一行、同一列或同一条对角线上。这个问题的目标是找出所有的可行解。在本文中,我们将探讨...

    c语言的N皇后算法

    1. 位运算优化:使用位运算代替传统的数组或列表来表示棋盘和皇后的位置,因为位运算通常比数组索引更快。 2. 剪枝:在搜索树的递归过程中,一旦某一行发现无法放置皇后,立即返回上一层,不再继续向下搜索。 3. ...

    Java编写的N皇后问题

    总结来说,Java编写的N皇后问题是一个涉及递归、回溯算法以及问题求解的经典示例。通过理解和实现这个解决方案,开发者不仅可以提升自己的编程技能,还能深入理解如何运用这些算法解决实际问题。在实际的软件开发中...

    分支限界法求皇后问题代码

    皇后问题,又称N皇后问题,是计算机科学领域中一个著名的问题。它要求在N×N的棋盘上放置N个皇后,使得任意两个皇后都无法在同一行、同一列或同一条对角线上。分支限界法是一种求解这类问题的有效算法,它结合了深度...

    n皇后\大数运算\二叉树等 北大工硕期末题

    2、 编程求解皇后问题。在m*m的棋盘上有n个皇后(n ≤ m),输出所有合法的皇后排列(即在任何一行、一列或一条对角在线,仅能放置一个皇后)。 3、 实现图书馆借书系统,其功能包括: (1) 申请新的图书证; (2...

    矩阵链乘和n皇后问题的程序和解题报告(随机法+回溯法)

    在计算机科学领域,矩阵链乘和n皇后问题是两个经典的算法问题,它们分别涉及到高效计算和问题求解策略。本文将详细解析这两个问题以及相应的解决方法。 首先,我们来看矩阵链乘。这是一个关于优化运算顺序的问题,...

    N皇后问题及深度优先算法.doc

    N皇后问题及深度优先算法 N皇后问题是一种经典的算法问题,它需要在 NxN 的棋盘上摆放 N 个皇后,使得每个皇后都不在同一行、同一列或同一斜线上。该问题可以使用深度优先算法来解决。 深度优先算法是一种搜索策略...

    回溯法-N皇后问题_N皇后回溯法C++_

    此外,为了提高效率,还可以考虑使用位运算来替代传统的数组操作,这在处理大棋盘时尤其有效。 总的来说,N皇后问题的回溯法C++实现是一个很好的学习案例,它不仅展示了如何运用回溯法解决复杂问题,还涉及到递归、...

    N-Queens:多机并行求解器的N皇后问题

    8 皇后问题在单机上的运算时间是毫秒级,有 92 个解,编程实现之(**注意:目前世界纪录是 N = 26, 研究 N-皇后问题的并行算法,写一个单机多线程程序,争取达到线性加速比(以 CPU 核数计)。再设法将算法扩展到多...

    回溯法解决n后问题

    回溯法是一种强大的算法策略,常用于解决组合优化问题,如经典的八皇后问题。在这个问题中,目标是在一个8x8的...理解和掌握回溯法不仅有助于解决n皇后问题,还能应用于其他类似的问题,如图的着色问题、数独求解等。

    算法设计——N后问题的回溯解法

    - 使用位运算来加速冲突检测。 - 采用剪枝技术减少无效的搜索路径。 #### 六、实际应用 N后问题不仅是一个经典的计算机科学问题,而且其背后的算法思想广泛应用于诸如排程、资源分配等实际场景中。例如,在硬件...

    罗马利亚度假问题和N皇后问题

    常见的解法有回溯法、深度优先搜索和位运算等,这些方法在理解和实现上都有其独特之处。 在处理这两个问题时,人工智能技术如搜索算法、约束满足、遗传算法、神经网络等都可能被用到。学习和理解这些问题的解决方案...

    数据结构高校电子教案(精)内附若干经典数据结构课题题解,如N皇后等

    解N皇后问题的过程中,我们可以学习到如何设计有效的约束条件,以及如何利用回溯法在遇到矛盾时优雅地撤回并尝试其他路径。 另一个提及的标签是“背包求解”,这通常指的是动态规划在背包问题中的应用。背包问题是...

    NQueens_Backtracking:回溯算法解决N皇后问题

    7. **效率优化**:在实现过程中,可以通过一些技巧来优化算法,比如利用位运算来快速检查行、列和对角线冲突,减少不必要的计算。 8. **代码结构**:通常,解决N皇后问题的Java代码会包含一个主类,一个用于表示...

    八皇后问题

    在1850年,弗朗西斯·高特(Franz Nauck)推广了这个问题,并且将其扩展到n皇后问题。八皇后问题要求将八个皇后放置在一个8×8的国际象棋棋盘上,使得任意两个皇后之间不能互相攻击。按照国际象棋规则,皇后可以沿着...

    huanghou.rar_queen

    下面我们将深入探讨N皇后问题的解决方案以及如何使用回溯法来求解。 首先,我们来看N皇后问题的定义。给定一个N×N的棋盘,我们希望在每一行都放一个皇后,但条件是任何两个皇后都不能在同一行、同一列或对角线上...

    3着色4皇后矩阵链快速排序公共子序列

    此问题扩展到n皇后问题,是经典的回溯算法应用实例,有助于理解递归和状态空间搜索。 3. **矩阵链相乘**: 矩阵链相乘是线性代数中的一个问题,涉及到多个矩阵的乘法,目标是最小化计算所需的乘法操作数。动态规划...

    回溯法实验报告解装载问题

    回溯法是一种基于试探性的深度优先搜索的算法,常用于解决约束满足问题。在这个实验报告中,回溯法...在实际编程中,可以考虑优化剪枝函数,提高搜索效率,例如使用位运算来快速检查行、列和对角线冲突,以减少计算量。

Global site tag (gtag.js) - Google Analytics