八皇后

发表于 | 更新于: | 次
字数统计: 584 字 | 阅读时长 ≈ 3 分钟

日水博客(1/1)

经典题，也是模板题，就不多说了(然而我写了3小时，debug2小时)

八皇后问题

【题目描述】

在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。

[输入]

(无)

【输出】按给定顺序和格式输出所有八皇后问题的解（见样例）。

【输入样例】

（无）

【输出样例】

1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
>1 0 0 0 0 0 0 0 
>0 0 0 0 0 0 1 0 
>0 0 0 0 1 0 0 0 
>0 0 0 0 0 0 0 1 
>0 1 0 0 0 0 0 0 
>0 0 0 1 0 0 0 0 
>0 0 0 0 0 1 0 0 
>0 0 1 0 0 0 0 0 `
>No. 2
>1 0 0 0 0 0 0 0 
>0 0 0 0 0 0 1 0 
>0 0 0 1 0 0 0 0 
>0 0 0 0 0 1 0 0 
>0 0 0 0 0 0 0 1 
>0 1 0 0 0 0 0 0 
>0 0 0 0 1 0 0 0 
>0 0 1 0 0 0 0 0 
>...以下省略
>

贴代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
#include<stdlib.h>
#define FR(x,k,z) for(register int x = k; x <= z; x++)
#define FFR(x,k,z) for(register int x = k; x < z; x++)
typedef long long int64;

using namespace std;

int maps[9][9];
int piece, now, serial = 1;

int prints()//按列输出(这是个大坑，我两个半小时都花在这里)
{
	cout << "No. " << serial <<'\n';
	FR(i, 0, 7)
	{
		FR(j, 0, 7)
		{
			cout << maps[j][i] << ' ';
			continue;
		}
		cout <<'\n';
	}
	serial++;
#ifdef DEBUG
	system("pause");
#endif // DEBUG
	return 0;
}

bool checks(int x, int y)
{
	FR(i, 0, 7)//检测所在行是否冲突
	{
		if (maps[x][i] == 1)
		{
			return false;
		}
	}	
	FR(i, 0, 7)//检测所在列是否冲突
	{
		if (maps[i][y] == 1)
		{
			return false;
		}
	}
//这里不知道为啥我写 (m - r == x - y || m + r == x + y && maps[m][r] == 1)过不了，可能我太菜了
	FR(m, 0, 7)//检查所在对角线是否冲突
	{
		FR(r, 0, 7)
		{
			if (m - r == x - y && maps[m][r] == 1)//右下角
			{
				return false;
			}
			if (m + r == x + y && maps[m][r] == 1)//左下角
			{
				return false;
			}
		}
	}
	return true;
}

int dfs(int step)
{
	if (step == 8)
	{
		prints();
		return 1;
	}
	FR(j, 0, 7)
	{
		if (!checks(step, j))
		{
			continue;
		}
		maps[step][j] = 1;
		dfs(step + 1);
		maps[step][j] = 0;
	}
	return 0;
}

int main()
{
	dfs(0);
	return 0;
}