4x4 2D character matrix permutations

Question

I have a 4x4 2D array of characters like this:

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

Now, I would need to find all the permutations of 3 characters, 4 characters, etc till 10.

So, some words that one could "find" out of this are TEN, BALD, BLUE, GUYS.

I did search SO for this and Googled, but to no concrete help. Can you push me in the right direction in which algorithm I should learn (A* maybe?). Please be gentle as I'm no algorithms guy (aren't we all (well, at least a majority :)), but am willing to learn just don't know where exactly to start.

Answer 1

Ahhh, that's the game Boggle isn't it... You don't want permutations, you want a graph and you want to find words in the graph.

Well, I would start by arranging the characters as graph nodes, and join them to their immediate and diagonal neighbours.

Now you just want to search the graph. For each of the 16 starting nodes, you're going to do a recursion. As you move to a new node, you must flag it as being used so that you can't move to it again. When you leave a node (having completely searched it) you unflag it.

I hope you see where this is going...

For each node, you will visit each of its neighbours and add that character to a string. If you have built your dictionary with this search in mind, you will immediately be able to see whether the characters you have so far are the beginning of a word. This narrows the search nicely.

The kind of dictionary I'm talking about is where you have a tree whose nodes have one child for each letter of the alphabet. The beauty of these is that you only need to store which tree node you're currently up to in the search. If you decide you've found a word, you just backtrack via the parent nodes to work out which word it is.

Using this tree style along with a depth-first graph search, you can search ALL possible word lengths at the same time. That's about the most efficient way I can think of.

---

Let me just write a pseudocodish function for your graph search:

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

And of course, to kick the whole thing off:

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

All that remains is to build the graph and the dictionary. And I just remembered what that dictionary data structure is called! It's a Trie. If you need more space-efficient storage, you can compress into a Radix Tree or similar, but by far the easiest (and fastest) is to just use a straight Trie.

Answer 2

As you not define preferred language I implemented on 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;
}

Code to get results:

    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);

Change parameter 3 to required text length.

Answer 3

It seems you just use the 4x4 matrix as an array of length 16. If it is the case, you can try the recursive approach to generate permutations up to length k as follows:

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)

The idea is to print each "candidate" that has more chars then downLim (3 in your case), and terminate when you reach the upper limit (highLim) - 10 in your case.

At each time, you "guess" which character is the next to put - and you append it to the candidate, and recursively invoke to find the next candidate.
Repeat the process for all possible guesses.

Note that there are choose(10,16)*10! + choose(9,16)*9! + ... + choose(3,16)*3! different such permutations, so it might be time consuming...

---

If you want meaningful words, you are going to need some kind of dictionary (or to statistically extract one from some context) in order to match the candidates with the "real words".