[math-fun] Similar permutations problem

Here's a real life problem. I have a lot of strings (~20,000) which are permutations of 14 letter "words" starting with ABCDEFGHIJKLMN I suspect a lot of these words are similar, meaning they have a large number of letters in the same position. Checking for identical words is trivial - just sort and compare adjacents. Is there an approach better than the brute force 20,000! pairwise comparisons to find similar permutations? (For those who like a less abstract descriptions, the 20,000 are solutions to a set of puzzles, and I suspect a lot of the solutions are similar even though the puzzles are distinct.)