I want to generate all unique crossword puzzle grids of a certain grid size (4x4 is a good size). All possible puzzles, including non-unique puzzles, are represented by a binary string with the length of the grid area (16 in the case of 4x4), so all possible 4x4 puzzles are represented by the binary forms of all numbers in the range 0 to 2^16.
Generating these is easy, but I'm curious if anyone has a good solution for how to programmatically eliminate invalid and duplicate cases. For example, all puzzles with a single column or single row are functionally identical, hence eliminating 7 of those 8 cases. Also, according to crossword puzzle conventions, all squares must be contiguous. I've had success removing all duplicate structures, but my solution took several minutes to execute and probably was not ideal. I'm at something of a loss for how to detect contiguity so if anyone has ideas on this it'd be much appreciated.
I'd prefer solutions in python but write in whichever language you prefer. If anyone wants, I can post my python code for generating all grids and removing duplicates, slow as it may be.
Disclaimer: mostly untested other than all tests do have an impact by filtering out some grids and a few spotted errors were fixed. Can certainly be optimized.
def is_valid_grid (n):
row_mask = ((1 << n) - 1)
top_row = row_mask << n * (n - 1)
left_column = 0
right_column = 0
for row in range (n):
left_column |= (1 << (n - 1)) << row * n
right_column |= 1 << row * n
def neighborhood (grid):
return (((grid & ~left_column) << 1)
| ((grid & ~right_column) >> 1)
| ((grid & ~top_row) << n)
| (grid >> n))
def is_contiguous (grid):
# Start with a single bit and expand with neighbors as long as
# possible. If we arrive at the starting grid then it is
# contiguous, else not.
part = (grid ^ (grid & (grid - 1)))
while True:
expanded = (part | (neighborhood (part) & grid))
if expanded != part:
part = expanded
else:
break
return part == grid
def flip_y (grid):
rows = []
for k in range (n):
rows.append (grid & row_mask)
grid >>= n
for row in rows:
grid = (grid << n) | row
return grid
def rotate (grid):
rotated = 0
for x in range (n):
for y in range (n):
if grid & (1 << (n * y + x)):
rotated |= (1 << (n * x + (n - 1 - y)))
return rotated
def transform (grid):
yield flip_y (grid)
for k in range (3):
grid = rotate (grid)
yield grid
yield flip_y (grid)
def do_is_valid_grid (grid):
# Any square in the topmost row?
if not (grid & top_row):
return False
# Any square in the leftmost column?
if not (grid & left_column):
return False
# Is contiguous?
if not is_contiguous (grid):
return False
# Of all transformations, we pick only that which gives the
# smallest number.
for transformation in transform (grid):
# A transformation can produce a grid without a square in the topmost row and/or leftmost column.
while not (transformation & top_row):
transformation <<= n
while not (transformation & left_column):
transformation <<= 1
if transformation < grid:
return False
return True
return do_is_valid_grid
def valid_grids (n):
do_is_valid_grid = is_valid_grid (n)
for grid in range (2 ** (n * n)):
if do_is_valid_grid (grid):
yield grid
for grid in valid_grids (4):
print grid