Java教程

八皇后问题

本文主要是介绍八皇后问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述:

有一个NxN的棋盘,将N个棋子放置在棋盘上,使得每行、每列有且只有一个棋子,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。 假设N的取值为6,其中一个有效的布局如下。
image
上面的布局可以用序列2 4 6 1 3 5来描述,第i个数字表示在第i行相应的列有一个棋子,如下:
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
请编写程序找出所有满足条件的布局。并将它们以上面的方式输出。输出的序列按字典序排列。
只输出前3个满足条件的布局。最后一行为满足条件的布局总数。

输入:

一个整数N (6<=N<=13) 表示棋盘是N x N的。

输出:

前3行为前3个解,每个解的两个数字之间用一个空格隔开。第4行为一个整数,表示解的总数。

样例输入:

6

样例输出:

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4


思路:

这道题也是十分经典的一道dfs的题目了吧。

大致思路很简单:就是遍历每一个点,能放就放,它所站的这行这列对角线标记住。

但是 问题来了 :找到放的点,该怎么标记它所占用的格子呢?

横行竖列很好标记,用一个数组来标记此行,占用为1.

那对角线怎么标记呢???

这里就要用到一个很重要的性质了————————对角线的性质(因为时间不够篇幅有限,就不做十分详细的介绍)

我们可以观察出 从右往左斜的线,各个点之间坐标之间有些关系:
e . g . 6 —— 1 ---> 6 + 1 = 7

5 —— 2 ---> 5 + 2 = 7

4 —— 3 ---> 4 + 3 = 7

这几个点都处于同一条对角线(见题目描述图),而他们的x+y坐标都是相同的,所以这就是副对角线的性质了,标记的时候就只用用当前点的x坐标加上枚举出来的i相加标记为1即可标记完整条对角线。

接下来,从左往右斜的线就是主对角线了,笔者就不进行过多叙述,方法和上面一样,举出例子,总结规律即可。
(怎么还是情不自禁花了这么长篇幅。不行!下次还要水一些)

几个难点和关键点都讲完了,接下来就直接放出代码了:


代码:

#include <bits/stdc++.h>
using namespace std;
int n;
int line [105],zhu[105],fu[105], s [105];
int ans = 0;
void print () {
    if(ans < 3){//题目限制只输出前三个(笔者ans++写在后面的,所以为<3) 
        for (int i = 1; i <= n; i ++) {
            printf ("%d ", s [i]);
        }
        printf("\n");//打印输出 
    }
    ans++;//输出只输出前三个,但总数还是要加的 
}
 
void dfs(int x){//当前枚举到第x个棋子了 
    if(x == n+1){//如果n个棋子枚举完了就输出; 
        print ();
    }
    else{
        for (int i=1;i<=n;i++){//枚举每个点 
            if(line[i] == 0 && zhu[x-i+n] == 0 && fu[x+i] == 0){
            	//如果主副对角线和行列都没标记过那么就放下棋子 
                line[i] = 1;//标记行列 
                zhu[x-i+n] = 1;//标记主对角线 
                fu[x+i] = 1;//标记副对角线 
                s [x] = i;//加入输出数组 
                dfs(x+1);//枚举下一个棋子 
                line[i] = 0;
                zhu[x-i+n] = 0;
                fu[x+i] = 0;//取消标记 
            }
        }
    }
}
int main() {
    scanf("%d",&n);//输入 
    dfs(1);//开始dfs第几个棋子 
    printf("%d",ans);//输出答案 
    return 0;
}
这篇关于八皇后问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!