Skip to content
Advertisement

Knight’s tour backtracking

I am working on knight’s tour problem, and using backtracking algorithm. My code doesn’t produce the right output in the end it just repeats the last two entries over and over until n^2 -1 is not reached.

This is my code. I am following this pseudocode http://www.wou.edu/~broegb/Cs345/KnightTour.pdf

visited = [[False for x in range(5)] for y in range(5)]

def move(x,y,m):

    result=False
    if x<0 or x>=5 or y<0 or y>=5:
        return False
    if visited[x][y]==True:
        return False
    if m==24:
        print "a solution has been found"
        print x,",",y


        visited[x][y]=True
        return True

    else:
        result=result or move(x+2,y+1,m+1)
        result=result or  move(x+2,y-1,m+1)
        result=result or move(x-2,y+1,m+1)
        result=result or move(x-2,y-1,m+1)
        result=result or move(x+1,y+1,m+1)
        result=result or move(x+1,y-1,m+1)
        result=result or move(x-1,y+1,m+1)
        result=result or move(x-1,y-1,m+1)
    if result==True:
        print x,",",y

        return True
    else:
        visited[x][y]=False
        return False

Advertisement

Answer

You are settings visited[x][y]=True to true at the end of your algorithm. It has to be set after you check you’ve bin there. I also made a couple of enhancements for your code:

N = 5 # This way you can test it with 5 or 6 and even 100 if you want to.
visited = [[False for x in range(N)] for y in range(N)]

def move(x,y,m):

    result=False
    if x<0 or x>=N or y<0 or y>=N or visited[x][y]==True: # You may merge these two ifs.
        return False
    visited[x][y]=True
    if m==(N * N - 1):
        print "a solution has been found"
        visited[x][y]=True # Set visited here tot true.
        return True
    else:
        print x,",",y
        if (move(x+2,y+1,m+1) or move(x+2,y-1,m+1)
            or move(x-2,y+1,m+1) or move(x-2,y-1,m+1)
            or move(x+1,y+1,m+1) or move(x+1,y-1,m+1)
            or move(x-1,y+1,m+1) or move(x-1,y-1,m+1)): # Place them in one if.
            print x,",",y

            return True
    return False # If the algorithm comes here it may return false

print move(2,1,0)
Advertisement