Java - 多少個數字的組合

Question

任何人都可以給我一個想法，我如何用Java解決以下問題。有多少個可能的有效數字，其中有效數字是0-9之間的任何數字，10位數字的長度，不包括＃或*，一張國際象棋可以在通過電話鍵盤旅行時跟蹤。這裏說我有一個國王，它只能像在真正的遊戲中一樣，以任何方向移動，但一次只能移動一個單元格。

因此鍵盤看起來是這樣的：

  1 2 3 
     4 5 6 
     7 8 9 
     * 0 # 

於是一片，使得每次10個移動，並通過它是一個有效的數字創建的每個唯一編號。一件作品從最初的起始位置開始。

更新： 一塊可以移動或停留在一個地方（移動或停留都會算作移動）以及重新訪問單元格（只要它允許在其各自的移動權限內）。因此，舉例來說，如果國王從位置1移動，則三個有效的10移動路徑以創建有效數字編號可以是1236547890或1111111111或1212121212

以下是僅有4個單元格的小型四格方形墊的代碼只是爲了測試目的：

public class King 
{ 
private static final Integer[] ALLOWED_FROM_1 = {2, 3, 4}; 
private static final Integer[] ALLOWED_FROM_2 = {1, 3, 4}; 
private static final Integer[] ALLOWED_FROM_3 = {1, 2, 4}; 
private static final Integer[] ALLOWED_FROM_4 = {1, 2, 3}; 
List<Integer> visited; 

public King() 
{ 
    this.visited = new ArrayList<Integer>(); 

} 

public List<Integer> get_destinations(int currentPos, int noOfMoves) 
{ 
    if (noOfMoves == 0) 
    { 
     visited.add(currentPos); 
     return visited; 

    } 
    else 
    { 

     List<Integer> possibleMoves = getPossibleMoves(currentPos); 

     for (int i = 0; i < possibleMoves.size(); i++) 
     { 
      visited.add(possibleMoves.get(i)); 
      get_destinations(possibleMoves.get(i), noOfMoves - 1); 

     } 

     return visited; 
    } 



} 


private List<Integer> getPossibleMoves(int currentPos) 
{ 

    List<Integer> possibleMoves = new ArrayList<Integer>(); 

    switch (currentPos) 
    { 
     case 1 : possibleMoves.addAll(Arrays.asList(ALLOWED_FROM_1)); 
      break; 

     case 2: possibleMoves.addAll(Arrays.asList(ALLOWED_FROM_2)); 
      break; 

     case 3 : possibleMoves.addAll(Arrays.asList(ALLOWED_FROM_3)); 
      break; 

     case 4 : possibleMoves.addAll(Arrays.asList(ALLOWED_FROM_4)); 
    } 

    return possibleMoves; 

} 
} 

上面的代碼只產生部分答案，丟失了許多不同的排列。主要的問題是我怎樣才能確保它能產生所有的排列，以及在上面的代碼中什麼時候能夠達到應該存儲並隨後檢索的4位數字（4次移動後）。我怎樣才能避免重新訪問相同的序列，例如1234 1234，所以基本上對其進行了優化，使其不會產生相同的路徑序列/有效數字。

所有幫助非常感謝。

Answer 1

這是一些可能有所幫助的僞代碼。你可以用這樣的遞歸解決的問題：

// Returns a list of all the destinations given a current location 
// and the number of moves allowed (10 for King) 
list<int> get_destinations(int cur_location, int num_moves) { 
    // Base case. If no more moves are allowed, return current location as list. 
    if(num_moves == 0) { 
    return as_list(cur_location); 
    } else { 
    // List of all destinations possible from here 
    list<int> destinations; 
    // Get all the possible moves that are 1 step away. 
    // For example: from 1, we would return 2 and 4 
    list<int> possible_moves = get_possible_moves(cur_location); 

    // For each of the moves generated from the last step, 
    // recursively call get_destinations() with (num_moves - 1) 
    for(int n:possible_moves) { 
     destinations += get_destinations(n, num_moves - 1); 
    } 

    return destinations; 
    } 
} 

你可以這樣調用這個函數是這樣的：

get_unique_nums(get_destinations); // Returns the set in the form you need it 

祝您的功課！

Answer 2

似乎很瑣碎的學術遞歸問題。只要允許遞歸，語言就不重要。

你需要：

1. 設置 一個。 F（n，m）數組（在你的情況下值爲3x4） b。和這件作品的初始位置。 c。以允許您可能想要定義的委託（函數指針，匿名類）函數定義允許的移動

2. 創建一個遞歸可調用的函數，用於標識下一個符合條件的輸入： a。當前件位置（i，j）， b。在第一次迭代從深度遞歸函數

3. 返回回遞歸深度1 = 10

4. 如果您還需要所有的序列，使這個遞歸函數可回收（非void類型）我想說字符串將是最好的

5. 如果你想更簡單的代碼，你不需要驗證在設定的允許單元的每一步*的存在，＃，只是確認最終10個符號長的字符串是可以解析爲UNSIGNED LONG。儘管它使遞歸太長。

Answer 3

對於王，這種重複來了。 2，1，2，1，3,4，3，1，2，3，4，2，3,4，3，1

可以使getPossibleMove（）函數返回細胞按特定順序排列。 這將有助於避免重複路徑。說，在只有數字順序，那麼它應該返回

2，1，2，1，
2，1，2，3，
2，1，2，5，
2，1,4- ，如圖1所示，
2，1，4，5，
2，1，4,7

此外，如果不希望允許片移動到相同的小區，就除去在這些細胞只有getPossibleMove（）函數。

我沒寫什麼代碼，所以只寫了理論解釋。