Word Square generation in Python

Am working on a few minor improvements, but I think the major saving to be had is in removing the line

square2, isquare2 = square[:], isquare[:]

Instead, do

sofar = square[x], isquare[y]
for o in options[sofar]:
    square[x], isquare[y] = o
    for s in addone(square, isquare, position+1):
        yield s
square[x], isquare[y] = sofar

import time
start = time.clock()

dim = 3 #the dimension of our square
posmax = dim**2 #maximum positions on a dim*dim square

Python convention is to have constants be in ALL_CAPS

words = open("word.list").read().splitlines()

Actually, a file iterates over its lines so you can do words = list(open("words.list"))

words = set([w for w in words if len(w)==dim])

I'd make it a generator rather then a list and combine the previous two lines

print 'Words: %s' % len(words)

It is generally preferred to do any actual logic inside a function. Its a bit faster and cleaner

prefs = {}
for w in words:

I'd suggest spelling out word

    for i in xrange(0,dim):
        prefs[w[:i]] = prefs.get(w[:i], set())
        prefs[w[:i]].add(w[i])

Actually, you can do prefs.setdefault(w[:i],set()).add(w[i]) for the same effect.

sq, options = ['' for i in xrange(dim)], {}

You can do sq, options = [''] * dim, {} for the same effect

for i in prefs: 
for j in prefs:
    options[(i,j)] = [(i+o, j+o) 
        for o in prefs[i] & prefs[j]]

schedule = [(p/dim, p%dim) for p in xrange(posmax)]

This can be written as schedule = map(divmod, xrange(posmax))

def addone(square, isquare, position=0):
#for r in square: print r #prints all square-states

Don't leave dead code as comments, kill it!

if position == posmax: yield square

I'd put the yield on the next line, I think its easier to read especially if you have an else condition

else:
    x,y = schedule[position]
    square2, isquare2 = square[:], isquare[:]

In the one line you don't have a space after the comma, in the next line you do. I suggest always including the space.

    for o in options[(square[x], isquare[y])]:
        square2[x], isquare2[y] = o
        for s in addone(square2, isquare2, position+1):
            yield s

print sum(1 for s in addone(sq, sq[:]))

print (time.clock() - start)

I tried a different schedule, it made a very small difference to the time though!

schedule = [(b-y,y)
    for b in range(DIM*2)
    for y in range(min(b+1, DIM))
    if b-y< DIM]

assert len(schedule) == POSMAX

We fill column by column with the current schedule. I tried adding a check whether we're going to be able to put anything in the next row before filling the rest of the column, but it results in a slight slowdown.

if x+1 < DIM and len(FOLLOWSBOTH[(square[x+1], transpose[y])]) == 0:
    continue

I am still tempted to think that something like this but more thorough could still save time: checking not just this one spot, but everything remaining in the row and the column, to ensure that there are compatible letters. That needs a new, more complex data structure though!