TopCoder SRM 392 Level2 1000
原题地址：http://www.topcoder.com/stat?c=problem_statement&pm=8561&rd=11126
两个整数n和d, 1<=n<=10, 1<=d<=n,求一个n*n方阵，每一行每一列都存在0～d的每个数，如果有多个矩阵，返回字母序最小的一个。

从头递归搜索，对每个位置从小遍历所有值，针对每个值做如下操作：
1.赋值为0
2.检查该行剩下的位置是否足够放下还没有出现的所有的数，若否返回第一步并且＋＋；
3.检查该列剩下的位置是否足够放下还没有出现的所有的数，若否返回第一步并且＋＋；
4.现在是一个可以考虑的值，首先是终结值，若该位置已经是矩阵右下角，则返回true，这是唯一返回true的起点
5.向后递归调用函数，调用下一个位置
6.如果返回值为true，则返回true，否则继续
7.返回false

总的来说，递归的顺序，1是遍历所有可能值，2，3是排除和剪枝，4是检测成功条件，5是递归调用，6，7是递归的结果
算法的复杂度较高，（15，15）就已经算不出了，而且还不知道该怎么计算时间复杂度，这样的递归应该复杂度是很高的
可是通过剪枝应该优化了很多，不过不知道计算复杂度时侯要怎么考虑。

很大程度上还是根据提示写完的，代码能力太弱啦！
 1import java.util.*;
 2import java.util.regex.*;
 3import java.text.*;
 4import java.math.*;
 5import java.awt.geom.*;
 6
 7public class QuasiLatinSquares
 8{
 9    int[][] ans;
10    int n;
11    int d;
12    
13    public String[] makeSquare(int n, int d)
14    {
15        
16        this.n = n;
17        this.d = d;
18        ans = new int[n][n];
19        backtrace(0,0);
20        
21        //change the integer matrix to string array
22        String[] ret = new String[n];
23        for(int i = 0; i < n ; ++ i){
24            StringBuilder sb = new StringBuilder();
25            sb.append(ans[i][0]);
26            for(int j = 1; j < n ; ++ j){
27                sb.append(" ");
28                sb.append(ans[i][j]);
29            }
30            ret[i] = sb.toString();
31        }
32        return ret;
33    }
34    
35    public boolean backtrace(int i, int j){
36        //have to check every value here
37        for(int v = 0; v < d; ++ v){
38            ans[i][j] = v;
39            
40            //check whether still enough place for numbers that haven't appear
41            boolean[] row = new boolean[d];
42            boolean[] col = new boolean[d];
43            Arrays.fill(row, false);
44            Arrays.fill(col, false);
45            for(int rowidx = 0; rowidx <= i; ++ rowidx)
46                row[ans[rowidx][j]] = true;
47            for(int colidx = 0; colidx <= j; ++ colidx)
48                col[ans[i][colidx]] = true;
49            int rct = 0, cct = 0;
50            for(boolean b:row){
51                if(b == false) rct++;
52            }
53            for(boolean b:col){
54                if(b == false) cct++;
55            }
56            if(rct > n-1-i)
57                continue;
58            if(cct > n-1-j)
59                continue;
60            
61            //if it's the last place, success!
62            if((i == n-1) && (j == n-1))
63                return true;
64
65            //recursively calculate latter numbers based on this value
66            boolean next;
67            if(j != n-1)
68                next = backtrace(i,j+1);
69            else
70                next = backtrace(i+1,0);
71            //if it has reached the end,it means this value has led to success, else it means the value has to increase
72            if(next == true)
73                return true;
74            
75        }
76        //have checked every number but none matches, former numbers has to reconsider
77        return false;
78    }
79}