1375: n皇后问题

n皇后问题是指将 n 个皇后放在 n×n 的棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。
输出n皇后的所有方案，将 从第一行到最后一行，每行皇后所在的列组合为一个字符串，方案的输出顺序按字符串的字典序进行输出

该图的表示的字符串为17468253
输出
* . . . . . . .
. . . . . . * .
. . . * . . . .
. . . . . * . .
. . . . . . . *
. * . . . . . .
. . . . * . . .
. . * . . . . .
'.'表示空位，‘*’表示该位有一个皇后

输入一个正整数n

输出所有方案，顺序按该方案的串的字典序输出
每个方案之间有一个空行

4

. * . . 
. . . * 
* . . . 
. . * . 

. . * . 
* . . . 
. . . * 
. * . . 

n为4时，只有两种方案，第一种方案代表的串为21413，第二种方案代表的串为3142，第一种的串小于第二种串，所以先输出第一种方案


本题中
若有列数大于9，组合成的串如 1 10 2 3 4 5 6 7 8 9 而不是1 1 0 2 3 4 5 6 7 8 9


$n\leq 12$