CODEWITHSUNDEEP
recursionbacktrackingknights-tour
pythonc0der
pythonc0der

Reputation: 33

Knight's tour using backtracking

I have been given some initialisation code and told to write a function knight(n,y,x) to print a solution to the problem.

This initialisation code is

 size = 8
         board = []
         for y in range(size) :
             board = board + [[-1]*size]
         moves= [[1,2],[1,-2],[-1,2],[-1,-2],
                 [2,1],[2,-1],[-2,1],[-2,-1]]

And my code so far, which just seems to run forever is

def knight(n,y,x):
    if n == 0:
        board[y][x] = 0
        n = 1
    elif n == (size**2) :
        return board
    for j,i in moves:
        y1 = y+j
        x1 = x+i
        if y1 < size and x1 < size and y1>=0 and x1>=0 and board[y1][x1] == -1:
            board[y1][x1] = n
            knight(n+1,y1,x1)
            board[y1][x1] = -1
    return

But I can't figure why it is a problem. I have looked through a few of the existing questions on here but they use multiple functions where we have been told to just use the one. Could anybody please help?

Upvotes: 1

Views: 113

Answers (1)

Keldan Chapman
Keldan Chapman

Reputation: 658

I have found a problem in your code, which fixes it for everything up to 7x7 boards. I assume it works on 8x8, it just takes exponentially longer. You might have to implement some algorithm improvements to get it to be quicker. Anyway the error I found was:

You ARE finding the board, but you only return it one frame back. You need to set it up so that, if a board is found, the code returns it all the way back.

Try replace the following line:

knight(n+1,y1,x1)

with the following:

sol = knight(n+1,y1,x1)
if sol is not None:
    return sol

I'll have a go at trying to get an answer from the 8x8, and update this if I can help any more.

Upvotes: 1

Related Questions