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)