N皇后问题使用stack的非递归实现
package com.xx.dataStructure.stack; class Point { int x; int y; int value; Point(int x ,int y){ this(x,y,0); } Point(int x ,int y,int value){ this.x = x; this.y = y; this.value = value; } @Override public String toString(){ return "(" + x + "," + y + ")"; } } //求解N皇后问题的所有解 public class Queen { private int solution = 0; private int n; private Point [][] points = null; public Queen(int n) { assert (n > 0); this.n = n; this.solution = 0; points = new Point[n][n]; for(int i =0; i<n ; ++i){ for(int j =0; j<n ; ++j){ points[i][j] = new Point(i,j); } } } //point的行、列、对角线的点value +1 public static void add(Point[][] points,Point point){ //列 for(int i = 0; i < points.length ; i++ ){ points[i][point.y].value += 1; } //行 for(int i = 0; i < points.length ; i++ ){ points[point.x][i].value += 1; } //对角线 for( int i= point.x, j = point.y ;( i < points.length && j < points.length); ++i , ++j ){ points[i][j].value += 1; } for( int i= point.x, j = point.y ;( i >= 0 && j < points.length); --i , ++j ){ points[i][j].value += 1; } for( int i= point.x, j = point.y ;( i < points.length && j >= 0); ++i , --j ){ points[i][j].value += 1; } for( int i= point.x, j = point.y ;( i >= 0 && j >= 0); --i , --j ){ points[i][j].value += 1; } point.value = 1; } public static void minus(Point[][] points,Point point){ //列 for(int i = 0; i < points.length ; i++ ){ points[i][point.y].value -= 1; } //行 for(int i = 0; i < points.length ; i++ ){ points[point.x][i].value -= 1; } //对角线 for( int i= point.x, j = point.y ;( i < points.length && j < points.length); ++i , ++j ){ points[i][j].value -= 1; } for( int i= point.x, j = point.y ;( i >= 0 && j < points.length); --i , ++j ){ points[i][j].value -= 1; } for( int i= point.x, j = point.y ;( i < points.length && j >= 0); ++i , --j ){ points[i][j].value -= 1; } for( int i= point.x, j = point.y ;( i >= 0 && j >= 0); --i , --j ){ points[i][j].value -= 1; } point.value = 0; } // 能否使用非递归算法 回溯法来使时间复杂度降为多项式 public static void solveProblem0(Queen queen) { Stack<Point> stack = new Stack<Point>(100); System.out.println("开始求解"+queen.n+"皇后问题。"); Point [][] points = queen.points; int [] tags = new int[queen.n]; for(int i = 0; i < queen.n; i ++){ tags[i] = -1; } int k = 0; try { for (int i = 0; i < queen.n; ++i) { Point currentPoint = points[0][i]; stack.push(currentPoint); add(points,currentPoint); k++; while(!stack.isEmpty()){ if (k == queen.n ){ queen.solution++; stack.traverse(); Point point = stack.pop(); minus(points, point); k--; }else { Point nextP = findNextPoint(points,tags,k); if (nextP != null){ stack.push(nextP); add(points,nextP); k++; }else { Point point = stack.pop(); minus(points, point); tags[k--] = -1; } } } } } catch (Exception e) { e.printStackTrace(); } } public static Point findNextPoint(Point [][] points,int[] tags ,int k){ Point p = null; for(int q = tags[k] + 1 ; q < points.length; q++){ tags[k]++; if (points[k][q].value == 0){ p = points[k][q]; break; } } return p; } public static void main(String[] args) { solveProblem0(new Queen(1)); solveProblem0(new Queen(2)); solveProblem0(new Queen(3)); solveProblem0(new Queen(4)); solveProblem0(new Queen(5)); solveProblem0(new Queen(6)); } }
程序输出
开始求解1皇后问题。 (0,0), 开始求解2皇后问题。 开始求解3皇后问题。 开始求解4皇后问题。 (0,1),(1,3),(2,0),(3,2), (0,2),(1,0),(2,3),(3,1), 开始求解5皇后问题。 (0,0),(1,2),(2,4),(3,1),(4,3), (0,0),(1,3),(2,1),(3,4),(4,2), (0,1),(1,3),(2,0),(3,2),(4,4), (0,1),(1,4),(2,2),(3,0),(4,3), (0,2),(1,0),(2,3),(3,1),(4,4), (0,2),(1,4),(2,1),(3,3),(4,0), (0,3),(1,0),(2,2),(3,4),(4,1), (0,3),(1,1),(2,4),(3,2),(4,0), (0,4),(1,1),(2,3),(3,0),(4,2), (0,4),(1,2),(2,0),(3,3),(4,1), 开始求解6皇后问题。 (0,1),(1,3),(2,5),(3,0),(4,2),(5,4), (0,2),(1,5),(2,1),(3,4),(4,0),(5,3), (0,3),(1,0),(2,4),(3,1),(4,5),(5,2), (0,4),(1,2),(2,0),(3,5),(4,3),(5,1),
相关推荐
Python数据结构预算法之栈(Stack)的实现与应用 数据结构预算法.pdf
简述N皇后问题的方法,适合大家查看! void make(int l) //递归搜索以stack[l]为初结点的所有路径 { int i,j; //子结点个数 if (l==n+1) { total=total+1; //路径数+1 for(i=1;i<=n;i++) printf("%-3d",stack...
用c语言编写的一个stack程序,实现了进栈,出栈,删除栈顶元素等功能。
本文实例讲述了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法。分享给大家供大家参考,具体如下: /*求二叉树叶子节点个数 -- 采用递归和非递归方法 经调试可运行源码及分析如下: ***/ #include #...
数据结构 严蔚敏 栈 stack
int stacksize; //当前已分配的存储空间 } SqStack; Status InitStack(SqStack &S) Status GetTop(SqStack &S, BiTree &e) Status Push(SqStack &S, BiTree e) Status Pop(SqStack &S,BiTree &e) Status ...
数据结构实验用堆栈实现计算器,大二数据结构实验
数据结构中stack的详细编码及使用 改代码中包含了stack的初始,添加,删除,修改,销毁以及一些简单应用的代码
这个是用c语言实现的一个stack类数据结构的操作。对c语言堆栈更加深入的认识!
该代码使用了std::stack来实现栈数据结构,并使用递归回溯的方式求解n皇后问题。在函数isSafe中,用于检查当前位置是否安全。如果在同一列、同一条对角线或反对角线上存在其他皇后,则该位置不安全。 函数...
基于python的数据结构代码实现-栈Stack
内容包含常见基本数据结构实现(C语言版)如各自排序、链表、栈、队列、各种树以及应用、图算法、字符串匹配算法、回溯、并查集等 以及包含各个数据结构常见算法题的解答(C语言版) bitTree 二叉搜索树 ...
java数据结构 ArrayList、Stack、Map,为提高效率,未做边界判断(由开发人员保证逻辑上不会出现越界),实现了添加和查询的功能,无修改删除功能
鉴于python做为脚本语言的简洁性,这里写一篇小文章用python实现二叉树,帮助一些对数据结构不太熟悉的人快速了解下二叉树。本文主要通过python以非递归形式实现二叉树构造、前序遍历,中序遍历,后序遍历,层次遍历...
数据结构基于C++语言程序开发的树的非递归先序遍历 if (p->rchild != NULL)/* 右孩子入栈 */ { top++; stack[top] = p->rchild; } if (p->lchild != NULL)/* 左孩子入栈 */ { top++; stack[top] = p->...
2. 利用教材中的Stack类,为其设计外部函数(非成员函数)实现下面delete_all功能,必要时可以使用临时的Stack对象。编写主函数测试delete_all函数,栈元素设定为字符类型即可。 template void delete_all(Stack<T>...
第二部分 数据结构 第3章 数据描述 75 3.1 引言 75 3.2 线性表 76 3.3 公式化描述 77 3.3.1 基本概念 77 3.3.2 异常类NoMem 79 3.3.3 操作 79 3.3.4 评价 83 3.4 链表描述 86 3.4.1 类ChainNode 和Chain 86 3.4.2 ...
Stack Stack的实现
数据结构实例应用(包含源代码) 一、停车场管理 /*停车场管理队列实现,离开时间比进入时间早的情况没做处理*/ #include "consts.h" #define MAXNUM 2 /*车库容量*/ #define price 0.05 /*每车每分钟费用*/ typedef ...
数据结构_stack_source