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）就已經算不出了，而且還不知道該怎么計算時間復雜度，這樣的遞歸應該復雜度是很高的
可是通過剪枝應該優化了很多，不過不知道計算復雜度時侯要怎么考慮。
很大程度上還是根據提示寫完的，代碼能力太弱啦！
1
import 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
}