[ create a new paste ] login | about

Link: http://codepad.org/gKFLu34M    [ raw code | fork ]

Python, pasted on Jul 21:
from array import array

SIDE = 5
SQR_SIDE = SIDE * SIDE

circuit = array("l", [0]) * SQR_SIDE
nsolutions = 0

movex = array("l", [-1,-2,-2,-1,+1,+2,+2,+1])
movey = array("l", [-2,-1,+1,+2,+2,+1,-1,-2])
shift = array("l", [x * SIDE + y for x,y in zip(movex, movey)])

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

def solve(nb, x, y, movex=movex, movey=movey, shift=shift):
    global nsolutions, SIDE, SQR_SIDE, circuit

    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
    for x in xrange(SIDE):
        for y in xrange(SIDE):
            solve(1, x, y);
    print "\n%dx%d case, %d solutions." % (SIDE, SIDE, nsolutions)

import psyco; psyco.full()
main()


Create a new paste based on this one


Comments: