Last week we had to prepare a crossword for a custom crossword for a special occasion, and so I took upon the challenge of writing my own crossword generator (crossword compiler, as they seem to be called on the internet). Generating a crossword is clearly a constraint satisfaction problem, so I thought that using Answer Set Programming for this would be a good fit. Here is what I came up with:

size(10, 10).

row(0..X-1) :- size(X,Y).
col(0..Y-1) :- size(X,Y).

word("hello"; "world").


letter(W, @letter(W)) :- word(W).

fits(W,h,X,Y) :- word(W), col(X), row(Y), col(X+@length(W)-1).
fits(W,v,X,Y) :- word(W), col(X), row(Y), row(Y+@length(W)-1).

{pos(W,O,X,Y) : fits(W,O,X,Y)} = 1 :- word(W).

lpos(C,X+I,Y) :- pos(W,h,X,Y), letter(W,(I,C)).
lpos(C,X,Y+I) :- pos(W,v,X,Y), letter(W,(I,C)).

:- pos(W,v,X,Y), lpos(C,X,Y-1).
:- pos(W,v,X,Y), lpos(C,X,Y+@length(W)).
:- pos(W,h,X,Y), lpos(C,X-1,Y).
:- pos(W,h,X,Y), lpos(C,X+@length(W),Y).

:- pos(A,h,X1,Y1), {pos(B,v,X2,Y2) : 
    		      X1<=X2, X2<X1+@length(A),
    		      Y2<=Y1, Y1<Y2+@length(B)} < 1.
:- pos(B,v,X2,Y2), {pos(A,h,X1,Y1) : 
    		      X1<=X2, X2<X1+@length(A),
    		      Y2<=Y1, Y1<Y2+@length(B)} < 1.

#minimize {C,X,Y:lpos(C, X, Y)}.

#show lpos/3.
#show size/2.

I have here the following predicates, that can be customized at will:

  1. size(X,Y) describes the maximum size of the board;
  2. word(W) defines the words to be put in the crossword; note that the ASP syntax allows you to define multiple words on the same predicate using the semicolon ; as connective;
  3. row(Y) and col(X) are defined in the range of size(X,Y) and describe valid row and column positions;
  4. if a word \(W\) fits at a specific starting point \((X, Y)\) with orientation \(O \in \{v,h\}\) then fits(W,O,X,Y) is generated;
  5. finally, a word can take at most one position pos from the fits predicate and the i-th letter of a word is given its position with the predicate lpos, and must satisfy all the constraints described:
    • there must be no letter before the beginning and after the end of a word, hence they must be empty spaces;
    • each word must cross another word at least once: note that this does not required that clusters of words be connected, but connected crosswords can be easily generated setting a small enough board for the number of words given to the solver.

This ASP program relies on two Python functions:

def letter(word):
  i = 0
  l = []
  for c in word:
    l.append((i, c))
    i += 1
  return l

def length(w):
  return len(w)

And finally I use the following Python code to produce the output, interpreting the pos and size predicates:

import os, re

tmp = os.popen("clingo cw.lp").read()

x = re.findall("Answer: 1\n(.*)\nSATISFIABLE", tmp, flags=re.M)[0]

board = []
char = "#"

def size(x, y):
    for i in range(0, y):
        board.append([char for j in range(0, x)])

def lpos(c, x, y):
    if board[x][y] == char:
        board[x][y] = c
        print "replacing existing character!"

for s in x.split(" "):

out = "\n".join([",".join(row).upper() for row in board])

print out
open("cw.csv", 'w').write(out)

Note that it only works when clingo is installed, the ASP program is satisfiable, and the ASP file is called cw.lp.