I'll just leave this puzzle here (7)

5 Name: #!/usr/bin/anonymous : 2011-05-30 05:24 ID:WiytFL3M

Figured it out bishes. I actually thought it was wrong in the beginning, but then I found out my word list didn't have the right words for bishop after I looked up the solution for bishop. Unfortunately, this is pretty inefficient, but it is better than brute force. I think around O(m n^2) where m is the number of letters in the word and n is the number of words in the dictionary.

Given word w_i, length m. (ie. w_1 is the first letter, w_2 is second letter, and so on)
We make a graph with the words as vertices and we try to find a path that would make up the square matrix.

Read all words from dictionary into sets of vertices A_i s.t
every word is length m, the set A_i has words starting with w_i.

Add edges between vertices in set A_i and A_{i+1} if x is in A_i and y is in A_{i+1}, x_{i+1} = y_i.

The idea is that we make a tree with root "bishop" and every edge we form only forms when they might fit into the matrix. It does not necessarily fit into the matrix.

Do BFS from root and find all paths of length m. A path is a potential square matrix.

Check all of the paths (square matrices) to see if any one is symmetric. If there is such a path then found it. Else we did not.

This thread has been closed. You cannot post in this thread any longer.