同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1934_n后问题（LasVegas算法）

2022-5-16 18:18| 发布者: Hocassian| 查看: 48| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504163221700-Problem List-采集的数据-后羿采集器.html

Pro.ID

1934

Title

n后问题（Las Vegas算法）

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1934

AC

Submit

Ratio

0.00%

时间&空间限制

Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

输入

输入的第一个为测试样例的个数T，接下来有T个测试样例。每个测试样例的只有一行一个数n （ n < 100 ），表示棋盘的大小。

输出

Description

在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

Input

输入的第一个为测试样例的个数T，接下来有T个测试样例。每个测试样例的只有一行一个数n （ n < 100 ），表示棋盘的大小。

Output

为每个测试样例输出一行结果：任意一种可行方案。

可行方案的输出格式是：第一行的皇后所处的列号，第二行的皇后所处的列号，...，第n行的皇后所处的列号。列号从1开始。每个列号之后跟一个空格。

如果没有可行方案，则输出NIL

Sample Input

2
3
4

Sample Output

NIL
2 4 1 3

Author

John

样例输入