>>377を、リスト内包のネストをループに戻してみた。
http://codepad.org/XwQJSHNw
これで 2.2sec で、 >>377 とほとんど変わらない。

で、これを次のように cython にかけてみると 0.4sec になった。
cython --embed queen.py
gcc `python-config --cflags` `python-config --ldflags` queen.c
./a.out