I packaged Bill McCloskey's xword for Debian, and it's been uploaded and accepted. If you like crosswords, check it out. It works with the format used by The New York Times and other places.
So, aptitude install xword if you're running Sid, or download it.
aptitude install xword