题目大意:给定N*N个数,把它们填入N*N的方格中,使每行每列和两个对角线里数的和都相等。数据保证有可行解,输出任一解即可。
输入
第一行一个整数N。
第二行N*N个整数,表示要填入幻方中的数。
输出
N行,每行N个整数,代表填好的幻方
样例输入
3 1 2 3 4 5 6 7 8 9
样例输出
2 7 6 9 5 1 4 3 8
提示
数据点 | 特征 |
1 | N=3 |
2 | |
3 | |
4 | N=4且数字种类数不超过9 |
5 | |
6 | 4
4815960 32237520 2073804 -668352 -22605600 -668352 15784584 4815960 10300272 -6152664 10300272 15784584 -6152664 7558116 2073804 7558116 |
7 | 4
-80196146 -51775286 -34722770 -29038598 -17670254 -11986082 -6301910 -617738 10750606 16434778 22118950 27803122 39171466 44855638 61908154 90329014 |
8 | N = 4 |
9 | |
10 |
对于所有数据点,填入数字的绝对值不超过10^9。
解题思路
格子搜索,一个一个格子填入数字,每次从n*n个数字里面选一个没填过的。对应n=3,即使不剪枝,时间复杂度也不超过10!,但对于n=4,必定超时。
首先考虑剪枝,没有最优,只有可不可行,那就进行可行性剪枝。什么是可行呢?要求每行每列每斜都相等,这个值是可以算出来的,即m=n*n个数的和除以n。在填完一行、一列、一斜,就判断那n个数是否等于m,如果不相等,就不需要搜索了。结果还是超时!
再想想,搜索顺序对速度有没有影响呢?终于找到规律,如果n=4,从上到下、从左到右的格子依次是0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,那么我们可以按照这样的顺序进行搜索:0,1,2,3,4,5,6,7,8,12,9,13,10,11,14,15,这样的话,3、7、12、9、13、11、14、15都是可以直接确定的,也就是说只有8个数需要枚举,复杂度是16*15*14*12*11*10*8*4,即从16个数里面选8个数的复杂度(还跟顺序有关)!
接下来就是慢慢考虑到哪个格子的时候,需要判断些什么,如3判断第一行、7判断第二行、12判断第一列、9判断撇、13判断第二列、11判断第三行、14判断第三列、15判断第四行第四列以及捺。