@空明流轉
直接枚舉法，你說的是對5040種排列依次猜測嗎。。。？最壞情況下猜測次數可能5040次吧?；蛘吣阌懈玫霓k法嗎？
@東坡_居士
我覺得不應當考慮概率，而應當考慮在任意時刻，可行解集合里任何數都有可能是正確結果。實際上就是在一個狀態轉移圖中，任何可行的路徑都有可能沿著走下去，每選擇一個數，就走進了一個分支。
@東坡_居士
上面公式還可以進一步修改一下：
t(F) = min{ t( F- conf(f) ) + 1, for all f belongs to F}， 其中conf(f)指與f沖突的集合（每一種返回結果就對應一個沖突集，所以復雜度又上升了）。
@東坡_居士
我猜測你也在考慮“動態規劃”方法。
我考慮過“動態規劃”算法，遞推公式： t(F) = min{ t(F-f)+1, for all f belongs to F}, 其中 F 是當前可行集，t(F)為該可行集 F 條件下猜出結果的次數，f 為 F 中的一個可行排列。
但是我沒有編程實現，因為擔心復雜度太高運行不完。但是可以保證這樣能得到最優解。
貪心算法得到的應當不是最優解，但是近似最優解，而且也是可以接受的。
@東坡_居士
最好最壞就是說：每一行求最大（最壞），然后對所有行的最大值中取最?。ㄗ詈茫?。所以計算過程還是 O(M^2) 的。
@東坡_居士
回復東坡_居士：你的算法“如果這個“提問”得到的“答案”種類越多，每個答案下面的可能數字就越少”，實際上可以通過對Clever1Palyer的進行修改實現：
34 int all_max = 0;
35 int all_max_index;
36 for (int i=0; i<M; i++) {
37 // 對于每一個可行排列 Ri
38 if (_cand[i]) { // 這一行也可以去掉
41 // cur_max 記錄該當前行可行排列的關系的種數
42 int cur_max = 0;
43 for (int j=0; j<=MATCH; j++)
44 res_count[j] = 0;
45 for (int j=0; j<M; j++) {
46 if (_cand[j])
47 res_count[ (int)table[i][j] ]++;
48 }
49 for (int j=0; j<=MATCH; j++) // 求種類數
50 if (res_count[j] > 0)
51 cur_max ++;
52 // 如果 cur_max 小于全局 all_max，則更新 all_max，并記錄下當前排列的序號
53 // 這樣能找到種類數最多的情況
54 if (cur_max > all_max) {
55 all_max = cur_max;
56 all_max_index = i;
57 }
58 }
59 }
所以我的假設是最壞假設，你的假設是等概率假設。呵呵，你把裁判想得比較善良。
@東坡_居士
當前Clever1Player時間復雜度為 (M*M*Time) ，其中Time為猜測次數。考慮次數總小于10，所以時間復雜度為 (M^2)。
我曾經做過優化，即使用一個數組保存可行排列序號，這樣在 Clever1Player 的 36 和 45 行就只需要掃描數組，而不需要每次都掃描 M 次了。當然總的時間復雜度依然是 (M^2)。
Clever2Player 與 Clever1Player 的唯一區別在于 “去掉了Clever1Player 的第 38 行”，使得“下一次猜測的排列不局限于可行排列”。
基于的考慮是：
-------------
假設正確結果是 0124
第一次猜 0123 -> 3A0B
Clever1Player 接下來不能猜 4567 ，因為 4567 不在可行集中（已經排除）。
但是Clever2Player 則有可能會猜 4567 得到 0A1B，直觀上說，猜測范圍就縮小到 01234567 中了，搜索空間減小很多。實際上我們人腦使用邏輯推理的時候通常就是這么考慮的，而且我們肯定是不會使用這種搜索算法的。
至于邏輯推理法與搜索法之間有什么聯系，我也不清楚。
-------------
另外，該算法的關注點在于猜測次數，即在于效果而不是效率。所以為了使算法看起來清晰，我沒有過多優化。
NaivePlayer 算法執行時間最快，大約1分鐘跑完所有，Clever1Player大約5分鐘，Clever2Player大約10分鐘。