4x4的2D人物矩阵排列

Question

我有字符的4×4二维数组是这样的：

A B C D 
U A L E 
T S U G 
N E Y I 

现在，我需要找到的3个字符，4个字符，等所有的排列，直到10

因此，可以从中找到的一些词是TEN,BALD,BLUE,GUYS。

我确实搜索过这个和谷歌搜索，但没有具体的帮助。你能把我推向正确的方向吗？我应该学习哪种算法（A *也许？）。请温柔一点，因为我不算算算家伙（不是我们全部（好吧，至少是大多数:)），但是我愿意学习只是不知道从哪里开始。

Answer 1

啊，这就是游戏Boggle是不是...你不想排列，你想要一个图，你想在图中找到单词。

那么，我首先将字符排列为图形节点，然后将它们连接到它们的直接邻居和对角线邻居。

现在你只是想搜索图表。对于16个起始节点中的每一个，您都要进行递归。在移动到新节点时，必须将其标记为正在使用，以便您不能再移动到该节点。当你离开一个节点（完全搜索它）时，你将它解除标记。

我希望你看这是怎么回事...

对于每个节点，您将参观各邻国和字符添加到字符串。如果你已经在脑海中建立了你的字典，那么你将立刻就能看到你到目前为止的字符是否是一个字的开头。这很好地缩小了搜索范围。

我谈论的字典的种类是你有一棵树的节点每个字母的字母有一个孩子。这些美妙之处在于你只需要在搜索中存储你现在正在使用的树节点。如果你决定找到一个单词，你只需通过父节点回溯，找出它是哪个单词。

使用此树样式以及深度优先图搜索，您可以同时搜索所有可能的字长。这是我能想到的最有效的方式。

---

让我写一个pseudocodish功能，为您的图形搜索：

function FindWords(graphNode, dictNode, wordsList) 
    # can't use a letter twice 
    if graphNode.used then return 

    # don't continue if the letter not part of any word 
    if not dictNode.hasChild(graphNode.letter) then return 
    nextDictNode = dictNode.getChild(graphNode.letter) 

    # if this dictionary node is flagged as a word, add it to our list 
    nextDictNode.isWord() 
     wordsList.addWord(nextDictNode .getWord()) 
    end 

    # Now do a recursion on all our neighbours 
    graphNode.used = true 
    foreach nextGraphNode in graphNode.neighbours do 
     FindWords(nextGraphNode, nextDictNode, wordsList) 
    end 
    graphNode.used = false 
end 

和当然，踢了整个事情关闭：

foreach graphNode in graph do 
    FindWords(graphNode, dictionary, wordsList) 
end 

剩下的工作就是建立图表和字典。我只记得那个字典数据结构叫什么！这是一个Trie。如果你需要更节省空间的存储，你可以压缩成Radix Tree或类似的，但最简单（最快）的就是使用直接Trie。

Answer 2

看来你只需要使用4×4矩阵长度为16的数组如果是的话，你可以尝试递归方法来生成排列的最大长度是k如下：

findPermutations(chars, i, highLim, downLim, candidate): 
    if (i > downLim): 
     print candidate 
    if (i == highLim): //stop clause 
     return 
    for j in range(i,length(chars)): 
     curr <- chars[i] 
     candidate.append(curr) 
     swap(chars,i,j) // make it unavailable for repicking 
     findPermutations(chars,i+1,highLim,downLim,candidate) 
     //clean up environment after recursive call: 
     candidate.removeLast() 
     swap(chars ,i, j) 

的想法是打印每个有更多字符的“候选人”，然后downLim（在你的情况下是3），并在达到上限（highLim） - 10时终止。

在每一次，你都会“猜测”下一个字符是什么 - 然后你将它附加到候选者，并递归地调用以找到下一个候选者。
重复所有可能的猜测过程。

请注意，有选择（10,16）* 10！ +选择（9,16）* 9！ + ... +选择（3,16）* 3！不同的这样的排列，所以它可能是费时......

---

如果你想意味深长的话，你将需要某种形式的词典（或统计学提取一个从某些方面），以配合具有“真实话语”的候选人。

Answer 3

正如你不能定义我的C＃实现的首选语言：

private static readonly int[] dx = new int[] { 1, 1, 1, 0, 0, -1, -1, -1 }; 
private static readonly int[] dy = new int[] { -1, 0, 1, 1, -1, -1, 0, 1 }; 

private static List<string> words; 
private static List<string> GetAllWords(char[,] matrix ,int d) 
{ 
    words = new List<string>(); 
    bool[,] visited = new bool[4, 4]; 
    char[] result = new char[d]; 

    for (int i = 0; i < 4; i++) 
     for (int j = 0; j < 4; j++) 
      Go(matrix, result, visited, d, i, j); 

    return words; 
} 

private static void Go(char[,] matrix, char[] result, bool[,] visited, int d, int x, int y) 
{ 
    if (x < 0 || x >= 4 || y < 0 || y >= 4 || visited[x, y]) 
     return; 

    if (d == 0) 
    { 
     words.Add(new String(result)); 
     return; 
    } 

    visited[x, y] = true; 
    result[d - 1] = matrix[x, y]; 

    for (int i = 0; i < 8; i++) 
    { 
     Go(matrix, result, visited, d - 1, x + dx[i], y + dy[i]); 
    } 

    visited[x, y] = false; 
} 

代码，得到的结果：

char[,] matrix = new char[,] { { 'A', 'B', 'C', 'D' }, { 'U', 'A', 'L', 'E' }, { 'T', 'S', 'U', 'G' }, { 'N', 'E', 'Y', 'I' } }; 
    List<string> list = GetAllWords(matrix, 3); 

改变参数3到所需的文本长度。