一个搜索的题目,不过肯定是要剪枝的

最简单的两个剪枝我想到了

第一个:
首先,第一行已经确定了,那么我们可以把第一列也确定,就按照升序,2,3,4,5……,这样的话,没生成这么一个square,我们就可以随便的去交换除了第一行后面的几行。

他们的一个全排列就对应着一种组合,所以最后的答案乘以N-1的阶乘就可以

第二个:
这个其实是看来的,就是每次只要所搜完N-1行就可以了。因为剩下的一行必然存在一个解。其实这个不难理解的,最后一行的排列顺序只跟前面的每一列缺少的那个数有关。

而且也只能取缺少的那个数,所以也就是唯一的。

第三个:
要用到置换群,我没看懂

尽管之前N次看组合数学里面都说到置换群,但是我还是似懂非懂,问了数学小王子,他也不是非常懂。然后以为这个东西没用,就忽略了。没想到还真的有用。