Arranging 3 letter words in a 2D matrix such that each row, column and diagonal forms a word

Question

You are given a dictionary of 3 letter words and have to find a matrix of 3x3 such that each row, column and diagonal forms a word in the dictionary. The words in the dictionary are sorted and you can assume O(1) time for retrieving a word from the dictionary.

This has been asked as a Facebook interview question.

Answer 1

Your comment suggest you are also looking for backtracking solution, which will be not efficient, but solves this. Pseudo-Code:

solve(dictionary,matrix):
  if matrix is full:
       if validate(dictionary,matrix) == true:
            return true
        else:
            return false
  for each word in dictionary:
      dictionary -= word
      matrix.add(word)
      if solve(dictionary,matrix) == true:
          return true
      else:
          dictionary += word
           matrix.removeLast()
   return false //no solution for this matrix.

In the above pseudo-code, matrix.add() adds the given word in the first non-occupied line. matrix.remove() removes the last occupied line, and validate() checks if the solution is a legal one.

Activation: solve(dictionary,empty_matrix), if the algorithm yields true, there is a solution and the input matrix will contain it, else it will yield false.

The above pseudo-code runs in exponential time! it is very non-efficient. However, since this problem resembles(*) the crossword problem, which is NP-Complete, it might be your best shot.

(*)The original Crossword-Problem doesn't have the diagonal condition that this problem has, and is of course more general: nxm matrix, not only 3x3. Though the problems are similar, a reduction doesn't pop to my head, and I will be glad to see one if exist.

Answer 2

• You find every unique set of 3 words.
• You get all 6 possible matrices for those 3 words.
• You do a dictionary check for the 5 words that could be created from those matrices (3 columns and 2 diagonals).

Some JavaScript to illustrate.

//setup a test dictionary
var dict = [
 "MAD",
 "FAD",
 "CAT",
 "ADD",
 "DOG",
 "MOD",
 "FAM",
 "ADA",
 "DDD",
 "FDD"
];
for(var i=0; i<dict.length; i++)
 dict[dict[i]]=true;

// functions
function find(dict) {
for(var x=0; x<dict.length; x++) {
for(var y=x+1; y<dict.length; y++) {
for(var z=y+1; z<dict.length; z++) {
 var a=dict[x];
 var b=dict[y];
 var c=dict[z];
 if(valid(dict,a,b,c)) return [a,b,c];
 if(valid(dict,a,c,b)) return [a,c,b];
 if(valid(dict,b,a,c)) return [b,a,c];
 if(valid(dict,b,c,a)) return [b,c,a];
 if(valid(dict,c,a,b)) return [c,a,b];
 if(valid(dict,c,b,a)) return [c,b,a];
}
}
}
return null;
}
function valid(dict, row1, row2, row3) {
 var words = [];
 words.push(row1.charAt(0)+row2.charAt(0)+row3.charAt(0));
 words.push(row1.charAt(1)+row2.charAt(1)+row3.charAt(1));
 words.push(row1.charAt(2)+row2.charAt(2)+row3.charAt(2));
 words.push(row1.charAt(0)+row2.charAt(1)+row3.charAt(2));
 words.push(row3.charAt(0)+row2.charAt(1)+row1.charAt(2));
 for(var x=0; x<words.length; x++)
  if(dict[words[x]] == null) return false;
 return true;
}

//test
find(dict);

Answer 3

My approach would be to filter the dictionary first to create two new dictionaries: The first contains all single letter prefixes of words (of which there are probably 26), and the second contains all double letter prefixes of words (of which there are fewer than 26^2 since no word starts with BB, for example).

1. Choose a word from the dictionary, call it X. This will be the first row of the matrix.

2. Check that X1, X2, X3 are all valid single letter prefixes using that handy list you made. If they are, go on to step 3; otherwise go back to step 1.

3. Choose a word from the dictionary, call it Y. This will be the second row of the matrix.

4. Check that X1 Y1, X2 Y2, X3 Y3 are all valid double letter prefixes using that handy list you made. If they are, go on to step 5; otherwise go back to step 3. If this was the last word in the dictionary, then go all the way back to step 1.

5. Choose a word from the dictionary, call it Z. This will be the third row of the matrix.

6. Check that X1 Y1 Z1, X2 Y2 Z2, X3 Y3 Z3 are all words in the dictionary. If they are, congrats, you've done it! Otherwise go back to step 5. If this was the last word in the dictionary, then go all the way back to step 3.

I coded this up in Maple and it works reasonably well. I left it running to find all such matrices and it turns out there are enough to crash Maple due to memory overflow.