From: tridge@nimbus.anu.edu.au (Andrew Tridgell)
Subject: angry: a cross word builder (version 1.0)
Originator: tridge@nimbus
Organization: Australian National University, Canberra
Date: Tue, 28 Jul 92 00:26:44 GMT

I got quite a few replies from people who said that they would like a
copy of my crossword builder, so I'm now posting version 1.0. At this
stage I'm just posting source code. The main reason for this is that
the replies I got raised several queries that showed my ignorance of
crossword building. Once these are resolved (if ever) then I'll have
to organise a post of an IBM PC binary.

Before I go on I should explain that the code was produced as part of
a race. My wife tried to produce the crossword by hand (with the help
of a windows based crossword program) and I tried to write code to do
it automatically. I won, which shows the code was not designed to be
"model programming". It helped that my wife is hopeless with
crosswords.

Here are some of the questions that were raised along with some other
limitations of the code:

Q) Does it produce rotationally symmetric crosswords?

A) No. I didn't even know crosswords were supposed to be rotationally
symmetric. Why are they? I looked a few up in the paper and found that
were indeed symmetric, which I had never noticed before.


Q) Can you input your own grid?

A) No. It probably wouldn't be all that hard to re-code it to do this
but I suspect that with a short list of words you wouldn't get a high
success rate. If you fed it the whole dictionary then there wouldn't
be a problem (I think).


Q) Can it produce crosswords with no black squares? (such as 6x6 problem)

A) No. It can ONLY produce crosswords where you can place the words
one at a time so that after each word the crossword is "legal". This
precludes a whole host of possible crosswords.


Q) What is the .pzl format?

A) It's the format used by the Microsoft windows shareware program
"xword" - available from a friendly ftp site near you. Angry also
saves the puzzles in plain text, with spaces for black squares. I put
in the .pzl format so you could get pretty printouts.


Q) How does it work?

A) Brute force, with a bit of smarts built in. In concept it tries all
words in all positions then picks the word with the highest "score",
places that word then tries again. Doing this with a dictionary would
take years of course, so I then define a "depth" so the user can
compromise between speed and better crosswords. If
depth==number_of_words then it is brute force. If depth is N then do this

	1. pick N words at random
	2. find the best position for each word (highest score - see below)
	3. choose randomly from among highest scoring words
	4. place word
	5. if any words left go to 1.
	6. remove any words not connected to other words
	7. goto 1
	FINAL. If depth > 10 then do a brute force final effort.

	SCORE: 
	   +35 for connection not at the end of a word
	   +30 for connection at end of a word
	   +9 for not lying along an edge
	   +1 for being oriented differently to the last word
	(these are VERY ad hoc)

Angry gives up when it can't place any more words. It then tries to
produce another, and prints it if it is better then the first. These
keeps going till you stop the program. (press ^C under unix - press
and key under DOS)

Whenever a better xword is found it is written both to best.doc and
best.pzl.


Usage: angry Xsize Ysize WordList [depth]

Xsize: number of squares across 

Ysize: number of squares down

WordList: file containing a column of words 

depth: depth of search.  This defaults to 1 (fastest). I recommend
about 5 for normal use. If you put in 11 or high then you will
activate a brute force search at the end of the build (slow).


Q) How fast is it?

A) That depends on the depth. With a depth of 1 it produces crosswords
every few seconds on a Sun4. On a PC it may take 30 seconds to get a
crossword. The time will increase as Xsize*Ysize. It will not increase
with an increase in wordlist length (not by much anyway) unless
depth>10 in which case the final stage goes linearly with the number
of words.


Q) How big can it get?

A) The only limitation is the machines memory. Also the words can't
be longer than 1000 letters - which I don't think will be a problem
(at least in English!)



OK enought drivel for now - here is the source. Remember - it cost
nothing.

/* Angry! The cross word builder */
/* written by Andrew Tridgell (23rd July 1992) */  
/* Copyright (C) Andrew Tridgell 1992 */

/* 
Permission is given for the use or copying of this program for
non-commercial purposes. If you wish to use it for commercial purposes
then please contact the author:

Andrew Tridgell
Computer Sciences Laboratory
Australian National University
GPO BOX 4
Canberra, 2601, Australia

E-Mail: Andrew.Tridgell@anu.edu.au
*/


#define VERSION "1.0"
  
#include <stdio.h>  
#include <malloc.h>  
#include <stdlib.h>  
#include <time.h>  

enum _Direction{ACROSS,DOWN}; 
typedef enum _Direction Direction; 
typedef int BOOL; 

 
/* this structure holds the word list */
typedef struct
{
  char *word;
  int i,j;
  Direction d;
  BOOL used;
} list_struct;



#define True 1 
#define False 0 
#define CONST const 
#define LONG_STRING_LENGTH 1000
#define MAX_TRY depth 
#define MAX_FAILURES 20 
 
/* define how words will be scored */
#define SC_END 30 
#define SC_MID 35 
#define SC_NOEDGE 9 
#define SC_DIR 1 

/* min score for a word with some crossings */
#define SC_MIN_CROSSING (SC_NOEDGE + SC_DIR + 1)
 
/* these bits implement the "rotating line" */
char circle[4] = "\\|/-"; 
char lastc = 0; 
#define CIRCLE {printf("%c\r",circle[(lastc=((lastc+1)%4))]);fflush(stdout);}
 

char *strtidy(); 
void read_a_line(); 
char *my_fgets(); 
 
 
#ifndef __MSDOS__ 
#define randomize() srand(time(NULL)) 
#define BLACKSQUARE 32 
#define kbhit() False 
#else 
#define BLACKSQUARE 219 
#endif 



/* GLOBAL VARIABLES */
int xsize=0;  
int ysize=0;  
int depth=1; 
BOOL final_try=False; 
char **grid; 


 
/******************************************************************* 
create a 2D matrix of any type. The return must be cast correctly. 
********************************************************************/ 
void **any_matrix2D(int el_size,int dim1,int dim2) 
{ 
int dimension=2; 
int *dims=NULL; 
void **mat; 
int i,j,size,ptr_size,ppos,prod; 
int padding; 
void *next_ptr; 
  
/* first gather the arguments */  
  
if (dimension <= 0) return(NULL);  
if (el_size <= 0) return(NULL);  
  
dims = (int *)malloc(dimension * sizeof(int));  
if (dims == NULL) return(NULL);  
dims[0] = dim1;
dims[1] = dim2;
  
/* now we've disected the arguments we can go about the real business of  
creating the matrix */  
  
/* calculate how much space all the pointers will take up */  
ptr_size = 0;  
for (i=0;i<(dimension-1);i++)  
	{  
	prod=sizeof(void *);  
	for (j=0;j<=i;j++) prod *= dims[j];  
	ptr_size += prod;  
	}  
  
/* padding overcomes potential alignment errors */  
padding = (el_size - (ptr_size % el_size)) % el_size;  
  
/* now calculate the total memory taken by the array */  
{  
prod=el_size;  
for (i=0;i<dimension;i++) prod *= dims[i];  
size = prod + ptr_size + padding;  
}  
  
/* allocate the matrix memory */  
mat = (void **)malloc(size);  
  
if (mat == NULL)  
	{  
	fprintf(stdout,"Error allocating %d dim matrix of size %d\n",dimension,size);  
	free(dims);  
	return(NULL);  
	}  
  
/* now fill in the pointer values */  
next_ptr = (void *)&mat[dims[0]];  
ppos = 0;  
prod = 1;  
for (i=0;i<(dimension-1);i++)  
{  
int skip;  
if (i == dimension-2)   
  {  
    skip = el_size*dims[i+1];  
    next_ptr = (void *)(((char *)next_ptr) + padding); /* add in the padding */  
  }  
else  
  skip = sizeof(void *)*dims[i+1];  
  
for (j=0;j<(dims[i]*prod);j++)  
  {  
    mat[ppos++] = next_ptr;  
    next_ptr = (void *)(((char *)next_ptr) + skip);  
  }  
prod *= dims[i];  
}  
  
free(dims);  
return((void *)mat);  
}  
  
  
/*******************************************************************  
return a random number  
********************************************************************/  
int random_num(void)  
{  
return(rand());  
}  
  
  
/*******************************************************************  
this returns the number of lines in a text file  
********************************************************************/  
int num_text_lines(CONST char *fname)  
{  
FILE *file;  
int count = 0;  
char buf[2000];  
  
file = fopen(fname,"r");  
if (!file)  
  return(0);  
  
while (!feof(file))  
  {  
    read_a_line(buf,2000,file);  
    if (*buf) count++;  
  }  
  
fclose(file);  
return(count);  
}  
  
/*******************************************************************  
read a line from a file. If the line is of 0 length then read another  
********************************************************************/  
void read_a_line(char *buf,int maxlen,FILE *file)  
{  
my_fgets(buf,maxlen,file);  
if (strlen(buf) == 0)  
	my_fgets(buf,maxlen,file);  
}  
  
/*******************************************************************  
like fgets but remove trailing CR or LF  
********************************************************************/  
char *my_fgets(char *s,int n,FILE *stream)  
{  
char *ret;  
  
ret = fgets(s,n,stream);  
if (ret == NULL)   
  {  
    *s = 0;  
    return(NULL);  
  }  
  
return(strtidy(s,"\n\r "));  
}  
  
/*******************************************************************  
remove specified chars from front and back of a string   
********************************************************************/  
char *strtidy(char *str,CONST char *chars)  
{  
int len=strlen(str);  
while ((len > 0) && (strchr(chars,*str) != NULL))  
	{  
	memcpy(str,&str[1],len);  
	len--;  
	}  
while ((len > 0) && (strchr(chars,str[len-1]) != NULL))  
	{  
	str[len-1]=0;  
	len--;  
	}  
return(str);  
}  
  
  
  
  
/*******************************************************************  
load a list of words  
********************************************************************/  
list_struct *LoadWordList(char *fname,int *num)  
{  
FILE *file;  
int i;  
char line[LONG_STRING_LENGTH];  
list_struct *list;  
*num = num_text_lines(fname);  
if (*num < 1)  
  return(NULL);  
  
list = (list_struct *)malloc(sizeof(list_struct)*(*num));  
if (!list) return(NULL);

file = fopen(fname,"r");  
for (i=0;i<(*num);i++)  
  {  
    read_a_line(line,LONG_STRING_LENGTH,file);  
    list[i].word = (char *)malloc(sizeof(char)*(strlen(line)+1));
    if (!list[i].word) return(NULL);
    strcpy(list[i].word,line);  
    list[i].used = False;
  }  
fclose(file);  
  
return(list);  
}  
  
/*******************************************************************  
place a word on the grid
********************************************************************/  
void PlaceWord(char *word,int i,int j,Direction dir)  
{  
int k;  
int len=strlen(word);  
CIRCLE
if (dir == ACROSS)  
  {  
    for (k=0;k<len;k++)  
      grid[i+k][j] = word[k];  
  }  
else  
  {  
    for (k=0;k<len;k++)  
      grid[i][j+k] = word[k];  
  }  
}  


/*******************************************************************  
un_place a word  
********************************************************************/  
void UnPlaceWord(char *word,int i,int j,Direction dir)  
{  
int k;  
int len=strlen(word);
BOOL minus,plus;  
if (dir == ACROSS)  
  {  
    minus = (j!=0);
    plus = (j!=(ysize-1));
    for (k=0;k<len;k++)  
      if (!(minus && grid[i+k][j-1]) && !(plus && grid[i+k][j+1]))
	grid[i+k][j] = 0;  
  }  
else  
  {  
    minus = (i!=0);
    plus = (i!=(xsize-1));
    for (k=0;k<len;k++)  
      if (!(minus && grid[i-1][j+k]) && !(plus && grid[i+1][j+k]))
	grid[i][j+k] = 0;  
  }  
}  


/*******************************************************************  
work out how many cross overs there are for a word
********************************************************************/  
int Crossings(char *word,int i,int j,Direction dir)  
{  
int k;  
int len=strlen(word);
int res=0;
BOOL minus,plus;  
if (dir == ACROSS)  
  {  
    minus = (j!=0);
    plus = (j!=(ysize-1));
    for (k=0;k<len;k++)  
      if ((minus && grid[i+k][j-1]) || (plus && grid[i+k][j+1]))
	res++;
  }  
else  
  {  
    minus = (i!=0);
    plus = (i!=(xsize-1));
    for (k=0;k<len;k++)  
      if ((minus && grid[i-1][j+k]) || (plus && grid[i+1][j+k]))
	res++;
  }  
return(res);
}  


/*******************************************************************  
determine if a position is taken - just checks for overlaps
********************************************************************/  
BOOL Taken(list_struct *list,int num,char *word,int i,int j,Direction dir)  
{
  int len=strlen(word);
  int n;
  if (dir == ACROSS)
    for (n=0;n<num;n++)
      if (list[n].used && (list[n].d == dir) && (list[n].j == j))
	{
	  int l2=strlen(list[n].word);
	  int e1 = i+len-1;
	  int e2 = list[n].i+l2-1;
	  if (!((i>e2) || (list[n].i>e1))) return(True);
	}

  if (dir == DOWN)
    for (n=0;n<num;n++)
      if (list[n].used && (list[n].d == dir) && (list[n].i == i))
	{
	  int l2=strlen(list[n].word);
	  int e1 = j+len-1;
	  int e2 = list[n].j+l2-1;
	  if (!((j>e2) || (list[n].j>e1))) return(True);
	}

return(False);
}

  
/*******************************************************************  
determine if a word is legal in a position  
********************************************************************/  
BOOL Legal(char *word,int i,int j,Direction dir)  
{  
int len=strlen(word);  
BOOL plus,minus;
if (dir == ACROSS)  
  {  
    int k;  
    if (i+len > xsize) return(False);  
    if ((i != 0) && grid[i-1][j]) return(False);  
    if (((i+len) != xsize) && grid[i+len][j]) return(False);  
    minus = (j!=0);
    plus = (j!=(ysize-1));
    for (k=0;k<len;k++)  
      {  
	if (grid[i+k][j] && (grid[i+k][j] != word[k])) return(False);  
	if ((j != 0) && grid[i+k][j-1] && !grid[i+k][j]) return(False);  
	if ((j != (ysize-1)) && grid[i+k][j+1] && !grid[i+k][j]) return(False);  
	if (grid[i+k][j] && !((plus && grid[i+k][j+1]) || (minus && grid[i+k][j-1])))
	  return(False);
      }  
  }  
else  
  {  
    int k;  
    if (j+len > ysize) return(False);  
    if ((j != 0) && grid[i][j-1]) return(False);  
    if (((j+len) != ysize) && grid[i][j+len]) return(False);  
    minus = (i!=0);
    plus = (i!=(xsize-1));
    for (k=0;k<len;k++)  
      {  
	if (grid[i][j+k] && (grid[i][j+k] != word[k])) return(False);  
	if ((i != 0) && grid[i-1][j+k] && !grid[i][j+k]) return(False);  
	if ((i != (xsize-1)) && grid[i+1][j+k] && !grid[i][j+k]) return(False);  
	if (grid[i][j+k] && !((plus && grid[i][j+k]) || (minus && grid[i-1][j+k])))
	  return(False);
      }  
  }  
return(True);  
}  
  
/*******************************************************************  
score a word in a position  
********************************************************************/  
int Score(char *word,int i,int j,Direction dir)  
{  
int len=strlen(word);  
int score=0;  
if (dir == ACROSS)  
  {  
    int k;  
    for (k=0;k<len;k++)  
      if (grid[i+k][j])
	{  
	  if ((k == 0) || (k == (len-1)))   
	    score += SC_END;  
	  else  
	    score += SC_MID;  
	}  
    if ((j != 0) && (j != (ysize-1))) score += SC_NOEDGE;  
  }  
else  
  {  
    int k;  
    for (k=0;k<len;k++)  
      if (grid[i][j+k])
	{  
	  if ((k == 0) || (k == (len-1)))   
	    score += SC_END;  
	  else  
	    score += SC_MID;  
	}  
    if ((i != 0) && (i != (xsize-1))) score += SC_NOEDGE;  
  }  
return(score);  
}  
  
Direction last_dir=ACROSS;  
  
  
/*******************************************************************  
find the best position for a word  
********************************************************************/  
BOOL BestPosition(char *word,int *besti,int *bestj,Direction *dir)  
{  
int best;  
register int i,j;  
Direction d;  
int s;  
int len = strlen(word);  
best = -1;  
 
  
d = ACROSS;  
for (i=0;i<=(xsize-len);i++)  
  for (j=0;j<ysize;j++)  
      if (Legal(word,i,j,d))  
	{  
	  s = Score(word,i,j,d);  
	  if (last_dir != d) s += SC_DIR;  
	  if (s > best || ((s == best) && ((random_num()%(xsize*ysize/4))!=0)))  
	    {  
	      best = s;  
	      *besti = i;  
	      *bestj = j;  
	      *dir = d;  
	    }  
	}  
  
d = DOWN;  
for (i=0;i<xsize;i++)  
  for (j=0;j<=(ysize-len);j++)  
      if (Legal(word,i,j,d))  
	{  
	  s = Score(word,i,j,d);  
	  if (last_dir != d) s += SC_DIR;  
	  if (s > best || ((s == best) && ((random_num()%(xsize*ysize/4))!=0)))  
	    {  
	      best = s;  
	      *besti = i;  
	      *bestj = j;  
	      *dir = d;  
	    }  
	}  
  
return(best >= 0);  
}  
  
/*******************************************************************  
zero a crossword  
********************************************************************/  
void ZeroCrossword(list_struct *list,int num)  
{  
int i,j;  
for (i=0;i<xsize;i++)  
  for (j=0;j<ysize;j++)  
    grid[i][j] = 0;  
for (i=0;i<num;i++)
  list[i].used = False;
}  
  
  
  
/*******************************************************************  
build a crossword  
********************************************************************/  
int BuildCrossword(list_struct *list,int num,int min_score)  
{  
int i,j,n;  
Direction d;  
int remaining=0;  
int failures=0; 
int *scores = (int *)malloc(sizeof(int)*num);  

for (n=0;n<num;n++)
  if (!list[n].used) remaining++;
  
while (remaining > 0)  
  {  
    int n1,tried;  
    int choose;  
    int numbest=0,bestscore=-1;  
    int k;  
 
 
    for (i=0;i<num;i++)  
      scores[i] = -1;  

    tried=0;  

    n1 = random_num() % num;  

    for (n=n1;(n<num) && (tried++ < MAX_TRY) && !kbhit();n++)  
      if (!list[n].used && BestPosition(list[n].word,&i,&j,&d))  
	{
	  scores[n] = Score(list[n].word,i,j,d);  
	  if (scores[n] == bestscore) numbest++;  
	  if (scores[n] > bestscore)  
	    {  
	      bestscore = scores[n];  
	      numbest = 1;  
	    } 
	} 

    for (n=0;(n<n1) && (tried++ < MAX_TRY) && !kbhit();n++)  
      if (!list[n].used && BestPosition(list[n].word,&i,&j,&d))  
	{
	  scores[n] = Score(list[n].word,i,j,d);  
	  if (scores[n] == bestscore) numbest++;  
	  if (scores[n] > bestscore)  
	    {  
	      bestscore = scores[n];  
	      numbest = 1;  
	    } 
	} 

    if (kbhit()) return(0);  

    if (bestscore < min_score) 
      { 
	failures++; 
	if (failures > MAX_FAILURES) 
	  {  
	    free(scores);  
	    return(num-remaining);  
	  }  
	continue; 
      } 
    else 
      failures=0; 
    k = random_num() % numbest;  
    numbest=0;  
    for (n=0;n<num;n++)  
      if (scores[n] == bestscore)  
	{  
	  if (numbest == k) choose=n;  
	  numbest++;  
	}  
    BestPosition(list[choose].word,&i,&j,&d);  
    PlaceWord(list[choose].word,i,j,d);
    
    list[choose].used = True;  
    list[choose].i = i;
    list[choose].j = j;
    list[choose].d = d;

    remaining--;  
  }  
free(scores);  
return(num-remaining);  
}


/*******************************************************************  
try every word - place any with score greater than min_score
********************************************************************/  
int TryAllWords(list_struct *list,int num,int min_score)  
{  
  int i,j,n;  
  Direction d;  
  int res=0;

  for (n=0;n<num && !kbhit();n++)  
    if (!list[n].used && BestPosition(list[n].word,&i,&j,&d) &&
	(Score(list[n].word,i,j,d) >= min_score))
      {
	PlaceWord(list[n].word,i,j,d);
	
	list[n].used = True;  
	list[n].i = i;
	list[n].j = j;
	list[n].d = d;
	res++;
      }

return(res);  
}


/*******************************************************************  
remove all words below a specified score
********************************************************************/  
int RemoveLowCrossings(list_struct *list,int num,int min_cross)  
{  
int n;  
int removed=0;

for (n=0;(n<num);n++)  
  if (list[n].used && (Crossings(list[n].word,list[n].i,list[n].j,list[n].d) < min_cross))
    {
      UnPlaceWord(list[n].word,list[n].i,list[n].j,list[n].d);
      list[n].used = False;
      removed++;
    }
return(removed);
}  

  
/*******************************************************************  
display the crossword  
********************************************************************/  
void DisplayCrossword(FILE *f)  
{  
int i,j;  
for (j=0;j<ysize;j++)  
  {  
    for (i=0;i<xsize;i++)  
      {  
	if (grid[i][j])  
	  fputc(grid[i][j],f);  
	else  
	  fputc(BLACKSQUARE,f);  
      }  
    fputc('\n',f);  
  }  
putchar('\n');  
}  
  
  
/*******************************************************************  
save the crossword in a pzl file  
********************************************************************/  
void SavePuzzle(char *fname)  
{  
FILE *f = fopen(fname,"w");  
int i,j;  
if (!f) return;  
  
fprintf(f,"%cXWORD0%s%c%c%2d%2d",42,"Angry",3,3,xsize,ysize);  
  
for (j=0;j<ysize;j++)  
    for (i=0;i<xsize;i++)  
      fprintf(f,"%c %c",(grid[i][j]?grid[i][j]:'1'),3);  
  
fclose(f);  
}  
  
  
/*******************************************************************  
the main program
********************************************************************/  
int main(int argc,char *argv[])  
{  
char *wordfile;
list_struct *wordlist;
int num_words;

int best=-1;  
  
randomize();
if (argc < 4)  
  {  
    printf("angry: Xsize Ysize WordFile [depth]\n");  
    return(0);  
  }  

xsize = atoi(argv[1]);  
ysize = atoi(argv[2]);  
wordfile = argv[3];  
 
if (argc > 4) 
  depth = atoi(argv[4]); 
if (depth > 10) final_try = True;
  
grid = (char **)any_matrix2D(sizeof(char),xsize,ysize);  

if (!grid)  
  {  
    printf("failed to allocate memory for the crossword\n");
    return(0);  
  }  
  
wordlist = LoadWordList(wordfile,&num_words);  
if (!wordlist)
  {
    printf("Failed to read list of words from %s\n",wordfile);
    return(0);
  }


printf("Welcome to Angry - the Cross Word builder! (version %s)\n",VERSION);  
printf("please be patient.....\n\n");  
  
while (True && !kbhit())
  {  
  int n;  
  ZeroCrossword(wordlist,num_words);  
  printf("*\r");
  n = BuildCrossword(wordlist,num_words,0);  
  n -= RemoveLowCrossings(wordlist,num_words,1);
  n = BuildCrossword(wordlist,num_words,SC_MIN_CROSSING);
  n -= RemoveLowCrossings(wordlist,num_words,1);
  if (final_try)
  n += TryAllWords(wordlist,num_words,SC_MIN_CROSSING);
  if (n > best)  
    {  
      best = n;  
      printf("placed %d words\n",best);  
      {  
	FILE *f = fopen("best.doc","w");  
	if (f)
	  {
	    fprintf(f,"placed %d words\n\n",best);  
	    DisplayCrossword(f);  
	    fclose(f);
	  }
	DisplayCrossword(stdout);  
	SavePuzzle("best.pzl");  
      }  
    }  
  fflush(stdout);  
}  
return(0);  
}  
 

-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Andrew Tridgell                 CSLab, Research School of Physical Sciences
Andrew.Tridgell@anu.edu.au      Australian National University (x3064)
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-