1

My knight's tour code taking a long time to generate the output but it seems to be working fine until it reaches 61st step. What problem is making this code slower and inefficient? This code is working fine for 5*5,6*6 but it's getting slower when I try this code with 7*7 or beyond. What improvements need to be done to make it as quick as possible without waiting a long time for 8*8 output?

def isSafe(x,y,array):
    return x>=0 and x<8 and y>=0 and y<8 and array[x][y]==-1

def knightsTour(x,y,moveI,x_move,y_move,solution):
    if moveI==65:        
        return True
    #try out all different configuration
    for k in range(8):
        x_value= x + x_move[k]
        y_value = y + y_move[k]

        for x1 in range(8):
            print(solution[x1])
        print()
        if isSafe(x_value,y_value,solution):
            solution[x_value][y_value] = moveI
            if knightsTour(x_value,y_value,moveI+1,x_move,y_move,solution) is True:
                return True
            else:
                solution[x_value][y_value]=-1
    return False          

x_move=[ 2, 1, -1, -2, -2, -1, 1, 2  ]
y_move=[1, 2, 2, 1, -1, -2, -2, -1]
solution = [[-1 for x in range(8)] for x in range(8)]
solution[0][0]=1
knightsTour(0,0,2,x_move,y_move,solution)
suvojit_007
  • 1,690
  • 2
  • 17
  • 23
  • x_move and y_move give the next move of x and y coordinate respectively – suvojit_007 Aug 03 '18 at 06:03
  • A nicer idiom than stepping integer k through separate lists `x_move, y_move` is to directly do `for (x_move, y_move) in ((2,1), (1,2), (-1,2), (-2,1), (-2,-1), (-1,-2), (1,-2), (2,-1)):` – smci Aug 03 '18 at 06:23
  • You can get an enormous speedup by **using the 200-year-old heuristic [Warnsdorf's rule](https://en.wikipedia.org/wiki/Knight%27s_tour#Warnsdorf's_rule)**, which says pick the square from which there are fewest onward moves; this nudges you towards edges, corners and areas you've already visited. So instead of having a `isSafe()` returning boolean, you would now have `onwardMoves()` returning int 0..8, and you pick the candidate with the lowest (>=1). Supposedly you can do in this in linear time. – smci Aug 03 '18 at 06:36
  • I'm voting to close this question as off-topic because it was modified after a correct answer was posted – Reblochon Masque Aug 03 '18 at 06:56
  • Can you prove my code wrong? You haven't read my question properly and gave the same answer without any modification. Is your deleted code working for 8*8 like 5*5? – suvojit_007 Aug 03 '18 at 07:17
  • @ReblochonMasque just run your code for 8*8 and you will get what I'm trying to say in this question. – suvojit_007 Aug 03 '18 at 07:20
  • This question was changed, from "why is it taking so long", to "What improvements need to be done to make it as quick as possible"! there is no telling what you really want! – Reblochon Masque Aug 03 '18 at 07:23
  • @ReblochonMasque don't take me wrong but the code I have given is not working fine for 8*8 and it's taking too long to compute. I have mentioned it's working till 61st step in my question. – suvojit_007 Aug 03 '18 at 07:25
  • suvojit_007: I just explained to you how to implement Warnsdorf's rule. That's your answer. Have you done it yet? – smci Aug 03 '18 at 07:30
  • Possible duplicate of https://stackoverflow.com/questions/20783702/knights-tour-baktracking-lasts-too-long – tkruse Apr 07 '20 at 05:34
  • Does this answer your question? [Knight's tour backtrack implementation choosing the step array](https://stackoverflow.com/questions/21511683/knights-tour-backtrack-implementation-choosing-the-step-array) – tkruse Apr 07 '20 at 05:36

0 Answers0