$n\times n$ 的矩阵 $a$ 是拉丁方阵当且仅当 $a$ 的任意一行、任意一列都是 $1 \sim n$ 的排列。

求字典序最小的 $n$ 阶拉丁方阵。

这个显然可以爆搜做，但我没有找到任何一种非指数级的算法。

我打表找了 $1\sim 11$ 阶的答案，发现 $n$ 阶可以推广到 $n2^k$ 阶的答案，但没什么用。

1

1 2 
2 1 

1 2 3 
2 3 1 
3 1 2 

1 2 3 4 
2 1 4 3 
3 4 1 2 
4 3 2 1 

1 2 3 4 5 
2 1 4 5 3 
3 4 5 1 2 
4 5 2 3 1 
5 3 1 2 4 

1 2 3 4 5 6 
2 1 4 3 6 5 
3 4 5 6 1 2 
4 3 6 5 2 1 
5 6 1 2 3 4 
6 5 2 1 4 3 

1 2 3 4 5 6 7 
2 1 4 3 6 7 5 
3 4 1 2 7 5 6 
4 5 6 7 1 2 3 
5 3 7 6 2 1 4 
6 7 2 5 3 4 1 
7 6 5 1 4 3 2 

1 2 3 4 5 6 7 8 
2 1 4 3 6 5 8 7 
3 4 1 2 7 8 5 6 
4 3 2 1 8 7 6 5 
5 6 7 8 1 2 3 4 
6 5 8 7 2 1 4 3 
7 8 5 6 3 4 1 2 
8 7 6 5 4 3 2 1 

1 2 3 4 5 6 7 8 9 
2 1 4 3 6 5 8 9 7 
3 4 1 2 7 8 9 5 6 
4 3 2 1 8 9 6 7 5 
5 6 7 8 9 1 2 3 4 
6 5 8 9 1 7 3 4 2 
7 8 9 5 2 3 4 6 1 
8 9 6 7 4 2 5 1 3 
9 7 5 6 3 4 1 2 8 

1 2 3 4 5 6 7 8 9 10 
2 1 4 3 6 5 8 7 10 9 
3 4 1 2 7 8 9 10 5 6 
4 3 2 1 8 7 10 9 6 5 
5 6 7 8 9 10 1 2 3 4 
6 5 8 7 10 9 2 1 4 3 
7 8 9 10 3 4 5 6 1 2 
8 7 10 9 4 3 6 5 2 1 
9 10 5 6 1 2 3 4 7 8 
10 9 6 5 2 1 4 3 8 7 

1 2 3 4 5 6 7 8 9 10 11 
2 1 4 3 6 5 8 7 10 11 9 
3 4 1 2 7 8 5 6 11 9 10 
4 3 2 1 8 9 10 11 5 6 7 
5 6 7 8 1 10 11 9 2 3 4 
6 5 8 7 2 11 9 10 1 4 3 
7 8 9 10 11 1 2 3 4 5 6 
8 7 10 11 9 2 3 4 6 1 5 
9 10 11 5 3 4 6 1 7 2 8 
10 11 6 9 4 3 1 5 8 7 2 
11 9 5 6 10 7 4 2 3 8 1