八皇后问题洛谷P1219

偏执的太偏执、 2021-11-17 14:44 267阅读 0赞

## 题目描述 ##

检查一个如下的6 x 6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

![60.png][]

上面的布局可以用序列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大小的。

**输出格式：**

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

方法好像有按位搜索，深度优先搜索，棋盘法等等，现在只会一种方法，后面再添加。

在对角线上有一个规矩 ”↗“这个对角线上横坐标+纵坐标为定值，“↘”对角线上横坐标减纵坐标为定值，由于j-i可能为负值，所以再j-i的基础上加了n。

主要就是用三个一维数组存储该列是否被占用，左下到右上的对角线是否被占用，左上到右下的对角线是否被占用，如果没有被占用，那么这个皇后占领该位置；用ans\[行数\]来存储每行被占领的列(这句可能不知道我在说什么)，就是用来输出的。

#include<iostream>
    using namespace std;
    
    int que[14];
    int line[20] = { 0 }, dj1[50] = { 0 }, dj2[50] = { 0 };
    int n;
    int s=0;
    int ans[20];
    void queen(int j)
    {
    	//输出
    	if (j > n)
    	{
    		s++;
    		if (s > 3)
    			return;
    		else {
    			for (int k = 1; k <= n; k++)
    				cout << ans[k]<<" ";
    			cout << endl;
    			return;
    		}
    		
    	}
    	for (int i = 1; i <= n; i++)
    	{//i代表列 dj1是↙  dj2是↖;
    		if (!line[i] && !dj1[i + j] && !dj2[j - i + n])
    		{
    			ans[j] = i;
    			line[i] = 1;
    			dj1[i + j] = 1;
    			dj2[j - i + n] = 1;
    		
    			queen(j+1);
    
    			dj2[j - i + n] = 0;
    			dj1[i + j] = 0;
    			line[i] = 0;
    		}
    	}
    }
    
    int main()
    {
    	cin >> n;
    	queen(1);
    	cout << s << endl;
    	return 0;
    }

在这个代码里，i代表行列，j代表行，从第一行到第n行，然后输出控制为3个。

转载于:https://www.cnblogs.com/yz-lucky77/p/11099200.html

[60.png]: /images/20211116/441ef64e5952404ab90b29bc99273302.png