一个简单的算法问题

Question

设有n种不同的颜色，同一种形状的n颗宝石分别具有这n种不同的颜色。现有n种不同形状的宝石共n*n颗，欲将这n*n颗宝石排列成n行n列的一个方阵，使方阵中每一行和每一列的宝石都有n种不同形状和n种不同颜色。试设计一个程序计算出对于给定的n有多少种不同的宝石排列方案。
各位大虾请用JAVA描述此算法。

Answer 1

1 2 ...n
2 3 ...1
..
n 1 ...n-//数字表示颜色
//行间调换 N！种 不用列调换 因为是对称的

Answer 2

假设现在有2种颜色a和b，2种形状A和B，用<颜色，形状>来表示一个石头。
谁能给我一个排好的方案？

Answer 3

对于n为偶数的时候，应该是无解的。当n为奇数的时候，
我们将颜色和形状排列成两个有序数组[C1,C2,...Cn],[S1,S2,...,Sn] 。
我们约定C[i] = Ci (i<=n), C[i] = C[i-n] (i>n)
        S[i] = Si (i<=n), S[i] = S[i-n] (i>n)========================  第1行  =======================================
在n种颜色，            n种形状中选择一个石头，  共  n  *  n  种选择方法；
然后在剩下的n-1种颜色，n-1种形状中选择一个石头，共(n-1)*(n-1)种选择方法；
然后在剩下的n-2种颜色，n-2种形状中选择一个石头，共(n-2)*(n-2)种选择方法；
...
最后在剩下的1种颜色，  1种形状中选择一个石头，  共   1 *  1  种选择方法；========================  第2行  =======================================
在第1行的基础上，每列颜色+1,形状+2
========================  第3行  =======================================
在第2行的基础上，每列颜色+1,形状+2
...
========================  第n行  =======================================
在第n-1行的基础上，每列颜色+1,形状+2可以验证，这样的一个分法可以保证每行每列都涵盖了所有的颜色和形状。
显然，保持第一行不变，剩下的n-1行做任意的行换位都可以生成一种不同的分法，这种分法同样满足题目的要求。因此，当n为奇数的时候，其分法数量为 
[(n!)*(n!) -- 第一行的分法] * [(n-1)! --剩下的n-1行的分法]

Answer 4

假设用(i,j)来表示第i种颜色第j种形状的石头。
设f(i,j)=i+(j-1)*n
那么这n*n个石头恰好对应于1至n*n这n*n个正整数。
石头的每一种排法恰好对应于n阶魔阵的一种填法，n阶魔阵的一种填法恰好对应于石头的一种排法。
原问题是不是就等价于不要求对角线元素和相等的n阶魔阵填法问题呢？
好高深啊！

Answer 5

更正一下前面我的说法
将颜色和形状排列成两个有序数组[C1,C2,...Cn],[S1,S2,...,Sn] 
...
========================  第2行  =======================================
在第1行的基础上，每列颜色+1,形状+2
...
事实上，由于颜色+1,形状+2的石头可能已经出现在第一行了，这样它当然就不可能再在第2行出现了。但是可以反过来，
先排好第一行，再按照第一行的颜色和形状出现的次序进行排序，这样就可以了。如果要求的仅仅是有多少个解的话，直接用上面的公式计算就可以了。
如果是要打印出解法的话，就麻烦一点了。或许可以用寻路的方法来尝试所有的可能性（就是效率太低）这个问题挺复杂的，没有从数学的角度严格的证明过，不知道这个公式是否正确的。

Answer 6

令f(x,y)=(Ax+By+C) mod n;g(x,y)=(Dx+Ey+F) mod n;h(x,y)=f(x,y)+n*g(x,y)
不失一般性可令A=D=1,B=1,C=F=0
则只要存在E满足:E,n互素且(E-1),n互素则原问题必有解。
由此可证n为偶数时必无解,因为E,E-1两者之一必不与n互素;n为奇数时必有解,因为令E=n-1即可。
又根据轮换对称性，存在一个解,则它的行的任意一个排列也为一个解,列的任意一个排列也为一个解，且这样覆盖了所有解，所以共有(n!)*(n!)个解。
结论：n=2k (k=1,2,...) 时共0个解; n=2k-1 (k=1,2,...) 时共(n!)*(n!)个解。