Programming for Xgrid
This section gives a sample application for Xgrid, finding all possible 4 x 4 word squares containing 10 different English words in the four horizontals, four verticals, and two diagonals (reading left to right). One example is:
How the programs work
The programs work as follows. First two words are chosen for the leftmost verticals:
Then four lists of words are looked up, giving all the words starting with the two-letter prefixes on the horizontals: "am", "ci", "ec", and "sa", and on the diagonals: "ai" and "sc".
If any of these lists is blank the search is abandoned, and the next word is tried for the second vertical.
Otherwise we try fitting all possible combinations of words from these lists in the four horizontals. For example:
Next we check that the rightmost two verticals, and the two diagonals, are all valid words.
Finally we check that all 10 words in the grid are distinct. If all these tests succees we print out the result as a valid 4 x 4 word square.
For comparison, here is the time taken to execute each program for the full list of 2360 four-letter words on a 2.66 GHz Mac Pro:
If anyone can improve the programs to reduce these times I'd be interested to know.
The programs are given here:
blog comments powered by Disqus