I took a stab at converting the recent psyco-optimized code to cython,

and got a speedup.

gcj 4.3.3 1.39s

gcc 4.3.3 1.55s

cython 11.2 1.91s

psyco 1.94s

javac 1.5.0_19 2.00s

python 2.5.4 168.37s

It was just a matter of cdef-ing all the arrays & integers --

bearophile already did the hard work :-)

Here's the cython code; all the others are from the repo.

#################################################

DEF NMOVES = 8

DEF SIDE = 5

DEF SQR_SIDE = SIDE * SIDE

cdef int circuit[SQR_SIDE]

cdef int nsolutions = 0

cdef int movex[NMOVES]

cdef int movey[NMOVES]

py_movex = [-1,-2,-2,-1,+1,+2,+2,+1]

py_movey = [-2,-1,+1,+2,+2,+1,-1,-2]

for i in range(NMOVES):

movex[i] = py_movex[i]

movey[i] = py_movey[i]

shift = [x * SIDE + y for x,y in zip(py_movex, py_movey)]

cdef int shift_0 = shift[0]

cdef int shift_1 = shift[1]

cdef int shift_2 = shift[2]

cdef int shift_3 = shift[3]

cdef int shift_4 = shift[4]

cdef int shift_5 = shift[5]

cdef int shift_6 = shift[6]

cdef int shift_7 = shift[7]

def showCircuit():

print

for x in xrange(SIDE):

x_SIDE = x * SIDE

for y in xrange(SIDE):

if SQR_SIDE < 100:

print "%02d " % circuit[x_SIDE + y],

else:

print "%03d " % circuit[x_SIDE + y],

print

cdef void solve(int nb, int x, int y,

int SIDE=SIDE, int SQR_SIDE=SQR_SIDE, int *circuit=circuit,

int shift_0=shift_0,

int shift_1=shift_1,

int shift_2=shift_2,

int shift_3=shift_3,

int shift_4=shift_4,

int shift_5=shift_5,

int shift_6=shift_6,

int shift_7=shift_7,

):

global nsolutions

cdef int newx, newy

cdef int pos = x * SIDE + y

circuit[pos] = nb

if nb == SQR_SIDE:

#showCircuit()

nsolutions += 1

circuit[pos] = 0

return

newx = x + -1

if newx >= 0 and newx < SIDE:

newy = y + -2

if newy >= 0 and newy < SIDE and not circuit[pos + shift_0]:

solve(nb+1, newx, newy)

newx = x + -2

if newx >= 0 and newx < SIDE:

newy = y + -1

if newy >= 0 and newy < SIDE and not circuit[pos + shift_1]:

solve(nb+1, newx, newy)

newx = x + -2

if newx >= 0 and newx < SIDE:

newy = y + 1

if newy >= 0 and newy < SIDE and not circuit[pos + shift_2]:

solve(nb+1, newx, newy)

newx = x + -1

if newx >= 0 and newx < SIDE:

newy = y + 2

if newy >= 0 and newy < SIDE and not circuit[pos + shift_3]:

solve(nb+1, newx, newy)

newx = x + 1

if newx >= 0 and newx < SIDE:

newy = y + 2

if newy >= 0 and newy < SIDE and not circuit[pos + shift_4]:

solve(nb+1, newx, newy)

newx = x + 2

if newx >= 0 and newx < SIDE:

newy = y + 1

if newy >= 0 and newy < SIDE and not circuit[pos + shift_5]:

solve(nb+1, newx, newy)

newx = x + 2

if newx >= 0 and newx < SIDE:

newy = y + -1

if newy >= 0 and newy < SIDE and not circuit[pos + shift_6]:

solve(nb+1, newx, newy)

newx = x + 1

if newx >= 0 and newx < SIDE:

newy = y + -2

if newy >= 0 and newy < SIDE and not circuit[pos + shift_7]:

solve(nb+1, newx, newy)

circuit[pos] = 0

def main():

print "Search for side=%d" % SIDE

cdef int x,y

for x in range(SIDE):

for y in range(SIDE):

solve(1, x, y);

print "\n%dx%d case, %d solutions." % (SIDE, SIDE, nsolutions)

def run():

import time

s=time.time()

main()

print time.time()-s

#################################################