TopCoder SRM 392 Level2 1000
原題地址：http://www.topcoder.com/stat?c=problem_statement&pm=8561&rd=11126
兩個(gè)整數(shù)n和d, 1<=n<=10, 1<=d<=n,求一個(gè)n*n方陣，每一行每一列都存在0～d的每個(gè)數(shù)，如果有多個(gè)矩陣，返回字母序最小的一個(gè)。

從頭遞歸搜索，對(duì)每個(gè)位置從小遍歷所有值，針對(duì)每個(gè)值做如下操作：
1.賦值為0
2.檢查該行剩下的位置是否足夠放下還沒有出現(xiàn)的所有的數(shù)，若否返回第一步并且＋＋；
3.檢查該列剩下的位置是否足夠放下還沒有出現(xiàn)的所有的數(shù)，若否返回第一步并且＋＋；
4.現(xiàn)在是一個(gè)可以考慮的值，首先是終結(jié)值，若該位置已經(jīng)是矩陣右下角，則返回true，這是唯一返回true的起點(diǎn)
5.向后遞歸調(diào)用函數(shù)，調(diào)用下一個(gè)位置
6.如果返回值為true，則返回true，否則繼續(xù)
7.返回false

總的來說，遞歸的順序，1是遍歷所有可能值，2，3是排除和剪枝，4是檢測(cè)成功條件，5是遞歸調(diào)用，6，7是遞歸的結(jié)果
算法的復(fù)雜度較高，（15，15）就已經(jīng)算不出了，而且還不知道該怎么計(jì)算時(shí)間復(fù)雜度，這樣的遞歸應(yīng)該復(fù)雜度是很高的
可是通過剪枝應(yīng)該優(yōu)化了很多，不過不知道計(jì)算復(fù)雜度時(shí)侯要怎么考慮。

很大程度上還是根據(jù)提示寫完的，代碼能力太弱啦！
 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}