8皇后问题的解法实例代码

代码如下:

#include <stdio.h>

#define MAX 200
#define Empty 0
#define Full 1
#define N 8

unsigned char qipan[N][N][N]={MAX};//初始化8张棋盘表示每下一步的
void input(int i);
int count = 0;

int main()
{
    input(0);
    getchar();
    return 0;
}
void input(int i)
{
    int x=0,y=0;
    int p=0,q=0;
    int flag = 0;
    //初始化当前棋盘
    if(i!=0)
    {
        for(x=0;x<N;x++)
        {
            for(y=0;y<N;y++)
            {
                qipan[i][x][y] = qipan[i-1][x][y];
            }
        }
    }
    else
    {
        for(x=0;x<N;x++)
        {
            for(y=0;y<N;y++)
            {
                qipan[i][x][y] = MAX;
            }
        }
    }
    //递归结束
    if(i==N)
    {
        count++;
        for(x=0;x<N;x++)
        {
            for(y=0;y<N;y++)
            {
                printf("%d ",qipan[i-1][x][y]);
            }
            printf("\n");
        }
        printf("%d\n",count);
        return;
    }

for(y=0;y<N;y++)
    {
        //找到空位
        if(qipan[i][i][y]==MAX)
        {
            //另其为1
            qipan[i][i][y] = 1;
            //前后左右上下都置为0
            for(p=0;p<N;p++)
            {
                for(q=0;q<N;q++)
                {
                    if(q==y||p==i||(p-i)==(q-y)||(p-i)==(y-q))
                        if(qipan[i][p][q] == MAX)
                            qipan[i][p][q] = 0;
                }
            }
            if(flag != -1)
            {
                //找下一个
                input(i+1);
            }
            //将棋盘变回本层原样
            for(p=0;p<N;p++)
            {
                for(q=0;q<N;q++)
                {
                    if(i!=0)
                    qipan[i][p][q] = qipan[i-1][p][q];
                    else
                    qipan[i][p][q] = MAX;
                }
            }
            flag =0;
        }
    }
    //找不到空位结束
    return;
}

赞 (0)

相关推荐

  • C++实现图的邻接矩阵存储和广度、深度优先遍历实例分析

    C++实现图的邻接矩阵存储和广度、深度优先遍历实例分析

    本文实例讲述了C++实现图的邻接矩阵存储和广度.深度优先遍历的方法.分享给大家供大家参考.具体如下: 示例:建立如图所示的无向图 由上图知,该图有5个顶点,分别为a,b,c,d,e,有6条边. 示例输入(按照这个格式输入): 5 6 abcde 0 1 1 0 2 1 0 3 1 2 3 1 2 4 1 1 4 1 输入结束(此行不必输入) 注:0 1 1表示该图的第0个顶点和第1个定点有边相连,如上图中的a->b所示       0 2 1表示该图的第0个顶点和第2个定点有边相连,如上图中的a

  • C语言通过深度优先搜索来解电梯问题和N皇后问题的示例

    N皇后问题 问题描述: 在n×n格的棋盘上放置彼此不受攻击的n个皇后.按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子.n后问题等价于再n×n的棋盘上放置n个皇后,任何2个皇后不妨在同一行或同一列或同一斜线上. 需求输入: 给定棋盘的大小n (n ≤ 13) 需求输出: 输出有多少种放置方法. #include <stdio.h> #include <math.h> #define MAX 101 int total = 0; char m[MAX][MAX

  • 深入N皇后问题的两个最高效算法的详解

    深入N皇后问题的两个最高效算法的详解

    N皇后问题是一个经典的问题,在一个N*N的棋盘上放置N个皇后,每行一个并使其不能互相攻击(同一行.同一列.同一斜线上的皇后都会自动攻击).一. 求解N皇后问题是算法中回溯法应用的一个经典案例回溯算法也叫试探法,它是一种系统地搜索问题的解的方法.回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试.在现实中,有很多问题往往需要我们把其所有可能穷举出来,然后从中找出满足某种要求的可能或最优的情况,从而得到整个问题的解.回溯算法就是解决这种问题的"通用算法",有&qu

  • C++实现八皇后问题的方法

    本文实例展示了C++实现八皇后问题的方法,是数据结构与算法中非常经典的一个算法.分享给大家供大家参考之用.具体方法如下: 一般在八皇后问题中,我们要求解的是一个8*8的国际象棋棋盘中,放下8个皇后且互相不能攻击的排列总数.皇后的攻击范围为整行,整列,以及其斜对角线. 由于皇后的攻击范围特性,注定我们每行只能放下一个皇后,于是我们要做的只是逐行放下皇后.八皇后问题是回溯法的典型问题.这里我们用的方法很简单: 从第一行开始逐个检索安全位置摆放皇后,一旦有安全位置则考虑下一行的安全位置.如果发现某行没

  • 八皇后问题的相关C++代码解答示例

    八皇后问题的相关C++代码解答示例

    八皇后问题即指在一个8*8的棋盘上放置8个皇后,不允许任何两个皇后在棋盘的同一行.同一列和同一对角线上.关键字:递归.上溯.通用技巧: 经观察发现,对8 x 8的二维数组上的某点a[i][j](0<=i,j<=7) 其主对角线(即左上至右下)上的每个点的i-j+7的值(范围在(0,14))均相等: 其从对角线(即右上至左下)上的每个点的i+j的值(范围在(0,14))均相等: 且每个主对角线之间的i-j+7的值均不同,每个从对角线之间的i-j+7的值亦不同: 如a[3][4]: 主:3-4+7

  • 八皇后问题实现代码分享

    main.cpp 复制代码 代码如下: #include<iostream>#include<cstring> using namespace std; const int N = 7; int count = 0; void QueenPrint(int LayOut[N][N])  //打印结果{ cout<<"第"<<++count<<"种布局:"<<endl; for(int i = 0

  • c++递归实现n皇后问题代码(八皇后问题)

    还是先来看看最基础的8皇后问题: 在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 扩展到N皇后问题是一样的.一看,似乎要用到二维数组.其实不需要.一维数组就能判断,比如Arr[i],就可以表示一个元素位于第i行第Arr[i]列--应用广泛的小技巧.而且在这里我们不用考虑去存储整个矩阵,如果Arr[i]存在,那么我们在打印的时候,打印到皇后位置的时候输出1,非皇后位输出0即可. 这种思路的实现方式网上大把,包括前面提到的那

  • C++深度优先搜索的实现方法

    C++深度优先搜索的实现方法

    本文实例讲述了图的遍历中深度优先搜索的C++实现方法,是一种非常重要的算法,具体实现方法如下: 首先,图的遍历是指从图中的某一个顶点出发,按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次.注意到树是一种特殊的图,所以树的遍历实际上也可以看作是一种特殊的图的遍历.图的遍历主要有两种算法:广度优先搜索(Breadth-First-Search)和深度优先搜索(Depth-First-Search). 一.深度优先搜索(DFS)的算法思想 深度优先搜索算法所遵循的搜索策略是尽可能"深&

  • C语言实现图的遍历之深度优先搜索实例

    DFS(Depth-First-Search)深度优先搜索算法是图的遍历算法中非常常见的一类算法.分享给大家供大家参考.具体方法如下: #include <iostream> #include <algorithm> #include <iterator> using namespace std; #define MAX_VERTEX_NUM 10 struct Node { int adjvex; struct Node *next; int info; }; typ

  • 8皇后问题的解法实例代码

    复制代码 代码如下: #include <stdio.h> #define MAX 200#define Empty 0#define Full 1#define N 8 unsigned char qipan[N][N][N]={MAX};//初始化8张棋盘表示每下一步的void input(int i);int count = 0; int main(){    input(0);    getchar();    return 0;}void input(int i){    int x

  • Java编程数组中最大子矩阵简便解法实现代码

    Java编程数组中最大子矩阵简便解法实现代码

    本文研究的主要是Java编程数组中最大子矩阵的相关内容,具体介绍如下. 遇到一个好人,可以改变一生:遇到一本好书,又何尝不是呢? 最近在翻阅 左程云先生的<程序员代码面试指南–IT名企算法与数据结构题目最优解>时就非常的有感悟.建议有这方面爱好的博友,也去观摩观摩. 书中讲解的基于栈的数组的最大矩阵的算法很经典,但是博主能力有限,没能彻底的领悟该算法的精髓,但是根据这个思想,博主想出了一种简易的应对该类问题的算法,现概述如下. 核心思想 先来看一张图吧,我们就可以大致的理解了. 如图,每一个轮

  • python使用pandas实现数据分割实例代码

    本文研究的主要是Python编程通过pandas将数据分割成时间跨度相等的数据块的相关内容,具体如下. 先上数据,有如下dataframe格式的数据,列名分别为date.ip,我需要统计每5s内出现的ip,以及这些ip出现的频数. ip date 0 127.0.0.21 15/Jul/2017:18:22:16 1 127.0.0.13 15/Jul/2017:18:22:16 2 127.0.0.11 15/Jul/2017:18:22:17 3 127.0.0.11 15/Jul/2017

  • Angularjs2不同组件间的通信实例代码

    AngualrJs2官方方法是以@Input,@Output来实现组件间的相互传值,而且组件之间必须父子关系,下面给大家提供一个简单的方法,实现组件间的传值,不仅仅是父子组件,跨模块的组件也可以实现传值 /** *1.定义一个服务,作为传递参数的媒介 */ @Injectable() export class PrepService{ //定义一个属性,作为组件之间的传递参数,也可以是一个对象或方法 profileInfo: any; } /** *2.传递参数的组件,我这边简单演示,直接就在构

  • Angular动态添加、删除输入框并计算值实例代码

    Angular动态添加.删除输入框并计算值实例代码 摘要: 在学习群中交流时,有人分享了一个动态添加输入框的方法,我在其基础上进行了一些改进 这个功能本身并不复杂,但还是要注意,每个ng-model的对象必须是不同的,这样才能把它们分隔开. 下面是完整代码: JS: angular.module("myApp",[]) .controller("inputController",function($scope){ $scope.items=[]; //初始化数组,以

  • 正则表达式匹配(URL、电话、手机、邮箱)的实例代码

    正则表达式,又称规则表达式.(英语:Regular Expression,在代码中常简写为regex.regexp或RE),计算机科学的一个概念.正则表通常被用来检索.替换那些符合某个模式(规则)的文本.下面通过实例代码给大家介绍正则表达式匹配(URL.电话.手机.邮箱)的实例代码,一起看看吧! 废话不多说了,直接给大家贴代码了,具体代码如下所示: <!DOCTYPE html> <html lang="en"> <head> <meta ch

  • JS实现分页浏览横向图片(类轮播)实例代码

    昨天朋友问我怎么用js实现分页浏览横向图片功能,其实实现代码很简单的,下面小编给大家带来了具体实现代码,代码如下所示: common.js function $(id) { return document.getElementById(id); } function $_tag(tag) { return document.getElementsByTagName(tag); } index.html <!DOCTYPE html> <html lang="en"&g

  • Ajax邮箱、用户名唯一性验证实例代码

    废话不多说了,直接给大家贴代码了,具体代码如下所示: <script type="text/javascript"> $(function () { $("#txtEmail").blur(function () { $.ajax({ type: "post", url: "reg.ashx?email=" + $.trim($("#txtEmail").val()) + "&

  • Django中使用jquery的ajax进行数据交互的实例代码

    Django中使用jquery的ajax进行数据交互的实例代码

    jquery框架中提供了$.ajax.$.get.$.post方法,用于进行异步交互,由于Django中默认使用CSRF约束,推荐使用$.get 示例:实现省市区的选择 最终实现效果如图: 将jquery文件拷贝到static/js/目录下 打开booktest/views.py文件,定义视图area1,用于显示下拉列表 #提供显示下拉列表的控件,供用户操作 def area1(request): return render(request,'booktest/area1.html') 打开bo

  • jQuery完成表单验证的实例代码(纯代码)

    废话不多说了,直接给大家贴代码了,具体代码如下所示: <!doctype html> <head> <meta charset=utf-8" /> <title>表单验证</title> <link href="css/style1.css" rel="external nofollow" rel="stylesheet" type="text/css"

随机推荐