J10 习题-1 N皇后问题

题目描述

在$N*N$的棋盘上放置 $N$ 个皇后，而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置$2$个皇后），编程求解所有的摆放方法 。

如上图：对应的位置信息是：$2,4,6,1,3,5$； 第一行的皇后放在第 $2$ 列；第二行的皇后放在第 $4$ 列；以此类推，请编程输出对应的方案情况；

输入格式

一个整数$n$，表示棋盘的尺寸。

输出格式

如果有解，输出 $s$ 行，每行 $n$ 个整数，表示该行皇后所在的列号（要求序列从小到大排序）。否则输出“$\text{impossible!}$”。

样例输入

4

样例输出

2 4 1 3
3 1 4 2

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$3\leq n \leq 10$。