Squaring Words

		   by John Walker  --  January 1998

		This program is in the public domain.

    This program searches for solutions to the "squaring words" puzzle
    posed in the conclusion of Chapter XVIII, "Picking Locks and
    Deciphering", of Charles Babbage's autobiography, "Passages from
    the Life of a Philosopher".  For example, squaring the word
    "dean" is to fill in the missing letters in the grid:

		d e a n
		e . . .
		a . . .
		n . . .

    so that the tableau reads the same across and down.  One
    solution for "dean" is the following, given by Babbage.

		d e a n
		e a s e
		a s k s
		n e s t

    This program, used in conjunction with a spelling checker
    dictionary consisting of an ASCII text file with one word
    per line (like a Unix /usr/dict/words file), searches for
    ways to square the word given as its sole command line
    argument, printing all solutions on standard output.  If
    your system doesn't have a suitable dictionary, you can
    download the Moby Words dictionary from:


    or by FTP from:


    Get the Moby Words file, mwords.tar.Z (many of the other
    files in this directory are also interesting), uncompress
    and un-tar, and consult the readme.txt file for a description
    of the contents.  The list of 354,984 single words is an
    excellent one to use with this program.  If you are looking
    for more common words in the square, try the list of 113,809
    words from the Scrabble[tm] dictionary, or the list of
    74,550 common dictionary words.

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

#define DICT    "moby.txt"  /* Dictionary file */

#define NW	5000	    /* Maximum candidate words per initial letter */
#define MAXWORD 128	    /* Longest target word */

#define IX(x) ((x) - 'a')   /* Map lcased initial letter to array index */

#define FALSE	0
#define TRUE	1

static char *words[IX('z') + 1][NW];
static int nwl[IX('z') + 1];   
static char *target;
static int ltarget;
static char *cand[128];

/*  LCASE  --  Translate a string in place to all lower case.
	       If the string contains any non-alphabetic character
	       FALSE is returned, otherwise TRUE.  */

static int lcase(char *cp) {
    int allalpha = TRUE;

    while (*cp) {
	if (!isalpha(*cp)) {
	    allalpha = FALSE;
	if (isupper(*cp)) {
	    *cp = tolower(*cp);
    return allalpha;

/*  ISSOL  --  Test whether the words assembled so far constitute
	       a valid solution.  */

static int issol(int n) {
    int i, j;

    for (i = 1; i <= n; i++) {
	for (j = 1; j < n; j++) {
	    if (cand[i][j] != cand[j][i]) {
		return FALSE;
    return TRUE;

/*  TESTSOL  --  Test for a solution for a given letter.  Upon
		 finding a solution at that level, this function plugs
		 the candidate word into the cand[] array and calls
		 itself recursively to search for solutions for the
		 next letter.  If a solution is found for the last
		 letter, print the complete square and return.	*/

static void testsol(int letter) {
    int k, l, m;

    for (k = 0; k < nwl[IX(target[letter])]; k++) {
	char *w = words[IX(target[letter])][k];
/* printf("L = %d w = %s cand = %s\n", letter, cand[letter - 1], w); /* Show candidate tests */
	if (cand[letter - 1][letter] == w[letter - 1]) {
	    cand[letter] = w;
	    if (letter == (ltarget - 1)) {
		if (issol(letter)) {
		    for (l = 0; l <= letter; l++) {
                        printf("   ");
			for (m = 0; m < (int) strlen(cand[l]); m++) {
                            printf(" %c", cand[l][m]);
	    } else {
		if (issol(letter)) {
		    testsol(letter + 1);

/*  Main program  */

int main(int argc, char *argv[])
    FILE *fp;
    char s[132];

    if (argc == 2) {
	target = argv[1];
    } else {
        fprintf(stderr, "usage: %s word\n", argv[0]);
	return 2;

    /*	Validate and prepare target word.  */

    if (!lcase(target)) {
        fprintf(stderr, "%s: cannot square word with non-alphabetic character.\n", argv[0]);
	return 2;
    ltarget = strlen(target);

    if (ltarget > MAXWORD) {
        fprintf(stderr, "Length of target word (%d) exceeds the maximum of %d.\n",
	    ltarget, MAXWORD);
	return 2;

    /*	Load the portion of dictionary that we need into memory.  */

    memset(nwl, 0, sizeof nwl);
    fp = fopen(DICT, "r");
    if (fp == NULL) {
        fprintf(stderr, "Cannot open dictionary file: %s\n", DICT);
    while (fgets(s, sizeof s, fp)) {

	/* Chop EOL this way because some dictionaries have
	   MS-DOS CR/LF sequences. */

	while (isspace(s[strlen(s) - 1])) {
	    s[strlen(s) - 1] = 0;

	/*  Discard any dictionary entry with a non-alphabetic character
            in it.  This isn't strictly necessary, but the problem was
	    posed as a crossword puzzle, and the chance of finding
	    solutions for words with non-alphabetic characters
            (for example, "we're") is vanishingly small.  Note:
            if you're thinking of loosening this restriction, note
	    that the indexing of the radix sort by first letter
            assumes only characters between 'a' and 'z'.  If you
            permit other initial characters, you'll have to expand the
	    words[] and nwl[] arrays and modify the IX() macro accordingly.  */

	if (lcase(s)) {
	    /* Filter for words which begin with letters of the target
	       and are short enough to be candidates. */
	    if (strchr(target + 1, s[0]) != NULL && strlen(s) == ltarget) {
		int x = IX(s[0]);

		if (nwl[x] >= NW) {
                    fprintf(stderr, "Boom!!!  More than %d words starting with \"%c\".\n",
			NW, s[0]);
                    fprintf(stderr, "         Rebuild with a larger setting for #define NW\n");
		words[x][nwl[x]++] = strdup(s);
/*printf("%s\n", s);  /*  Print candidate words from dictionary  */


    /*	Print summary of candidate words.  */

    for (i = 'a'; i <= 'z'; i++) {
	if (nwl[IX(i)] > 0) {
            fprintf(stderr, "%c  %5d\n", i, nwl[IX(i)]);

    /*	Search for solutions.  */

    cand[0] = target;		      /* Set first level candidate as target word */
    testsol(1); 		      /* Invoke first level solution seeker */

    return 0;