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
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)