#define kMaxSize 32 typedef char Puzzle[kMaxSize][kMaxSize]; /* referenced as [x][y] */ void Crossword( Puzzle thePuzzle, /* return solved puzzle here */ char *dictionary[], /* array of words to choose from */ long puzzleSize, /* number of rows/cols in puzzle */ long dictSize /* number of words in dictionary */ ); /* Program begins here */ #include #include #include #include /* Must be at least 32 bits, and ideally exactly 32 bits. */ typedef long letter_mask_t; typedef struct { const char *original_word; unsigned char letter[1]; /* variable-sized array of values [1, 26]. */ } move_t; /* Non-portable hack to compute size of above struct given how many * letters it has. It rounds up to sizeof(void *) to guarantee * alignment constraints are met. */ #define MOVE_SIZE(n) \ (((sizeof(void *) + (n) + (sizeof(void *) - 1)) \ / sizeof(void *)) \ * sizeof(void *)) #define NEXT_MOVE(m, n) ((move_t *) ((char *) (m) + (n))) typedef enum { CYCLENESS_UNKNOWN, IN_CYCLE, NOT_IN_CYCLE } cycleness_t; typedef struct _placement_t { /* number of entries in `move' array. */ long num_moves; /* If this == current_mark, this placement_t is "marked". We use * this for things like recursive searches. */ unsigned long mark; /* Number of letters in each entry of the `move' array. */ unsigned short letters_per_move; /* Byte size of each element in the `move' array. */ unsigned short move_size; /* Where does this start? */ unsigned short start_x, start_y; /* Direction this heads. */ unsigned short dx, dy; /* Is this partition part of a cyclic dependency? */ cycleness_t in_cycle; /* Totally done with this placement? */ char done; /* Field temporarily used during recursion. */ long depth; /* 1D index into the board where each letter is placed. */ unsigned long where[kMaxSize]; /* Other placements that intersect this one. */ struct _placement_t *neighbor[kMaxSize + 1]; /* NULL-terminated. */ /* array of variable-size objects! Don't dereference this array normally. */ move_t *move; } placement_t; /* No -1 so we can save room for NULL at the end. */ #define PLACEMENT_SIZE(n) \ (sizeof(placement_t) + (n) * sizeof(move_t *)) filter_for_length_1 static void filter_for_length_1(placement_t *p, letter_mask_t *letters_allowed, letter_mask_t *allowed_by_us) { move_t *m, *last; const letter_mask_t global_mask_0 = letters_allowed[p->where[0]]; letter_mask_t allowed_by_us_0 = 0; last = (move_t *) ((char *) p->move + (p->num_moves - 1) * MOVE_SIZE(1)); for (m = p->move; m->original_word != NULL; ) { if ( !(global_mask_0 & (1 << m->letter[0]))) { void *copy0 = ((void **)last)[0]; void *copy1 = ((void **)last)[1]; ((void **)m)[0] = copy0; ((void **)m)[1] = copy1; last->original_word = NULL; --p->num_moves; last = NEXT_MOVE(last, -MOVE_SIZE(1)); } else { allowed_by_us_0 |= 1 << m->letter[0]; m = NEXT_MOVE(m, MOVE_SIZE(1)); } } allowed_by_us[0] = allowed_by_us_0; } filter_for_length_2 static void filter_for_length_2(placement_t *p, letter_mask_t *letters_allowed, letter_mask_t *allowed_by_us) { move_t *m, *last; const letter_mask_t global_mask_0 = letters_allowed[p->where[0]]; letter_mask_t allowed_by_us_0 = 0; const letter_mask_t global_mask_1 = letters_allowed[p->where[1]]; letter_mask_t allowed_by_us_1 = 0; last = (move_t *) ((char *) p->move + (p->num_moves - 1) * MOVE_SIZE(2)); for (m = p->move; m->original_word != NULL; ) { if ( !(global_mask_0 & (1 << m->letter[0])) || !(global_mask_1 & (1 << m->letter[1]))) { void *copy0 = ((void **)last)[0]; void *copy1 = ((void **)last)[1]; ((void **)m)[0] = copy0; ((void **)m)[1] = copy1; last->original_word = NULL; --p->num_moves; last = NEXT_MOVE(last, -MOVE_SIZE(2)); } else { allowed_by_us_0 |= 1 << m->letter[0]; allowed_by_us_1 |= 1 << m->letter[1]; m = NEXT_MOVE(m, MOVE_SIZE(2)); } } allowed_by_us[0] = allowed_by_us_0; allowed_by_us[1] = allowed_by_us_1; } filter_for_length_3 static void filter_for_length_3(placement_t *p, letter_mask_t *letters_allowed, letter_mask_t *allowed_by_us) { move_t *m, *last; const letter_mask_t global_mask_0 = letters_allowed[p->where[0]]; letter_mask_t allowed_by_us_0 = 0; const letter_mask_t global_mask_1 = letters_allowed[p->where[1]]; letter_mask_t allowed_by_us_1 = 0; const letter_mask_t global_mask_2 = letters_allowed[p->where[2]]; letter_mask_t allowed_by_us_2 = 0; last = (move_t *) ((char *) p->move + (p->num_moves - 1) * MOVE_SIZE(3)); for (m = p->move; m->original_word != NULL; ) { if ( !(global_mask_0 & (1 << m->letter[0])) || !(global_mask_1 & (1 << m->letter[1])) || !(global_mask_2 & (1 << m->letter[2]))) { void *copy0 = ((void **)last)[0]; void *copy1 = ((void **)last)[1]; ((void **)m)[0] = copy0; ((void **)m)[1] = copy1; last->original_word = NULL; --p->num_moves; last = NEXT_MOVE(last, -MOVE_SIZE(3)); } else { allowed_by_us_0 |= 1 << m->letter[0]; allowed_by_us_1 |= 1 << m->letter[1]; allowed_by_us_2 |= 1 << m->letter[2]; m = NEXT_MOVE(m, MOVE_SIZE(3)); } } allowed_by_us[0] = allowed_by_us_0; allowed_by_us[1] = allowed_by_us_1; allowed_by_us[2] = allowed_by_us_2; } filter_for_length_4 static void filter_for_length_4(placement_t *p, letter_mask_t *letters_allowed, letter_mask_t *allowed_by_us) { move_t *m, *last; const letter_mask_t global_mask_0 = letters_allowed[p->where[0]]; letter_mask_t allowed_by_us_0 = 0; const letter_mask_t global_mask_1 = letters_allowed[p->where[1]]; letter_mask_t allowed_by_us_1 = 0; const letter_mask_t global_mask_2 = letters_allowed[p->where[2]]; letter_mask_t allowed_by_us_2 = 0; const letter_mask_t global_mask_3 = letters_allowed[p->where[3]]; letter_mask_t allowed_by_us_3 = 0; last = (move_t *) ((char *) p->move + (p->num_moves - 1) * MOVE_SIZE(4)); for (m = p->move; m->original_word != NULL; ) { if ( !(global_mask_0 & (1 << m->letter[0])) || !(global_mask_1 & (1 << m->letter[1])) || !(global_mask_2 & (1 << m->letter[2])) || !(global_mask_3 & (1 << m->letter[3]))) { void *copy0 = ((void **)last)[0]; void *copy1 = ((void **)last)[1]; ((void **)m)[0] = copy0; ((void **)m)[1] = copy1; last->original_word = NULL; --p->num_moves; last = NEXT_MOVE(last, -MOVE_SIZE(4)); } else { allowed_by_us_0 |= 1 << m->letter[0]; allowed_by_us_1 |= 1 << m->letter[1]; allowed_by_us_2 |= 1 << m->letter[2]; allowed_by_us_3 |= 1 << m->letter[3]; m = NEXT_MOVE(m, MOVE_SIZE(4)); } } allowed_by_us[0] = allowed_by_us_0; allowed_by_us[1] = allowed_by_us_1; allowed_by_us[2] = allowed_by_us_2; allowed_by_us[3] = allowed_by_us_3; } filter_for_length_5 static void filter_for_length_5(placement_t *p, letter_mask_t *letters_allowed, letter_mask_t *allowed_by_us) { move_t *m, *last; const letter_mask_t global_mask_0 = letters_allowed[p->where[0]]; letter_mask_t allowed_by_us_0 = 0; const letter_mask_t global_mask_1 = letters_allowed[p->where[1]]; letter_mask_t allowed_by_us_1 = 0; const letter_mask_t global_mask_2 = letters_allowed[p->where[2]]; letter_mask_t allowed_by_us_2 = 0; const letter_mask_t global_mask_3 = letters_allowed[p->where[3]]; letter_mask_t allowed_by_us_3 = 0; const letter_mask_t global_mask_4 = letters_allowed[p->where[4]]; letter_mask_t allowed_by_us_4 = 0; last = (move_t *) ((char *) p->move + (p->num_moves - 1) * MOVE_SIZE(5)); for (m = p->move; m->original_word != NULL; ) { if ( !(global_mask_0 & (1 << m->letter[0])) || !(global_mask_1 & (1 << m->letter[1])) || !(global_mask_2 & (1 << m->letter[2])) || !(global_mask_3 & (1 << m->letter[3])) || !(global_mask_4 & (1 << m->letter[4]))) { void *copy0 = ((void **)last)[0]; void *copy1 = ((void **)last)[1]; void *copy2 = ((void **)last)[2]; ((void **)m)[0] = copy0; ((void **)m)[1] = copy1; ((void **)m)[2] = copy2; last->original_word = NULL; --p->num_moves; last = NEXT_MOVE(last, -MOVE_SIZE(5)); } else { allowed_by_us_0 |= 1 << m->letter[0]; allowed_by_us_1 |= 1 << m->letter[1]; allowed_by_us_2 |= 1 << m->letter[2]; allowed_by_us_3 |= 1 << m->letter[3]; allowed_by_us_4 |= 1 << m->letter[4]; m = NEXT_MOVE(m, MOVE_SIZE(5)); } } allowed_by_us[0] = allowed_by_us_0; allowed_by_us[1] = allowed_by_us_1; allowed_by_us[2] = allowed_by_us_2; allowed_by_us[3] = allowed_by_us_3; allowed_by_us[4] = allowed_by_us_4; } filter_for_length_6 static void filter_for_length_6(placement_t *p, letter_mask_t *letters_allowed, letter_mask_t *allowed_by_us) { move_t *m, *last; const letter_mask_t global_mask_0 = letters_allowed[p->where[0]]; letter_mask_t allowed_by_us_0 = 0; const letter_mask_t global_mask_1 = letters_allowed[p->where[1]]; letter_mask_t allowed_by_us_1 = 0; const letter_mask_t global_mask_2 = letters_allowed[p->where[2]]; letter_mask_t allowed_by_us_2 = 0; const letter_mask_t global_mask_3 = letters_allowed[p->where[3]]; letter_mask_t allowed_by_us_3 = 0; const letter_mask_t global_mask_4 = letters_allowed[p->where[4]]; letter_mask_t allowed_by_us_4 = 0; const letter_mask_t global_mask_5 = letters_allowed[p->where[5]]; letter_mask_t allowed_by_us_5 = 0; last = (move_t *) ((char *) p->move + (p->num_moves - 1) * MOVE_SIZE(6)); for (m = p->move; m->original_word != NULL; ) { if ( !(global_mask_0 & (1 << m->letter[0])) || !(global_mask_1 & (1 << m->letter[1])) || !(global_mask_2 & (1 << m->letter[2])) || !(global_mask_3 & (1 << m->letter[3])) || !(global_mask_4 & (1 << m->letter[4])) || !(global_mask_5 & (1 << m->letter[5]))) { void *copy0 = ((void **)last)[0]; void *copy1 = ((void **)last)[1]; void *copy2 = ((void **)last)[2]; ((void **)m)[0] = copy0; ((void **)m)[1] = copy1; ((void **)m)[2] = copy2; last->original_word = NULL; --p->num_moves; last = NEXT_MOVE(last, -MOVE_SIZE(6)); } else { allowed_by_us_0 |= 1 << m->letter[0]; allowed_by_us_1 |= 1 << m->letter[1]; allowed_by_us_2 |= 1 << m->letter[2]; allowed_by_us_3 |= 1 << m->letter[3]; allowed_by_us_4 |= 1 << m->letter[4]; allowed_by_us_5 |= 1 << m->letter[5]; m = NEXT_MOVE(m, MOVE_SIZE(6)); } } allowed_by_us[0] = allowed_by_us_0; allowed_by_us[1] = allowed_by_us_1; allowed_by_us[2] = allowed_by_us_2; allowed_by_us[3] = allowed_by_us_3; allowed_by_us[4] = allowed_by_us_4; allowed_by_us[5] = allowed_by_us_5; } filter_for_length_7 static void filter_for_length_7(placement_t *p, letter_mask_t *letters_allowed, letter_mask_t *allowed_by_us) { move_t *m, *last; const letter_mask_t global_mask_0 = letters_allowed[p->where[0]]; letter_mask_t allowed_by_us_0 = 0; const letter_mask_t global_mask_1 = letters_allowed[p->where[1]]; letter_mask_t allowed_by_us_1 = 0; const letter_mask_t global_mask_2 = letters_allowed[p->where[2]]; letter_mask_t allowed_by_us_2 = 0; const letter_mask_t global_mask_3 = letters_allowed[p->where[3]]; letter_mask_t allowed_by_us_3 = 0; const letter_mask_t global_mask_4 = letters_allowed[p->where[4]]; letter_mask_t allowed_by_us_4 = 0; const letter_mask_t global_mask_5 = letters_allowed[p->where[5]]; letter_mask_t allowed_by_us_5 = 0; const letter_mask_t global_mask_6 = letters_allowed[p->where[6]]; letter_mask_t allowed_by_us_6 = 0; last = (move_t *) ((char *) p->move + (p->num_moves - 1) * MOVE_SIZE(7)); for (m = p->move; m->original_word != NULL; ) { if ( !(global_mask_0 & (1 << m->letter[0])) || !(global_mask_1 & (1 << m->letter[1])) || !(global_mask_2 & (1 << m->letter[2])) || !(global_mask_3 & (1 << m->letter[3])) || !(global_mask_4 & (1 << m->letter[4])) || !(global_mask_5 & (1 << m->letter[5])) || !(global_mask_6 & (1 << m->letter[6]))) { void *copy0 = ((void **)last)[0]; void *copy1 = ((void **)last)[1]; void *copy2 = ((void **)last)[2]; ((void **)m)[0] = copy0; ((void **)m)[1] = copy1; ((void **)m)[2] = copy2; last->original_word = NULL; --p->num_moves; last = NEXT_MOVE(last, -MOVE_SIZE(7)); } else { allowed_by_us_0 |= 1 << m->letter[0]; allowed_by_us_1 |= 1 << m->letter[1]; allowed_by_us_2 |= 1 << m->letter[2]; allowed_by_us_3 |= 1 << m->letter[3]; allowed_by_us_4 |= 1 << m->letter[4]; allowed_by_us_5 |= 1 << m->letter[5]; allowed_by_us_6 |= 1 << m->letter[6]; m = NEXT_MOVE(m, MOVE_SIZE(7)); } } allowed_by_us[0] = allowed_by_us_0; allowed_by_us[1] = allowed_by_us_1; allowed_by_us[2] = allowed_by_us_2; allowed_by_us[3] = allowed_by_us_3; allowed_by_us[4] = allowed_by_us_4; allowed_by_us[5] = allowed_by_us_5; allowed_by_us[6] = allowed_by_us_6; } filter_for_length_8 static void filter_for_length_8(placement_t *p, letter_mask_t *letters_allowed, letter_mask_t *allowed_by_us) { move_t *m, *last; const letter_mask_t global_mask_0 = letters_allowed[p->where[0]]; letter_mask_t allowed_by_us_0 = 0; const letter_mask_t global_mask_1 = letters_allowed[p->where[1]]; letter_mask_t allowed_by_us_1 = 0; const letter_mask_t global_mask_2 = letters_allowed[p->where[2]]; letter_mask_t allowed_by_us_2 = 0; const letter_mask_t global_mask_3 = letters_allowed[p->where[3]]; letter_mask_t allowed_by_us_3 = 0; const letter_mask_t global_mask_4 = letters_allowed[p->where[4]]; letter_mask_t allowed_by_us_4 = 0; const letter_mask_t global_mask_5 = letters_allowed[p->where[5]]; letter_mask_t allowed_by_us_5 = 0; const letter_mask_t global_mask_6 = letters_allowed[p->where[6]]; letter_mask_t allowed_by_us_6 = 0; const letter_mask_t global_mask_7 = letters_allowed[p->where[7]]; letter_mask_t allowed_by_us_7 = 0; last = (move_t *) ((char *) p->move + (p->num_moves - 1) * MOVE_SIZE(8)); for (m = p->move; m->original_word != NULL; ) { if ( !(global_mask_0 & (1 << m->letter[0])) || !(global_mask_1 & (1 << m->letter[1])) || !(global_mask_2 & (1 << m->letter[2])) || !(global_mask_3 & (1 << m->letter[3])) || !(global_mask_4 & (1 << m->letter[4])) || !(global_mask_5 & (1 << m->letter[5])) || !(global_mask_6 & (1 << m->letter[6])) || !(global_mask_7 & (1 << m->letter[7]))) { void *copy0 = ((void **)last)[0]; void *copy1 = ((void **)last)[1]; void *copy2 = ((void **)last)[2]; ((void **)m)[0] = copy0; ((void **)m)[1] = copy1; ((void **)m)[2] = copy2; last->original_word = NULL; --p->num_moves; last = NEXT_MOVE(last, -MOVE_SIZE(8)); } else { allowed_by_us_0 |= 1 << m->letter[0]; allowed_by_us_1 |= 1 << m->letter[1]; allowed_by_us_2 |= 1 << m->letter[2]; allowed_by_us_3 |= 1 << m->letter[3]; allowed_by_us_4 |= 1 << m->letter[4]; allowed_by_us_5 |= 1 << m->letter[5]; allowed_by_us_6 |= 1 << m->letter[6]; allowed_by_us_7 |= 1 << m->letter[7]; m = NEXT_MOVE(m, MOVE_SIZE(8)); } } allowed_by_us[0] = allowed_by_us_0; allowed_by_us[1] = allowed_by_us_1; allowed_by_us[2] = allowed_by_us_2; allowed_by_us[3] = allowed_by_us_3; allowed_by_us[4] = allowed_by_us_4; allowed_by_us[5] = allowed_by_us_5; allowed_by_us[6] = allowed_by_us_6; allowed_by_us[7] = allowed_by_us_7; } filter_for_length_9 static void filter_for_length_9(placement_t *p, letter_mask_t *letters_allowed, letter_mask_t *allowed_by_us) { move_t *m, *last; const letter_mask_t global_mask_0 = letters_allowed[p->where[0]]; letter_mask_t allowed_by_us_0 = 0; const letter_mask_t global_mask_1 = letters_allowed[p->where[1]]; letter_mask_t allowed_by_us_1 = 0; const letter_mask_t global_mask_2 = letters_allowed[p->where[2]]; letter_mask_t allowed_by_us_2 = 0; const letter_mask_t global_mask_3 = letters_allowed[p->where[3]]; letter_mask_t allowed_by_us_3 = 0; const letter_mask_t global_mask_4 = letters_allowed[p->where[4]]; letter_mask_t allowed_by_us_4 = 0; const letter_mask_t global_mask_5 = letters_allowed[p->where[5]]; letter_mask_t allowed_by_us_5 = 0; const letter_mask_t global_mask_6 = letters_allowed[p->where[6]]; letter_mask_t allowed_by_us_6 = 0; const letter_mask_t global_mask_7 = letters_allowed[p->where[7]]; letter_mask_t allowed_by_us_7 = 0; const letter_mask_t global_mask_8 = letters_allowed[p->where[8]]; letter_mask_t allowed_by_us_8 = 0; last = (move_t *) ((char *) p->move + (p->num_moves - 1) * MOVE_SIZE(9)); for (m = p->move; m->original_word != NULL; ) { if ( !(global_mask_0 & (1 << m->letter[0])) || !(global_mask_1 & (1 << m->letter[1])) || !(global_mask_2 & (1 << m->letter[2])) || !(global_mask_3 & (1 << m->letter[3])) || !(global_mask_4 & (1 << m->letter[4])) || !(global_mask_5 & (1 << m->letter[5])) || !(global_mask_6 & (1 << m->letter[6])) || !(global_mask_7 & (1 << m->letter[7])) || !(global_mask_8 & (1 << m->letter[8]))) { void *copy0 = ((void **)last)[0]; void *copy1 = ((void **)last)[1]; void *copy2 = ((void **)last)[2]; void *copy3 = ((void **)last)[3]; ((void **)m)[0] = copy0; ((void **)m)[1] = copy1; ((void **)m)[2] = copy2; ((void **)m)[3] = copy3; last->original_word = NULL; --p->num_moves; last = NEXT_MOVE(last, -MOVE_SIZE(9)); } else { allowed_by_us_0 |= 1 << m->letter[0]; allowed_by_us_1 |= 1 << m->letter[1]; allowed_by_us_2 |= 1 << m->letter[2]; allowed_by_us_3 |= 1 << m->letter[3]; allowed_by_us_4 |= 1 << m->letter[4]; allowed_by_us_5 |= 1 << m->letter[5]; allowed_by_us_6 |= 1 << m->letter[6]; allowed_by_us_7 |= 1 << m->letter[7]; allowed_by_us_8 |= 1 << m->letter[8]; m = NEXT_MOVE(m, MOVE_SIZE(9)); } } allowed_by_us[0] = allowed_by_us_0; allowed_by_us[1] = allowed_by_us_1; allowed_by_us[2] = allowed_by_us_2; allowed_by_us[3] = allowed_by_us_3; allowed_by_us[4] = allowed_by_us_4; allowed_by_us[5] = allowed_by_us_5; allowed_by_us[6] = allowed_by_us_6; allowed_by_us[7] = allowed_by_us_7; allowed_by_us[8] = allowed_by_us_8; } filter_for_length_10 static void filter_for_length_10(placement_t *p, letter_mask_t *letters_allowed, letter_mask_t *allowed_by_us) { move_t *m, *last; const letter_mask_t global_mask_0 = letters_allowed[p->where[0]]; letter_mask_t allowed_by_us_0 = 0; const letter_mask_t global_mask_1 = letters_allowed[p->where[1]]; letter_mask_t allowed_by_us_1 = 0; const letter_mask_t global_mask_2 = letters_allowed[p->where[2]]; letter_mask_t allowed_by_us_2 = 0; const letter_mask_t global_mask_3 = letters_allowed[p->where[3]]; letter_mask_t allowed_by_us_3 = 0; const letter_mask_t global_mask_4 = letters_allowed[p->where[4]]; letter_mask_t allowed_by_us_4 = 0; const letter_mask_t global_mask_5 = letters_allowed[p->where[5]]; letter_mask_t allowed_by_us_5 = 0; const letter_mask_t global_mask_6 = letters_allowed[p->where[6]]; letter_mask_t allowed_by_us_6 = 0; const letter_mask_t global_mask_7 = letters_allowed[p->where[7]]; letter_mask_t allowed_by_us_7 = 0; const letter_mask_t global_mask_8 = letters_allowed[p->where[8]]; letter_mask_t allowed_by_us_8 = 0; const letter_mask_t global_mask_9 = letters_allowed[p->where[9]]; letter_mask_t allowed_by_us_9 = 0; last = (move_t *) ((char *) p->move + (p->num_moves - 1) * MOVE_SIZE(10)); for (m = p->move; m->original_word != NULL; ) { if ( !(global_mask_0 & (1 << m->letter[0])) || !(global_mask_1 & (1 << m->letter[1])) || !(global_mask_2 & (1 << m->letter[2])) || !(global_mask_3 & (1 << m->letter[3])) || !(global_mask_4 & (1 << m->letter[4])) || !(global_mask_5 & (1 << m->letter[5])) || !(global_mask_6 & (1 << m->letter[6])) || !(global_mask_7 & (1 << m->letter[7])) || !(global_mask_8 & (1 << m->letter[8])) || !(global_mask_9 & (1 << m->letter[9]))) { void *copy0 = ((void **)last)[0]; void *copy1 = ((void **)last)[1]; void *copy2 = ((void **)last)[2]; void *copy3 = ((void **)last)[3]; ((void **)m)[0] = copy0; ((void **)m)[1] = copy1; ((void **)m)[2] = copy2; ((void **)m)[3] = copy3; last->original_word = NULL; --p->num_moves; last = NEXT_MOVE(last, -MOVE_SIZE(10)); } else { allowed_by_us_0 |= 1 << m->letter[0]; allowed_by_us_1 |= 1 << m->letter[1]; allowed_by_us_2 |= 1 << m->letter[2]; allowed_by_us_3 |= 1 << m->letter[3]; allowed_by_us_4 |= 1 << m->letter[4]; allowed_by_us_5 |= 1 << m->letter[5]; allowed_by_us_6 |= 1 << m->letter[6]; allowed_by_us_7 |= 1 << m->letter[7]; allowed_by_us_8 |= 1 << m->letter[8]; allowed_by_us_9 |= 1 << m->letter[9]; m = NEXT_MOVE(m, MOVE_SIZE(10)); } } allowed_by_us[0] = allowed_by_us_0; allowed_by_us[1] = allowed_by_us_1; allowed_by_us[2] = allowed_by_us_2; allowed_by_us[3] = allowed_by_us_3; allowed_by_us[4] = allowed_by_us_4; allowed_by_us[5] = allowed_by_us_5; allowed_by_us[6] = allowed_by_us_6; allowed_by_us[7] = allowed_by_us_7; allowed_by_us[8] = allowed_by_us_8; allowed_by_us[9] = allowed_by_us_9; } filter_for_length_11 static void filter_for_length_11(placement_t *p, letter_mask_t *letters_allowed, letter_mask_t *allowed_by_us) { move_t *m, *last; const letter_mask_t global_mask_0 = letters_allowed[p->where[0]]; letter_mask_t allowed_by_us_0 = 0; const letter_mask_t global_mask_1 = letters_allowed[p->where[1]]; letter_mask_t allowed_by_us_1 = 0; const letter_mask_t global_mask_2 = letters_allowed[p->where[2]]; letter_mask_t allowed_by_us_2 = 0; const letter_mask_t global_mask_3 = letters_allowed[p->where[3]]; letter_mask_t allowed_by_us_3 = 0; const letter_mask_t global_mask_4 = letters_allowed[p->where[4]]; letter_mask_t allowed_by_us_4 = 0; const letter_mask_t global_mask_5 = letters_allowed[p->where[5]]; letter_mask_t allowed_by_us_5 = 0; const letter_mask_t global_mask_6 = letters_allowed[p->where[6]]; letter_mask_t allowed_by_us_6 = 0; const letter_mask_t global_mask_7 = letters_allowed[p->where[7]]; letter_mask_t allowed_by_us_7 = 0; const letter_mask_t global_mask_8 = letters_allowed[p->where[8]]; letter_mask_t allowed_by_us_8 = 0; const letter_mask_t global_mask_9 = letters_allowed[p->where[9]]; letter_mask_t allowed_by_us_9 = 0; const letter_mask_t global_mask_10 = letters_allowed[p->where[10]]; letter_mask_t allowed_by_us_10 = 0; last = (move_t *) ((char *) p->move + (p->num_moves - 1) * MOVE_SIZE(11)); for (m = p->move; m->original_word != NULL; ) { if ( !(global_mask_0 & (1 << m->letter[0])) || !(global_mask_1 & (1 << m->letter[1])) || !(global_mask_2 & (1 << m->letter[2])) || !(global_mask_3 & (1 << m->letter[3])) || !(global_mask_4 & (1 << m->letter[4])) || !(global_mask_5 & (1 << m->letter[5])) || !(global_mask_6 & (1 << m->letter[6])) || !(global_mask_7 & (1 << m->letter[7])) || !(global_mask_8 & (1 << m->letter[8])) || !(global_mask_9 & (1 << m->letter[9])) || !(global_mask_10 & (1 << m->letter[10]))) { void *copy0 = ((void **)last)[0]; void *copy1 = ((void **)last)[1]; void *copy2 = ((void **)last)[2]; void *copy3 = ((void **)last)[3]; ((void **)m)[0] = copy0; ((void **)m)[1] = copy1; ((void **)m)[2] = copy2; ((void **)m)[3] = copy3; last->original_word = NULL; --p->num_moves; last = NEXT_MOVE(last, -MOVE_SIZE(11)); } else { allowed_by_us_0 |= 1 << m->letter[0]; allowed_by_us_1 |= 1 << m->letter[1]; allowed_by_us_2 |= 1 << m->letter[2]; allowed_by_us_3 |= 1 << m->letter[3]; allowed_by_us_4 |= 1 << m->letter[4]; allowed_by_us_5 |= 1 << m->letter[5]; allowed_by_us_6 |= 1 << m->letter[6]; allowed_by_us_7 |= 1 << m->letter[7]; allowed_by_us_8 |= 1 << m->letter[8]; allowed_by_us_9 |= 1 << m->letter[9]; allowed_by_us_10 |= 1 << m->letter[10]; m = NEXT_MOVE(m, MOVE_SIZE(11)); } } allowed_by_us[0] = allowed_by_us_0; allowed_by_us[1] = allowed_by_us_1; allowed_by_us[2] = allowed_by_us_2; allowed_by_us[3] = allowed_by_us_3; allowed_by_us[4] = allowed_by_us_4; allowed_by_us[5] = allowed_by_us_5; allowed_by_us[6] = allowed_by_us_6; allowed_by_us[7] = allowed_by_us_7; allowed_by_us[8] = allowed_by_us_8; allowed_by_us[9] = allowed_by_us_9; allowed_by_us[10] = allowed_by_us_10; } filter_for_length_12 static void filter_for_length_12(placement_t *p, letter_mask_t *letters_allowed, letter_mask_t *allowed_by_us) { move_t *m, *last; const letter_mask_t global_mask_0 = letters_allowed[p->where[0]]; letter_mask_t allowed_by_us_0 = 0; const letter_mask_t global_mask_1 = letters_allowed[p->where[1]]; letter_mask_t allowed_by_us_1 = 0; const letter_mask_t global_mask_2 = letters_allowed[p->where[2]]; letter_mask_t allowed_by_us_2 = 0; const letter_mask_t global_mask_3 = letters_allowed[p->where[3]]; letter_mask_t allowed_by_us_3 = 0; const letter_mask_t global_mask_4 = letters_allowed[p->where[4]]; letter_mask_t allowed_by_us_4 = 0; const letter_mask_t global_mask_5 = letters_allowed[p->where[5]]; letter_mask_t allowed_by_us_5 = 0; const letter_mask_t global_mask_6 = letters_allowed[p->where[6]]; letter_mask_t allowed_by_us_6 = 0; const letter_mask_t global_mask_7 = letters_allowed[p->where[7]]; letter_mask_t allowed_by_us_7 = 0; const letter_mask_t global_mask_8 = letters_allowed[p->where[8]]; letter_mask_t allowed_by_us_8 = 0; const letter_mask_t global_mask_9 = letters_allowed[p->where[9]]; letter_mask_t allowed_by_us_9 = 0; const letter_mask_t global_mask_10 = letters_allowed[p->where[10]]; letter_mask_t allowed_by_us_10 = 0; const letter_mask_t global_mask_11 = letters_allowed[p->where[11]]; letter_mask_t allowed_by_us_11 = 0; last = (move_t *) ((char *) p->move + (p->num_moves - 1) * MOVE_SIZE(12)); for (m = p->move; m->original_word != NULL; ) { if ( !(global_mask_0 & (1 << m->letter[0])) || !(global_mask_1 & (1 << m->letter[1])) || !(global_mask_2 & (1 << m->letter[2])) || !(global_mask_3 & (1 << m->letter[3])) || !(global_mask_4 & (1 << m->letter[4])) || !(global_mask_5 & (1 << m->letter[5])) || !(global_mask_6 & (1 << m->letter[6])) || !(global_mask_7 & (1 << m->letter[7])) || !(global_mask_8 & (1 << m->letter[8])) || !(global_mask_9 & (1 << m->letter[9])) || !(global_mask_10 & (1 << m->letter[10])) || !(global_mask_11 & (1 << m->letter[11]))) { void *copy0 = ((void **)last)[0]; void *copy1 = ((void **)last)[1]; void *copy2 = ((void **)last)[2]; void *copy3 = ((void **)last)[3]; ((void **)m)[0] = copy0; ((void **)m)[1] = copy1; ((void **)m)[2] = copy2; ((void **)m)[3] = copy3; last->original_word = NULL; --p->num_moves; last = NEXT_MOVE(last, -MOVE_SIZE(12)); } else { allowed_by_us_0 |= 1 << m->letter[0]; allowed_by_us_1 |= 1 << m->letter[1]; allowed_by_us_2 |= 1 << m->letter[2]; allowed_by_us_3 |= 1 << m->letter[3]; allowed_by_us_4 |= 1 << m->letter[4]; allowed_by_us_5 |= 1 << m->letter[5]; allowed_by_us_6 |= 1 << m->letter[6]; allowed_by_us_7 |= 1 << m->letter[7]; allowed_by_us_8 |= 1 << m->letter[8]; allowed_by_us_9 |= 1 << m->letter[9]; allowed_by_us_10 |= 1 << m->letter[10]; allowed_by_us_11 |= 1 << m->letter[11]; m = NEXT_MOVE(m, MOVE_SIZE(12)); } } allowed_by_us[0] = allowed_by_us_0; allowed_by_us[1] = allowed_by_us_1; allowed_by_us[2] = allowed_by_us_2; allowed_by_us[3] = allowed_by_us_3; allowed_by_us[4] = allowed_by_us_4; allowed_by_us[5] = allowed_by_us_5; allowed_by_us[6] = allowed_by_us_6; allowed_by_us[7] = allowed_by_us_7; allowed_by_us[8] = allowed_by_us_8; allowed_by_us[9] = allowed_by_us_9; allowed_by_us[10] = allowed_by_us_10; allowed_by_us[11] = allowed_by_us_11; } filter_for_length_13 static void filter_for_length_13(placement_t *p, letter_mask_t *letters_allowed, letter_mask_t *allowed_by_us) { move_t *m, *last; const letter_mask_t global_mask_0 = letters_allowed[p->where[0]]; letter_mask_t allowed_by_us_0 = 0; const letter_mask_t global_mask_1 = letters_allowed[p->where[1]]; letter_mask_t allowed_by_us_1 = 0; const letter_mask_t global_mask_2 = letters_allowed[p->where[2]]; letter_mask_t allowed_by_us_2 = 0; const letter_mask_t global_mask_3 = letters_allowed[p->where[3]]; letter_mask_t allowed_by_us_3 = 0; const letter_mask_t global_mask_4 = letters_allowed[p->where[4]]; letter_mask_t allowed_by_us_4 = 0; const letter_mask_t global_mask_5 = letters_allowed[p->where[5]]; letter_mask_t allowed_by_us_5 = 0; const letter_mask_t global_mask_6 = letters_allowed[p->where[6]]; letter_mask_t allowed_by_us_6 = 0; const letter_mask_t global_mask_7 = letters_allowed[p->where[7]]; letter_mask_t allowed_by_us_7 = 0; const letter_mask_t global_mask_8 = letters_allowed[p->where[8]]; letter_mask_t allowed_by_us_8 = 0; const letter_mask_t global_mask_9 = letters_allowed[p->where[9]]; letter_mask_t allowed_by_us_9 = 0; const letter_mask_t global_mask_10 = letters_allowed[p->where[10]]; letter_mask_t allowed_by_us_10 = 0; const letter_mask_t global_mask_11 = letters_allowed[p->where[11]]; letter_mask_t allowed_by_us_11 = 0; const letter_mask_t global_mask_12 = letters_allowed[p->where[12]]; letter_mask_t allowed_by_us_12 = 0; last = (move_t *) ((char *) p->move + (p->num_moves - 1) * MOVE_SIZE(13)); for (m = p->move; m->original_word != NULL; ) { if ( !(global_mask_0 & (1 << m->letter[0])) || !(global_mask_1 & (1 << m->letter[1])) || !(global_mask_2 & (1 << m->letter[2])) || !(global_mask_3 & (1 << m->letter[3])) || !(global_mask_4 & (1 << m->letter[4])) || !(global_mask_5 & (1 << m->letter[5])) || !(global_mask_6 & (1 << m->letter[6])) || !(global_mask_7 & (1 << m->letter[7])) || !(global_mask_8 & (1 << m->letter[8])) || !(global_mask_9 & (1 << m->letter[9])) || !(global_mask_10 & (1 << m->letter[10])) || !(global_mask_11 & (1 << m->letter[11])) || !(global_mask_12 & (1 << m->letter[12]))) { void *copy0 = ((void **)last)[0]; void *copy1 = ((void **)last)[1]; void *copy2 = ((void **)last)[2]; void *copy3 = ((void **)last)[3]; void *copy4 = ((void **)last)[4]; ((void **)m)[0] = copy0; ((void **)m)[1] = copy1; ((void **)m)[2] = copy2; ((void **)m)[3] = copy3; ((void **)m)[4] = copy4; last->original_word = NULL; --p->num_moves; last = NEXT_MOVE(last, -MOVE_SIZE(13)); } else { allowed_by_us_0 |= 1 << m->letter[0]; allowed_by_us_1 |= 1 << m->letter[1]; allowed_by_us_2 |= 1 << m->letter[2]; allowed_by_us_3 |= 1 << m->letter[3]; allowed_by_us_4 |= 1 << m->letter[4]; allowed_by_us_5 |= 1 << m->letter[5]; allowed_by_us_6 |= 1 << m->letter[6]; allowed_by_us_7 |= 1 << m->letter[7]; allowed_by_us_8 |= 1 << m->letter[8]; allowed_by_us_9 |= 1 << m->letter[9]; allowed_by_us_10 |= 1 << m->letter[10]; allowed_by_us_11 |= 1 << m->letter[11]; allowed_by_us_12 |= 1 << m->letter[12]; m = NEXT_MOVE(m, MOVE_SIZE(13)); } } allowed_by_us[0] = allowed_by_us_0; allowed_by_us[1] = allowed_by_us_1; allowed_by_us[2] = allowed_by_us_2; allowed_by_us[3] = allowed_by_us_3; allowed_by_us[4] = allowed_by_us_4; allowed_by_us[5] = allowed_by_us_5; allowed_by_us[6] = allowed_by_us_6; allowed_by_us[7] = allowed_by_us_7; allowed_by_us[8] = allowed_by_us_8; allowed_by_us[9] = allowed_by_us_9; allowed_by_us[10] = allowed_by_us_10; allowed_by_us[11] = allowed_by_us_11; allowed_by_us[12] = allowed_by_us_12; } filter_for_length_14 static void filter_for_length_14(placement_t *p, letter_mask_t *letters_allowed, letter_mask_t *allowed_by_us) { move_t *m, *last; const letter_mask_t global_mask_0 = letters_allowed[p->where[0]]; letter_mask_t allowed_by_us_0 = 0; const letter_mask_t global_mask_1 = letters_allowed[p->where[1]]; letter_mask_t allowed_by_us_1 = 0; const letter_mask_t global_mask_2 = letters_allowed[p->where[2]]; letter_mask_t allowed_by_us_2 = 0; const letter_mask_t global_mask_3 = letters_allowed[p->where[3]]; letter_mask_t allowed_by_us_3 = 0; const letter_mask_t global_mask_4 = letters_allowed[p->where[4]]; letter_mask_t allowed_by_us_4 = 0; const letter_mask_t global_mask_5 = letters_allowed[p->where[5]]; letter_mask_t allowed_by_us_5 = 0; const letter_mask_t global_mask_6 = letters_allowed[p->where[6]]; letter_mask_t allowed_by_us_6 = 0; const letter_mask_t global_mask_7 = letters_allowed[p->where[7]]; letter_mask_t allowed_by_us_7 = 0; const letter_mask_t global_mask_8 = letters_allowed[p->where[8]]; letter_mask_t allowed_by_us_8 = 0; const letter_mask_t global_mask_9 = letters_allowed[p->where[9]]; letter_mask_t allowed_by_us_9 = 0; const letter_mask_t global_mask_10 = letters_allowed[p->where[10]]; letter_mask_t allowed_by_us_10 = 0; const letter_mask_t global_mask_11 = letters_allowed[p->where[11]]; letter_mask_t allowed_by_us_11 = 0; const letter_mask_t global_mask_12 = letters_allowed[p->where[12]]; letter_mask_t allowed_by_us_12 = 0; const letter_mask_t global_mask_13 = letters_allowed[p->where[13]]; letter_mask_t allowed_by_us_13 = 0; last = (move_t *) ((char *) p->move + (p->num_moves - 1) * MOVE_SIZE(14)); for (m = p->move; m->original_word != NULL; ) { if ( !(global_mask_0 & (1 << m->letter[0])) || !(global_mask_1 & (1 << m->letter[1])) || !(global_mask_2 & (1 << m->letter[2])) || !(global_mask_3 & (1 << m->letter[3])) || !(global_mask_4 & (1 << m->letter[4])) || !(global_mask_5 & (1 << m->letter[5])) || !(global_mask_6 & (1 << m->letter[6])) || !(global_mask_7 & (1 << m->letter[7])) || !(global_mask_8 & (1 << m->letter[8])) || !(global_mask_9 & (1 << m->letter[9])) || !(global_mask_10 & (1 << m->letter[10])) || !(global_mask_11 & (1 << m->letter[11])) || !(global_mask_12 & (1 << m->letter[12])) || !(global_mask_13 & (1 << m->letter[13]))) { void *copy0 = ((void **)last)[0]; void *copy1 = ((void **)last)[1]; void *copy2 = ((void **)last)[2]; void *copy3 = ((void **)last)[3]; void *copy4 = ((void **)last)[4]; ((void **)m)[0] = copy0; ((void **)m)[1] = copy1; ((void **)m)[2] = copy2; ((void **)m)[3] = copy3; ((void **)m)[4] = copy4; last->original_word = NULL; --p->num_moves; last = NEXT_MOVE(last, -MOVE_SIZE(14)); } else { allowed_by_us_0 |= 1 << m->letter[0]; allowed_by_us_1 |= 1 << m->letter[1]; allowed_by_us_2 |= 1 << m->letter[2]; allowed_by_us_3 |= 1 << m->letter[3]; allowed_by_us_4 |= 1 << m->letter[4]; allowed_by_us_5 |= 1 << m->letter[5]; allowed_by_us_6 |= 1 << m->letter[6]; allowed_by_us_7 |= 1 << m->letter[7]; allowed_by_us_8 |= 1 << m->letter[8]; allowed_by_us_9 |= 1 << m->letter[9]; allowed_by_us_10 |= 1 << m->letter[10]; allowed_by_us_11 |= 1 << m->letter[11]; allowed_by_us_12 |= 1 << m->letter[12]; allowed_by_us_13 |= 1 << m->letter[13]; m = NEXT_MOVE(m, MOVE_SIZE(14)); } } allowed_by_us[0] = allowed_by_us_0; allowed_by_us[1] = allowed_by_us_1; allowed_by_us[2] = allowed_by_us_2; allowed_by_us[3] = allowed_by_us_3; allowed_by_us[4] = allowed_by_us_4; allowed_by_us[5] = allowed_by_us_5; allowed_by_us[6] = allowed_by_us_6; allowed_by_us[7] = allowed_by_us_7; allowed_by_us[8] = allowed_by_us_8; allowed_by_us[9] = allowed_by_us_9; allowed_by_us[10] = allowed_by_us_10; allowed_by_us[11] = allowed_by_us_11; allowed_by_us[12] = allowed_by_us_12; allowed_by_us[13] = allowed_by_us_13; } filter_for_length_15 static void filter_for_length_15(placement_t *p, letter_mask_t *letters_allowed, letter_mask_t *allowed_by_us) { move_t *m, *last; const letter_mask_t global_mask_0 = letters_allowed[p->where[0]]; letter_mask_t allowed_by_us_0 = 0; const letter_mask_t global_mask_1 = letters_allowed[p->where[1]]; letter_mask_t allowed_by_us_1 = 0; const letter_mask_t global_mask_2 = letters_allowed[p->where[2]]; letter_mask_t allowed_by_us_2 = 0; const letter_mask_t global_mask_3 = letters_allowed[p->where[3]]; letter_mask_t allowed_by_us_3 = 0; const letter_mask_t global_mask_4 = letters_allowed[p->where[4]]; letter_mask_t allowed_by_us_4 = 0; const letter_mask_t global_mask_5 = letters_allowed[p->where[5]]; letter_mask_t allowed_by_us_5 = 0; const letter_mask_t global_mask_6 = letters_allowed[p->where[6]]; letter_mask_t allowed_by_us_6 = 0; const letter_mask_t global_mask_7 = letters_allowed[p->where[7]]; letter_mask_t allowed_by_us_7 = 0; const letter_mask_t global_mask_8 = letters_allowed[p->where[8]]; letter_mask_t allowed_by_us_8 = 0; const letter_mask_t global_mask_9 = letters_allowed[p->where[9]]; letter_mask_t allowed_by_us_9 = 0; const letter_mask_t global_mask_10 = letters_allowed[p->where[10]]; letter_mask_t allowed_by_us_10 = 0; const letter_mask_t global_mask_11 = letters_allowed[p->where[11]]; letter_mask_t allowed_by_us_11 = 0; const letter_mask_t global_mask_12 = letters_allowed[p->where[12]]; letter_mask_t allowed_by_us_12 = 0; const letter_mask_t global_mask_13 = letters_allowed[p->where[13]]; letter_mask_t allowed_by_us_13 = 0; const letter_mask_t global_mask_14 = letters_allowed[p->where[14]]; letter_mask_t allowed_by_us_14 = 0; last = (move_t *) ((char *) p->move + (p->num_moves - 1) * MOVE_SIZE(15)); for (m = p->move; m->original_word != NULL; ) { if ( !(global_mask_0 & (1 << m->letter[0])) || !(global_mask_1 & (1 << m->letter[1])) || !(global_mask_2 & (1 << m->letter[2])) || !(global_mask_3 & (1 << m->letter[3])) || !(global_mask_4 & (1 << m->letter[4])) || !(global_mask_5 & (1 << m->letter[5])) || !(global_mask_6 & (1 << m->letter[6])) || !(global_mask_7 & (1 << m->letter[7])) || !(global_mask_8 & (1 << m->letter[8])) || !(global_mask_9 & (1 << m->letter[9])) || !(global_mask_10 & (1 << m->letter[10])) || !(global_mask_11 & (1 << m->letter[11])) || !(global_mask_12 & (1 << m->letter[12])) || !(global_mask_13 & (1 << m->letter[13])) || !(global_mask_14 & (1 << m->letter[14]))) { void *copy0 = ((void **)last)[0]; void *copy1 = ((void **)last)[1]; void *copy2 = ((void **)last)[2]; void *copy3 = ((void **)last)[3]; void *copy4 = ((void **)last)[4]; ((void **)m)[0] = copy0; ((void **)m)[1] = copy1; ((void **)m)[2] = copy2; ((void **)m)[3] = copy3; ((void **)m)[4] = copy4; last->original_word = NULL; --p->num_moves; last = NEXT_MOVE(last, -MOVE_SIZE(15)); } else { allowed_by_us_0 |= 1 << m->letter[0]; allowed_by_us_1 |= 1 << m->letter[1]; allowed_by_us_2 |= 1 << m->letter[2]; allowed_by_us_3 |= 1 << m->letter[3]; allowed_by_us_4 |= 1 << m->letter[4]; allowed_by_us_5 |= 1 << m->letter[5]; allowed_by_us_6 |= 1 << m->letter[6]; allowed_by_us_7 |= 1 << m->letter[7]; allowed_by_us_8 |= 1 << m->letter[8]; allowed_by_us_9 |= 1 << m->letter[9]; allowed_by_us_10 |= 1 << m->letter[10]; allowed_by_us_11 |= 1 << m->letter[11]; allowed_by_us_12 |= 1 << m->letter[12]; allowed_by_us_13 |= 1 << m->letter[13]; allowed_by_us_14 |= 1 << m->letter[14]; m = NEXT_MOVE(m, MOVE_SIZE(15)); } } allowed_by_us[0] = allowed_by_us_0; allowed_by_us[1] = allowed_by_us_1; allowed_by_us[2] = allowed_by_us_2; allowed_by_us[3] = allowed_by_us_3; allowed_by_us[4] = allowed_by_us_4; allowed_by_us[5] = allowed_by_us_5; allowed_by_us[6] = allowed_by_us_6; allowed_by_us[7] = allowed_by_us_7; allowed_by_us[8] = allowed_by_us_8; allowed_by_us[9] = allowed_by_us_9; allowed_by_us[10] = allowed_by_us_10; allowed_by_us[11] = allowed_by_us_11; allowed_by_us[12] = allowed_by_us_12; allowed_by_us[13] = allowed_by_us_13; allowed_by_us[14] = allowed_by_us_14; } typedef filter_func_t typedef void (*filter_func_t)(placement_t *, letter_mask_t *, letter_mask_t *); static const filter_func_t filter_func[16] = { 0, filter_for_length_1, filter_for_length_2, filter_for_length_3, filter_for_length_4, filter_for_length_5, filter_for_length_6, filter_for_length_7, filter_for_length_8, filter_for_length_9, filter_for_length_10, filter_for_length_11, filter_for_length_12, filter_for_length_13, filter_for_length_14, filter_for_length_15, }; /* Assorted constants, in an enum so debugger knows about them. */ enum { /* Bit mask indicating all letters. */ ALL_LETTERS = (1 << 26) - 1, /* Bit mask indicating "this square is not an intersection point * so ignore it". */ NOT_INTERSECTION_POINT = 0x7FFFFFFF, /* Empty square in the puzzle. */ EMPTY_SQUARE = 0 }; static unsigned long current_mark = 1; #define set_placement_mark(p) ((p)->mark = current_mark) #define clear_placement_mark(p) ((p)->mark = current_mark - 1) #define placement_is_marked(p) ((p)->mark == current_mark) #define clear_all_placement_marks() (++current_mark) count_num_placements /* Returns the total number of placements in the puzzle. */ static long count_num_placements(Puzzle puzzle, long puzzle_size) { long x, y, num_placements = 0; /* Horizontal placements. */ for (y = 0; y < puzzle_size; y++) for (x = 0; x < puzzle_size - 1; x++) if (puzzle[x][y] == EMPTY_SQUARE && puzzle[x + 1][y] == EMPTY_SQUARE) { ++num_placements; for (x++; x < puzzle_size && puzzle[x][y] == EMPTY_SQUARE; x++) ; } /* Vertical placements. */ for (x = 0; x < puzzle_size; x++) for (y = 0; y < puzzle_size - 1; y++) if (puzzle[x][y] == EMPTY_SQUARE && puzzle[x][y + 1] == EMPTY_SQUARE) { ++num_placements; for (y++; y < puzzle_size && puzzle[x][y] == EMPTY_SQUARE; y++) ; } return num_placements; } identify_placements static placement_t * identify_placements(Puzzle puzzle, long puzzle_size, long *num_placements_ptr, placement_t *square_to_placement[kMaxSize][kMaxSize][2], char interesting_length[kMaxSize + 1]) { /* Create an empty map from squares to the placements that intersect. */ long x, y, num_placements; placement_t *p, *placement; num_placements = count_num_placements(puzzle, puzzle_size); p = placement = (placement_t *) calloc(num_placements, sizeof p[0]); /* Find all horizontal placements. */ for (y = 0; y < puzzle_size; y++) for (x = 0; x < puzzle_size - 1; x++) if (puzzle[x][y] == EMPTY_SQUARE && puzzle[x + 1][y] == EMPTY_SQUARE) { const long start_x = x; p->start_x = x; p->start_y = y; p->dx = 1; p->dy = 0; for (; x < puzzle_size && puzzle[x][y] == EMPTY_SQUARE; x++) square_to_placement[x][y][0] = p; ++p; interesting_length[x - start_x] = 1; } /* Find all vertical placements. */ for (x = 0; x < puzzle_size; x++) for (y = 0; y < puzzle_size - 1; y++) if (puzzle[x][y] == EMPTY_SQUARE && puzzle[x][y + 1] == EMPTY_SQUARE) { const long start_y = y; p->start_x = x; p->start_y = y; p->dx = 0; p->dy = 1; for (; y < puzzle_size && puzzle[x][y] == EMPTY_SQUARE; y++) square_to_placement[x][y][1] = p; ++p; interesting_length[y - start_y] = 1; } /* assert(p == &placement[num_placements]); */ *num_placements_ptr = num_placements; return placement; } intersect_placement_with_global_mask /* Takes the list of moves allowed by a placement and uses that set * to tighten what's globally allowed for the squares it intersects. * "Marks" any placements whose word lists are changed as a result. */ static void intersect_placement_with_global_mask(const placement_t *p, letter_mask_t *global_mask) { const unsigned long move_size = p->move_size; int i; for (i = p->letters_per_move - 1; i >= 0; i--) { move_t *m; letter_mask_t mask = 0, g; /* Figure out the union of all letters valid for each square. */ for (m = p->move; m->original_word != NULL; m = NEXT_MOVE(m, move_size)) mask |= 1 << m->letter[i]; g = global_mask[p->where[i]]; if ((g & mask) != g) { /* Mark this neighbor as being in need of further refinement, * since we have just disallowed some of his moves. */ set_placement_mark(p->neighbor[i]); /* Note the new, tighter restriction on this square. */ global_mask[p->where[i]] = g & mask; } } } create_ascii_to_letter /* Creates an array mapping ASCII letter values to numbers 0-25. */ static void create_ascii_to_letter(unsigned char ascii_to_letter[256]) { int let; memset(ascii_to_letter, 0, 256); for (let = 0; let < 26; let++) ascii_to_letter['a' + let] = ascii_to_letter['A' + let] = let; } partition_words_by_length static void partition_words_by_length(char *dictionary[], long dict_size, const char interesting_length[kMaxSize + 1], const char **words_of_length[kMaxSize + 1], long num_words_of_length[kMaxSize + 1], void **mem_to_free_on_cleanup) { long num_words_left[kMaxSize + 1], num_useful_words, i, j, w, k; const char **r; void *raw_words_mem; /* Figure out how many words there are of each length. */ for (i = 0; i <= kMaxSize; i++) num_words_of_length[i] = 0; num_useful_words = 0; for (w = 0; w < dict_size; w++) { size_t len = strlen(dictionary[w]); if (len <= kMaxSize && interesting_length[len]) { ++num_words_of_length[len]; ++num_useful_words; } } /* Allocate room for a pointer vector for each word length. * We'll just put all of the pointer vectors together into * one big block of memory, separated by a NULL pointer. */ raw_words_mem = malloc((num_useful_words + kMaxSize + 1) * sizeof r[0]); r = (const char **) raw_words_mem; for (k = 0; k <= kMaxSize; k++) { const long num_words_of_this_length = num_words_of_length[k]; words_of_length[k] = r; r[num_words_of_this_length] = NULL; r += num_words_of_this_length + 1; /* leave room for terminating NULL */ } /* Note the words of each length. */ memcpy(num_words_left, num_words_of_length, sizeof num_words_left); for (j = 0; j < dict_size; j++) { size_t len = strlen(dictionary[j]); if (len <= kMaxSize && interesting_length[len]) words_of_length[len][--num_words_left[len]] = dictionary[j]; } /* Report the block of memory to free when done. */ *mem_to_free_on_cleanup = raw_words_mem; } tighten_constraints static int tighten_constraints(placement_t *placement, long num_placements, letter_mask_t *letters_allowed, int do_acyclic) { placement_t **orig_stack, **stack, *p; long n; stack = orig_stack = malloc((num_placements + 1) * sizeof orig_stack[0]); *stack++ = NULL; /* On entry, we've marked every placement that needs to be explored * further, so push those on the stack. */ for (n = num_placements - 1; n >= 0; n--) { placement_t *t = &placement[n]; if (placement_is_marked(t)) *stack++ = t; } while ((p = *--stack) != NULL) { letter_mask_t allowed_by_us[kMaxSize]; long i; if (p->done || (!do_acyclic && p->in_cycle == NOT_IN_CYCLE)) continue; if (p->letters_per_move < sizeof filter_func / sizeof filter_func[0]) (*filter_func[p->letters_per_move])(p, letters_allowed, allowed_by_us); else { letter_mask_t global_mask[kMaxSize]; long i, move_size; move_t *m, *last; move_size = p->move_size; memset(allowed_by_us, 0, sizeof allowed_by_us); /* For speed, stash globally allowed letters in linear array. */ for (i = 0; i < p->letters_per_move; i++) global_mask[i] = letters_allowed[p->where[i]]; /* Loop through all words here, discarding illegal words and * accruing a new union mask. */ last = (move_t *) ((char *) p->move + (p->num_moves - 1) * p->move_size); for (m = p->move; m->original_word != NULL; ) { long j; /* See if word is legal. */ for (j = p->letters_per_move - 1; j >= 0; j--) if (!(global_mask[j] & (1 << m->letter[j]))) break; if (j < 0) { /* It's legal. Note the possible letters and move on. */ long k; for (k = p->letters_per_move - 1; k >= 0; k--) allowed_by_us[k] |= 1 << m->letter[k]; m = NEXT_MOVE(m, move_size); } else { /* It's illegal. Delete this move by replacing it with * the last move in the list. Profiling shows this is * a hotspot, so inline a memcpy using our knowledge * about what moves look like. */ char *from, *to; long ctr; from = (char *) last; to = (char *) m; for (ctr = move_size; (ctr -= sizeof(void *)) >= 0; ) *(void **)(to + ctr) = *(void **)(from + ctr); last->original_word = NULL; --p->num_moves; last = NEXT_MOVE(last, -move_size); } } } if (p->num_moves == 0) { /* No moves --> no solution. Quit now! */ free(orig_stack); return 0; } /* Propagate our constraints to the global grid. If we actually * change anything, note that we need to recompute the valid * words list for whomever intersects the newly tightened square. */ for (i = p->letters_per_move - 1; i >= 0; i--) { letter_mask_t g = letters_allowed[p->where[i]]; if ((g & allowed_by_us[i]) != g) { placement_t *nbr; letters_allowed[p->where[i]] = g & allowed_by_us[i]; nbr = p->neighbor[i]; if (!placement_is_marked(nbr)) { *stack++ = nbr; set_placement_mark(nbr); } } } clear_placement_mark(p); } free(orig_stack); return 1; } place_word static void place_word(Puzzle puzzle, int x, int y, int dx, int dy, const char *word) { for (; *word; word++) { puzzle[x][y] = *word; x += dx; y += dy; } } place_move static void place_move(Puzzle puzzle, placement_t *p, move_t *m) { place_word(puzzle, p->start_x, p->start_y, p->dx, p->dy, m->original_word); } solve_trivial_placements /* Go ahead and fill in every placement where there's only one choice. */ static void solve_trivial_placements(Puzzle puzzle, placement_t *placement, long num_placements) { long i; /* Go ahead and make any move where there's only one choice. */ for (i = 0; i < num_placements; i++) { placement_t *p = &placement[i]; if (p->num_moves == 1) { place_move(puzzle, p, &p->move[0]); free(placement[i].move); placement[i].move = NULL; p->num_moves = 0; p->done = 1; } } } create_placements static placement_t * create_placements(Puzzle puzzle, long puzzle_size, char *dictionary[], long dict_size, letter_mask_t letters_allowed[kMaxSize * kMaxSize], long *letters_allowed_size_ptr, long *num_placements_ptr) { /* Do we care about words of length n? */ char interesting_length[kMaxSize + 1]; long n, num_placements; placement_t *placement; const char **words_of_length[kMaxSize + 1]; long num_words_of_length[kMaxSize + 1]; move_t **hash_table = NULL; unsigned long max_hash_table_size = 0; void *mem_to_free; /* Maps [A-Za-z] to the numbers 1-26, zero for all others. */ unsigned char ascii_to_letter[256]; /* Maps intersection squares to unique contiguous numbers. * Undefined garbage for non-intersection squares. */ unsigned long square_to_packed_linear[kMaxSize][kMaxSize]; unsigned long num_packed_linears = 0; /* Gives us the up to two placements that intersect the given square. */ placement_t *square_to_placement[kMaxSize][kMaxSize][2]; /* Initialize assorted arrays. */ memset(square_to_placement, 0, sizeof square_to_placement); memset(interesting_length, 0, sizeof interesting_length); create_ascii_to_letter(ascii_to_letter); /* Create all of the placement structs, etc. */ placement = identify_placements(puzzle, puzzle_size, &num_placements, square_to_placement, interesting_length); /* Figure out all of the words of the various lengths we want. */ partition_words_by_length(dictionary, dict_size, interesting_length, words_of_length, num_words_of_length, &mem_to_free); /* Loop through each partition and set up its neighbors and move list, * and reflect our move list on the global state. */ for (n = 0; n < num_placements; n++) { placement_t *t = &placement[n]; long num_intersect_squares = 0; long x, y, dx, dy, length; letter_mask_t mask[kMaxSize]; /* If anyone marked us as needing further refinement, clear it * since we're going to do that refinement now. */ clear_placement_mark(t); dx = t->dx; dy = t->dy; for (x = t->start_x, y = t->start_y, length = 0; x < puzzle_size && y < puzzle_size && puzzle[x][y] == EMPTY_SQUARE; x += dx, y += dy, length++) { placement_t *p0 = square_to_placement[x][y][0]; placement_t *nbr; /* default to all letters being allowed for this square. */ mask[length] = NOT_INTERSECTION_POINT; if (p0 != NULL && p0 != t) nbr = p0; else { placement_t *p1 = square_to_placement[x][y][1]; if (p1 != NULL && p1 != t) nbr = p1; else nbr = NULL; } if (nbr != NULL) { /* If we are the first partition to visit this intersect * point (i.e. this neighbor hasn't been processed) then * add this square to the global list of interesting * squares. */ if (nbr->letters_per_move != 0) mask[length] = letters_allowed [square_to_packed_linear[x][y]]; else { mask[length] = ALL_LETTERS; letters_allowed[num_packed_linears] = ALL_LETTERS; square_to_packed_linear[x][y] = num_packed_linears++; } /* We intersected some other placement here. This means we * care about this square. */ t->neighbor[num_intersect_squares] = nbr; t->where[num_intersect_squares] = square_to_packed_linear[x][y]; num_intersect_squares++; } } t->letters_per_move = num_intersect_squares; t->move_size = MOVE_SIZE(num_intersect_squares); if (t->letters_per_move == 0) { /* Plug in anything that fits. */ if (num_words_of_length[length] == 0) { /* No solution! */ goto done; } place_word(puzzle, t->start_x, t->start_y, t->dx, t->dy, words_of_length[length][0]); t->done = 1; t->num_moves = 0; t->move = NULL; continue; } /* Create all the moves for this placement. */ t->move = (move_t *) malloc((num_words_of_length[length]+1) * MOVE_SIZE(length)); { const char **w; move_t *m = t->move; unsigned long hash_table_size; hash_table_size = num_words_of_length[length] * 3 + 16; if (hash_table_size > max_hash_table_size) { free(hash_table); max_hash_table_size = hash_table_size; hash_table = calloc(max_hash_table_size, sizeof hash_table[0]); } else memset(hash_table, 0, hash_table_size * sizeof hash_table[0]); for (w = words_of_length[length]; *w; w++) { const char *s = *w; unsigned long hash; long ix, out; hash = 1; for (ix = out = 0; s[ix] != '\0'; ix++) if (mask[ix] != NOT_INTERSECTION_POINT) { int letter = ascii_to_letter[(unsigned char) s[ix]]; if ((mask[ix] & (1 << letter)) == 0) break; hash = (hash * 26) + letter; m->letter[out++] = letter; } /* If we made it all the way to the end without failing, * then add this word to the list. */ if (s[ix] == '\0') { const move_t *test_move; long j; hash %= hash_table_size; while ((test_move = hash_table[hash]) != NULL) { for (j = t->letters_per_move - 1; j>=0; j--) if (test_move->letter[j] != m->letter[j]) break; if (j < 0) break; if (++hash >= hash_table_size) hash -= hash_table_size; } if (test_move == NULL) { hash_table[hash] = m; m->original_word = *w; ++t->num_moves; m = NEXT_MOVE(m, t->move_size); } } } /* Terminate our list with a NULL pointer. */ m->original_word = NULL; } /* Compute global implications of the legal words here. */ intersect_placement_with_global_mask(t, letters_allowed); } solve_trivial_placements(puzzle, placement, num_placements); done: /* We don't need this memory any more, so free it. */ free(hash_table); free(mem_to_free); /* Recursively propagate around constraints. */ tighten_constraints(placement, num_placements, letters_allowed, 1); *letters_allowed_size_ptr = num_packed_linears; *num_placements_ptr = num_placements; return placement; } partition_aux /* Recursive helper function for `partition_and_mark_cycles'. */ static long partition_aux(placement_t *p, placement_t ***partition, placement_t *parent, long depth) { placement_t **nbrs, *nbr; long retval = depth; /* Add this placement to our partition. */ set_placement_mark(p); p->depth = depth; p->in_cycle = NOT_IN_CYCLE; if (!p->done) { **partition = p; ++*partition; for (nbrs = p->neighbor; (nbr = *nbrs) != NULL; nbrs++) { long x; if (nbr == parent) continue; if (placement_is_marked(nbr)) x = nbr->depth; else x = partition_aux(nbr, partition, p, depth + 1); if (x <= retval) { p->in_cycle = IN_CYCLE; retval = x; } } } return (p->in_cycle == IN_CYCLE) ? retval : 10000000; } partition_and_mark_cycles /* Store all non-solved placements reachable from root that are part of * some cycle into partition. */ static long partition_and_mark_cycles(placement_t *root, placement_t **partition) { placement_t **end_partition, **in, **out, *p; /* Put everything in the partition into the array, and mark each * that's part of a cycle. */ end_partition = partition; clear_all_placement_marks(); partition_aux(root, &end_partition, NULL, 1); *end_partition = NULL; /* Remove everything that's not part of a cycle. */ for (in = out = partition; (p = *in) != 0; in++) if (p->in_cycle == IN_CYCLE) *out++ = p; *out = NULL; return out - partition; } solve_partition /* Tries to solve a partition. Returns true on success. */ static int solve_partition(Puzzle puzzle, placement_t **partition, long partition_size, letter_mask_t *letters_allowed, long letters_allowed_size, placement_t *all_placements, long all_placements_size, placement_t *start) { placement_t *p, *most_popular; move_t **backup_move, *m; long *backup_num_moves, i; letter_mask_t *backup_letters_allowed; placement_t **new_partition; int success = 0; long bla_size; long move_size; /* Make a backup copy of our letters_allowed array. */ bla_size = letters_allowed_size * sizeof backup_letters_allowed[0]; backup_letters_allowed = malloc(bla_size); memcpy(backup_letters_allowed, letters_allowed, bla_size); /* Make backup copies of our move lists. */ backup_move = malloc(partition_size * sizeof backup_move[0]); backup_num_moves = malloc(partition_size * sizeof backup_num_moves[0]); /* Allocate room to hold this. */ new_partition = malloc((all_placements_size + 1) * sizeof new_partition[0]); p = most_popular = NULL; for (i = 0; i < partition_size; i++) { placement_t *q = partition[i]; long size; backup_num_moves[i] = q->num_moves; size = (q->num_moves + 1) * q->move_size; backup_move[i] = malloc(size); memcpy(backup_move[i], q->move, size); if (q == start) p = q; else if (most_popular == NULL || q->letters_per_move > most_popular->letters_per_move) most_popular = q; } if (p == NULL) p = most_popular; /* Hypothetically lay down this move. */ move_size = p->move_size; for (m = p->move; m->original_word; m = NEXT_MOVE(m, move_size)) { long r; /* Actually lay this move down on the board. */ place_move(puzzle, p, m); /* Remember that this placement is "done". */ p->done = 1; /* Tighten grid and update all neighbors who may care. */ clear_all_placement_marks(); for (r = p->letters_per_move - 1; r >= 0; r--) { letter_mask_t g = letters_allowed[p->where[r]]; letter_mask_t mask = 1 << m->letter[r]; if (g != mask) { letters_allowed[p->where[r]] = mask; set_placement_mark(p->neighbor[r]); } } /* Propagate constraints and check for contradiction. */ if (!tighten_constraints(all_placements, all_placements_size, letters_allowed, 0)) goto failed; { placement_t **nbrs, *nbr; /* No contradiction yet, so try our children. */ for (nbrs = p->neighbor; (nbr = *nbrs) != 0; nbrs++) { long new_partition_size; new_partition_size = partition_and_mark_cycles(nbr, new_partition); if (new_partition_size > 0 && !solve_partition(puzzle, new_partition, new_partition_size, letters_allowed, letters_allowed_size, all_placements, all_placements_size, nbr)) goto failed; } } /* Woohoo! We did it! */ success = 1; break; /* This didn't work, so restore state. */ failed: p->done = 0; for (r = 0; r < partition_size; r++) { placement_t *q = partition[r]; q->num_moves = backup_num_moves[r]; /* FIXME - don't actually need to copy on the last pass... * just assign pointer to backup memory and free the bad copy. */ memcpy(q->move, backup_move[r], (q->num_moves + 1) * q->move_size); } memcpy(letters_allowed, backup_letters_allowed, letters_allowed_size * sizeof letters_allowed[0]); } /* Housecleaning. */ free(new_partition); free(backup_letters_allowed); for (i = 0; i < partition_size; i++) free(backup_move[i]); free(backup_num_moves); free(backup_move); return success; } solve_acyclic_aux static void solve_acyclic_aux(Puzzle puzzle, placement_t *p, letter_mask_t *letters_allowed) { /* Find any legal move and make it. */ move_t *m; long move_size, loop_start; if (p->done) return; move_size = p->move_size; loop_start = p->letters_per_move - 1; for (m = p->move; m->original_word; m = NEXT_MOVE(m, move_size)) { long k; for (k = loop_start; k >= 0; k--) if (!(letters_allowed[p->where[k]] & (1 << m->letter[k]))) break; if (k < 0) { long j; /* Make the move. */ place_move(puzzle, p, m); /* Tighten up the board for everyone else. */ for (j = loop_start; j >= 0; j--) letters_allowed[p->where[j]] = 1 << m->letter[j]; p->done = 1; /* Flood out to our neighbors and do them too. */ for (j = loop_start; j >= 0; j--) solve_acyclic_aux(puzzle, p->neighbor[j], letters_allowed); /* Stop looking for a word. */ break; } } } solve_acyclic_stragglers /* The main algorithm guarantees we solve things that are part of * cycles but not those things which are not part of cycles, because * they are utterly trivial given the information we've computed. * This solves those last acyclic pieces. */ static void solve_acyclic_stragglers(Puzzle puzzle, placement_t *placement, long num_placements, letter_mask_t *letters_allowed) { long i; for (i = 0; i < num_placements; i++) { placement_t *p = &placement[i]; if (!p->done && p->num_moves > 0) solve_acyclic_aux(puzzle, p, letters_allowed); } } Crossword void Crossword( Puzzle thePuzzle, /* return solved puzzle here */ char *dictionary[], /* array of words to choose from */ long puzzleSize, /* number of rows/cols in puzzle */ long dictSize /* number of words in dictionary */ ) { letter_mask_t letters_allowed[kMaxSize * kMaxSize]; long num_placements, i, letters_allowed_size; placement_t *placement, **partition; int success = 1; /* Create our placement structures. */ placement = create_placements(thePuzzle, puzzleSize, dictionary, dictSize, letters_allowed, &letters_allowed_size, &num_placements); /* Find disjoint portions of the graph and solve them. */ partition = malloc((num_placements + 1) * sizeof partition[0]); for (i = 0; i < num_placements; i++) { placement_t *p = &placement[i]; if (p->num_moves > 0 && p->in_cycle == CYCLENESS_UNKNOWN) { long partition_size = partition_and_mark_cycles(p, partition); if (partition_size > 0) success &= solve_partition(thePuzzle, partition, partition_size, letters_allowed, letters_allowed_size, placement, num_placements, NULL); } } if (success) { /* Recompute all constraints for everyone not yet solved. */ for (i = 0; i < num_placements; i++) set_placement_mark(&placement[i]); tighten_constraints(placement, num_placements, letters_allowed, 1); /* Go through and solve them. */ solve_acyclic_stragglers(thePuzzle, placement, num_placements, letters_allowed); } /* House cleaning. */ free(partition); for (i = 0; i < num_placements; i++) free(placement[i].move); free(placement); }