皇后问题之C#版（非递归）

递归|问题

 
/*
 *Author:Junyi Sun @CCNU
* E-mail:fxsjy@yahoo.com.cn
*/

using System;
namespace sunjoy
{
    public class Queen
    {
        public static int Main()
        {
            int board_size = 0,x=0,y=0;//棋盘大小,当前行,当前列
            uint solution_count = 0;   //皇后摆放方案的个数
            int[] rows, cols, slot1, slot2, x2y;//行占用情况，列占用情况，“/”状斜线占用情况，“\”状斜线占用情况，皇后坐标
            DateTime t_start, t_end;
           
            Console.WriteLine("请输入棋盘的大小");
            try
            {
                board_size = Convert.ToInt32(Console.ReadLine());
                if (board_size <= 0)
                {
                    Console.WriteLine("非法数据");
                    return -1;
                }
            }
            catch (Exception e) { Console.WriteLine("发生异常" + e.Message); };

            rows = new int[board_size];
            cols = new int[board_size];
            slot1 = new int[board_size * 2 - 1];
            slot2 = new int[board_size * 2 - 1];
            x2y = new int[board_size];

            for (int i = 0; i < board_size; i++)
                x2y[i] = -1;   //坐标初始化都为-1
            t_start = DateTime.Now;
            while (true)
            {
                for (y = x2y[x]+1; y < board_size; y++)
                    if (rows[x] == 0 && cols[y] == 0 && slot1[x + y] == 0 && slot2[x - y + board_size - 1] == 0)
                        break;

                if (y < board_size)
                {
                    //第X行的棋子落下
                    rows[x] = 1; cols[y] = 1; slot1[x + y] = 1; slot2[x - y + board_size - 1] = 1; x2y[x] = y;
                }  
                else
                {
                    //回溯，拿起棋子
                    if (x > 0)
                    {
                        x2y[x] = -1;
                        x--;
                        rows[x] = 0; cols[x2y[x]] = 0; slot1[x + x2y[x]] = 0; slot2[x - x2y[x] + board_size - 1] = 0;
                        continue;
                    }
                    else break;
                }
                if (x == board_size - 1)   //如果已经得到了一组解，即当最后一行棋子落定之时
                {
                    for (int i = 0; i < board_size; i++)
                    {
                        for (int j = 0; j < board_size; j++)
                        {
                            if (x2y[i] == j) Console.Write("Ｑ");
                            else Console.Write("■");
                        }
                        Console.Write("\n");
                       
                    }
                    Console.Write("\n");
                    solution_count++;   //总方案数加一
                    rows[x] = 0; cols[x2y[x]] = 0; slot1[x + x2y[x]] = 0; slot2[x - x2y[x] + board_size - 1] = 0;//放弃这一列

                }
                else
                {
                    x++;   //继续处理下一行
                }
            }
            t_end = DateTime.Now;
            Console.WriteLine("总共{0}组解",solution_count);
            Console.WriteLine("计算及打印共用时间{0}秒",t_end-t_start);
            return 0;
        }
    }
}

___________________________________________________________

测试结果:
请输入棋盘的大小
4
■Ｑ■■
■■■Ｑ
Ｑ■■■
■■Ｑ■

■■Ｑ■
Ｑ■■■
■■■Ｑ
■Ｑ■■

总共2组解
计算及打印共用时间00:00:00秒

_______________________________________________
请输入棋盘的大小
6
■Ｑ■■■■
■■■Ｑ■■
■■■■■Ｑ
Ｑ■■■■■
■■Ｑ■■■
■■■■Ｑ■

■■Ｑ■■■
■■■■■Ｑ
■Ｑ■■■■
■■■■Ｑ■
Ｑ■■■■■
■■■Ｑ■■

■■■Ｑ■■
Ｑ■■■■■
■■■■Ｑ■
■Ｑ■■■■
■■■■■Ｑ
■■Ｑ■■■

■■■■Ｑ■
■■Ｑ■■■
Ｑ■■■■■
■■■■■Ｑ
■■■Ｑ■■
■Ｑ■■■■

总共4组解
计算及打印共用时间00:00:00.0156250秒

时间： 2024-09-30 04:00:10

皇后问题之C#版（非递归）的相关文章

c语言-C语言版非递归马踏棋盘·死循环了·求大神解答·小弟新手求助

问题描述 C语言版非递归马踏棋盘·死循环了·求大神解答·小弟新手求助 这是出现死循环的代码bool solution(Move move, Pos &beginPos){ if(!move) { printf("solution Failed!"); return false; } int chessBoard[8][8] = {0}; push(move, beginPos); chessBoard[beginPos.mX][beginPos.mY] = 1; int ste

非递归版归并排序

非递归版的归并排序,省略了中间的栈空间,直接申请一段O(n)的地址空间即可,因此空间复杂度为O(n),时间复杂度为O(nlogn); 算法思想: 开始以间隔为1的进行归并,也就是说,第一个元素跟第二个进行归并.第三个与第四个进行归并: 然后,再以间隔为2的进行归并,1-4进行归并,5-8进行归并: 再以2*2的间隔,同理,知道2*k超过数组长度为止. while(i<length){ Merge(arr,temp,i,length); i *= 2; } 当不够两组进行归并是,如果超过k个元素,

二叉树的非递归先序，中序，后序遍历

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<stack> using namespace std; struct Tree{ int x; Tree *lchild, *rchild; Tree(){ lchild = rchild = NULL; } }; typedef Tree* pT; void buildT(pT &

C#非递归方式实现排列组合

C#以非递归方式实现三位排列组合,如下代码: //深度优先  class Program      {          static void Main(string[] args)          {              int[] number = new int[] { 1, 3, 5, 7 };              List data = new  List();              Stack openStack = new Stack();           

二叉树递归和非递归遍历

二叉树是一种非常重要的数据结构,很多其他数据机构都是基于二叉树的基础演变过来的.二叉树有前.中.后三种遍历方式,因为树的本身就是用递归定义的,因此采用递归的方法实现三种遍历,不仅代码简洁且容易理解,但其开销也比较大,而若采用非递归方法实现三种遍历,则要用栈来模拟实现(递归也是用栈实现的).下面先简要介绍三种遍历方式的递归实现,再详细介绍三种遍历方式的非递归实现. 一.三种遍历方式的递归实现(比较简单,这里不详细讲解) 1.先序遍历--按照"根节点-左孩子-右孩子"的顺序进行访问. vo

全排列的递归与非递归实现浅析

全排列问题在公司笔试的时候很常见,这里介绍其递归与非递归实现. 递归算法 1.算法简述 简单地说:就是第一个数分别以后面的数进行交换E.g:E = (a , b , c),则 prem(E)= a.perm(b,c)+ b.perm(a,c)+ c.perm(a,b)然后a.perm(b,c)= ab.perm(c)+ ac.perm(b)= abc + acb.依次递归进行. void swap(string &pszStr,int k,int m) { if(k==m) return ; c

递归和非递归方式实现二叉树的建立和遍历

#include<stdio.h> #include<stdlib.h> #define MAXSIZE 20 typedef struct BiTnode{ char data; struct BiTnode *lchild,*rchild; }BiTnode,*BiTree; int i = 0; BiTree Create(BiTree t,char s[]) { char ch; ch = s[i++]; if(ch == ' ') { t = NULL; } else {

如何使用递归和非递归方式反转单向链表

以下是对使用递归和非递归方式反转单向链表的示例进行了详细的分析介绍,需要的朋友可以过来参考下   问题: 给一个单向链表,把它从头到尾反转过来.比如: a -> b -> c ->d 反过来就是 d -> c -> b -> a . 分析:假设每一个node的结构是: 复制代码 代码如下: class Node {  char value;  Node next; } 因 为在对链表进行反转的时候,需要更新每一个node的"next"值,但是,在更新

先序遍历二叉树的递归实现与非递归实现深入解析

以下是对先序遍历二叉树的递归实现与非递归实现进行了详细的分析介绍,需要的朋友可以过来参考下   1.先序遍历二叉树  递归实现思想:若二叉树为空,返回.否则 1)遍历根节点: 2)先序遍历左子树: 3)先序遍历右子树: 代码: 复制代码 代码如下: template<typename elemType> void PreOrder(nodeType<elemType> *root)  {      if(root==NULL)          return ;      visi

二叉树的非递归后序遍历算法案例解析

 这篇文章主要介绍了二叉树的非递归后序遍历算法实例,需要的朋友可以参考下 前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中. 方法有很多,这里只举一种,先定义栈结点的数据结构    代码如下: typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过.   lastOrderTraverse(Bi