首页 > 其他 > 详细

7-3 N皇后问题 (20 分)

时间:2019-10-09 23:50:16      阅读:285      评论:0      收藏:0      [点我收藏+]
7-3 N皇后问题 (20 分)
 

在N * N的方格棋盘上,放置N个皇后,要求每个皇后不同行,不同列,不同左右对角线。 其中N不超过10。 要求:输出所有的解。 算法提示:用栈求解皇后问题。

技术分享图片

输入格式:

输入N

输出格式:

逐行输出每一种解,用每个皇后的位置坐标表示,每个位置坐标之后均有一个空格符,输出最后一行为空行。

输入样例:

在这里给出一组输入。例如:

6

输出样例:

在这里给出相应的输出。例如:

1: (1,2) (2,4) (3,6) (4,1) (5,3) (6,5) 
2: (1,3) (2,6) (3,2) (4,5) (5,1) (6,4) 
3: (1,4) (2,1) (3,5) (4,2) (5,6) (6,3) 
4: (1,5) (2,3) (3,1) (4,6) (5,4) (6,2) 

 

技术分享图片
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int a[12][12] = { 0 }, n, b[12][12] = { 0 };
void dfs(int x, int y)
{
    int c[12][12] = { 0 };
    b[x][y] = 1;
    if (x <= n && y <= n) {
        if (x == n && !a[x][y]) {
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    if (b[i][j] == 1) cout << i << " " << j << " ";
            cout << endl;
        }

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                if ((i == x || j == y || (abs(y - j) == abs(x - i)))&&(!a[i][j])) {
                    a[i][j] = 1;
                    c[i][j] = 1;
                }
            }

        for (int i = 1; i <= n; i++)
            if (!a[x + 1][i]) 
                dfs(x + 1, i);
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            if (c[i][j]==1)
                a[i][j] = 0;
        }
    b[x][y] = 0;
}
int main()
{

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        dfs(1, i);
        memset(a, 0, sizeof a);
    }
}
View Code

思路:一开始去网上搜了一下如何判断斜角的方法,当前斜边的点等于当前的点竖边减去横边相等。然后在bfs和暴力枚举就可以算出

7-3 N皇后问题 (20 分)

原文:https://www.cnblogs.com/pppyyyzzz/p/11644841.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!