CODEWITHSUNDEEP
pythonknights-tour
PeterPefi
PeterPefi

Reputation: 99

Knight's Tour only solvable for one size board

I am trying to implement a knight's tour finder in python. Assuming the knight must start at the top left corner (called (0,0) here), it finds a solution for a 4x3 field, but not for any other fields.

def maneuvrability(position, path, width, height):
    if position[0] < width and position[1] < height and position not in path and position[0] >= 0 and position[1] >= 0:
        return True
    else:
        return False
        
def completedness(path,width,height):
    if len(path) == (width*height):
        return True
    else:
        return False
    
def possible_jumps(pos):
    return_list = []
    return_list.extend([
        (pos[0]-1,pos[1]-2),
        (pos[0]+1,pos[1]-2),
        (pos[0]+2,pos[1]-1),
        (pos[0]+2,pos[1]+1),
        (pos[0]-1,pos[1]+2),
        (pos[0]+1,pos[1]+2),
        (pos[0]-2,pos[1]-1),
        (pos[0]-2,pos[1]+1)])
    return return_list
    
def knights_tour(width,height,path=[(0,0)]):
    if completedness(path,width,height):
        return path
    else:
        elem = path[len(path)-1]
        succs = []
        succs.extend(possible_jumps(elem))
        for x in succs:
            if maneuvrability(x,path,width,height):
                return knights_tour(width,height,[y for y in path + [x]])
    
print(knights_tour(4,3))
print(knights_tour(5,5))

Upvotes: 0

Views: 131

Answers (1)

Jerry Halisberry
Jerry Halisberry

Reputation: 175

Your backtracking is not correct. At every step, you are only checking if the next move is valid, and then returning whether or not that move results in a knight's tour. Instead, you need to adapt the code to check all valid moves, and then see if any of them resulted in a complete knight's tour.

Upvotes: 1

Related Questions