5909: 【系列题】回溯(十四)N皇后

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:38 Solved:9

Description

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

N皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,输出所有不同的 N皇后问题 的解决方案。



每一种解法包含一个不同的 N皇后问题 的棋子放置方案。

请按照 从小到大顺序 输出。

如果不存在答案请输出 Error



Input

一个整数 n

Output

所有可能的放置方案。

每行一个方案。

每行 n 个数字 ai,表示将皇后放置在第 i 行的第 ai 列上。

请按照 从小到大顺序 输出。

Sample Input Copy

4

Sample Output Copy

2 4 1 3 
3 1 4 2 

HINT

样例说明:

 

输入:n = 4

输出:[[2, 4, 1, 3],[3, 1, 4, 2]]

解释:如上图所示,4皇后问题存在两个不同的解法。


数据范围:

  • 1 <= n <= 9