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:

 b  u  m  p
 a  r  e  a
 r  e  a  r
 s  a  l  t

The following pages gives equivalent examples written in Common Lisp and JavaScript.

How the programs work

The programs work as follows. First two words are chosen for the leftmost verticals:

 a  m      
 c  i      
 e  c      
 s  a      

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:

 a  m   e   n
 c  i   a   o
 e  c   r   u
 s  a   s   s

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.

Execution times

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:

Language Execution Time
Lisp 244 secs
JavaScript 497 secs

If anyone can improve the programs to reduce these times I'd be interested to know.

The programs are given here:

Lisp with Xgrid

JavaScript with Xgrid


blog comments powered by Disqus