八皇后与n皇后问题
in C#Algorithm with 1 comment
Read:473

八皇后与n皇后问题

in C#Algorithm with 1 comment

在我大一的时候才接触编程不久,开始研究了一些基础算法。那时候八皇后问题被我冥思苦想3天理解了,也算是有收获。长期不练算法也特别生疏了。所以我把八皇后与n皇后问题在blog复写出来。用的C#语言。

八皇后问题的概念

首先,先要了解什么时八皇后问题。八皇后是一个古老而著名的问题,是回溯算法的典型案例。在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法

简单了解回溯算法的概念

回溯算法有点类似递归。差别是:比如我有100种可能,每种可能下面又有100种可能,递归就是把这100*100一个一个去尝试,最后直到尝试出来,可能第6895次就是答案,可能要9999次。我就仗着电脑性能不错喜欢递归这种简单粗暴的暴力破解,但是要是计算量大呢?几十亿,几百亿上千亿的可能呢?递归到死?所以,回溯算法就是递归的升级版,也是一个一个去尝试搜索,但是,找一个满足条件的就往下一层搜索,同理,一直往下搜索下去,当遇到不满足的条件,就返回,去尝试别的路径,剩下的就不用试了,节省了很大的计算量。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”

八皇后图解与分析

可以看到这是八皇后的棋盘,我先下了一个皇后,根据规则,绿色的范围不能放其他皇后(横竖斜)
queen1.png
那么我只能在白色的地方放皇后了
queen2.png
两个皇后就占据这么多位置,这样下去,剩下的怎么能放得完?
如上面所说的一个一个是试,64个里面选出8个,那是十亿级别的计算量。

稍加分析,我们可以得到另一个不那么暴力的方法:显然,每行每列最多只能有一位皇后,如果基于这个事实再进行暴力破解,那结果会好很多。安排皇后时,第一行有8种选法,一旦第一行选定,假设选为(1,i),那么第二行只能选(2,j),其中,j不等于i,j不等于i-1,和j不等于i+1,毕竟45度斜线也在规则上。以此类推,需要穷举的情况有40320种,比十亿级别的小很多了。

C#编写

首先,我们创建两个变量

//定义解得个数
int sum = 0;
//定义皇后数组
int[] Queens = new int[8];

根据规则,我们创建一个判断你放的皇后位子安不安全的函数

//传入行和列的参数,这里用xy表示
public bool IsSafe(int x, int y)
{
    //如果是第一行,在场的就一个皇后,铁定安全,不会被攻击
    if (x == 0)
        return true;
    //不是第一行就要判断和之前的所有皇后有没有冲突
    else
    {
        for (int last_x = 0; last_x < x; last_x++)
        {
            //如果以前放置的皇后,和现在即将放置的皇后有冲突,x-last_x为现在要放的皇后和之前last_x行的皇后的行差
            //如果两个棋子的行差和列差相等,那么就说明他们是在斜率为1的斜线上。大白话:东北,西北,西南,东南,懂?
            if (!CompareTwo(Queens[last_x], x - last_x, y))
            {
                return false;
            }
        }
        return true;
    }
}

上面的IsSafe函数调用了一个CompareTwo比较两个皇后冲不冲突的函数

//Queens[last_x]的值就是last_x行的皇后的列last_y
public  bool CompareTwo(int last_y,int x_Cha,int y)
{
    //行的差距等于列的差距,那么两点就是就是成45度的直线,斜率为1。
    if (last_y == y || last_y - y == x_Cha || y - last_y == x_Cha)
    {
        return false;
    }
    else
        return true;
}

有了判断全部皇后是否安全的函数(IsSafe)和对比两个皇后是否有冲突的函数(CompareTwo),接下来需要一个回溯调用IsSafe的函数

public void Queen_ZuHe(int x)//排序组合皇后
{
    for (int y = 1; y < 9; y++)
    {
        if (x == 8)//都排到第八行了已经over了,该输出了
        {
            sum++;
            write();
            break;
        }
        if (IsSafe(x, y))//判断目前放的棋子是否安全,有冲突是false,true就是没有冲突,安全 
        {
            Queens[x] = y;//条件满足时,Queens数组的索引为x也就是行,值为y,也就是列。代表皇后坐标
            //找出了当前行的安全皇后,又要找下一行的安全位置,又调用这个函数,当前行是x,那么下一行就是x+1
            Queen_ZuHe(x + 1);
        }
    }
}

其实到这一步就已经结束了,不过write函数是干嘛的?当然是用来输出一个能用眼睛直观看的图组啦

public void write()//输出皇后的排列
{
    Console.WriteLine("第{0}种皇后的排列:", sum);
    for (int x = 0; x < 8; x++)
    {
        for (int y = 1; y < 9; y++)
        {
            if (Queens[x] == y)
                Console.Write("■");
            else
                Console.Write("□");
        }
        Console.WriteLine();
    }
}

最后在Main函数里面调用一下就可以了

Queen_ZuHe(0);//第一行为0,因为索引第一个为0

queen3.png

n皇后不是同理吗?

如果对你有帮助,打钱

赞赏



Responses
  1. 加油!看来你是要越走越远了

    Reply