CODEWITHSUNDEEP
pythonrecursionbacktrackingrecursive-backtrackingknights-tour
Lou
Lou

Reputation: 103

Knights Tour with Backtracking

I'm trying to write a Python program which will solve the Knight's Tour problem using backtracking. For those unfamiliar: "The knight is placed on the first square of an empty chess board and, moving according to the rules of chess, must visit each square exactly once."

My code works mostly but not completely. It usually gets the 7th move and then returns an unfinished board. Why?

board = [
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]]

def move(x, y, count, move_x, move_y):
    if count == len(board)**2:
        return True
    for i in range(8):
        if is_valid(x + int(move_x[i]), y + int(move_y[i]), board):
            if move(x + move_x[i], y + move_y[i], count + 1, move_x, move_y):
                board[x][y] = count
                return True
    return False
    

def print_board(bo):
    for i in range(len(bo)):
        for j in range(len(bo[0])):
            if j == (len(board[0]) - 1):
                print(bo[i][j])
            else:
                print(bo[i][j], end = " ")


def is_valid(x, y, board):
    if x >= 0 and y >= 0 and x < len(board) and y < len(board) and board[x][y] == 0:
        return True
    return False



def solve(bo):
    print_board(board)
    move_x = [1, 2, 2, 1, -1, -2, -2, -1]
    move_y = [2, 1, -1, -2, -2, -1, 1, 2]
    counter = 1
    x_loc = 0
    y_loc = 0

    if not(move(x_loc, y_loc, counter, move_x, move_y)):
        print("No solution")
    else:
        print("                 ")
        print_board(board)

solve(board)

Upvotes: 2

Views: 816

Answers (2)

Manish Salunkhe
Manish Salunkhe

Reputation: 11

    def process(i,j,cnt,board,n,query):
    board[i][j]=cnt
    cnt+=1
    if cnt==n*n+1:
        for a in range(n):
            print(board[a])
        print()
        if query==0:
            return True
        else:
            True
    stack=[]
    
    if i+2<n and j-1>-1 and board[i+2][j-1]==-1:
        stack.append([i+2,j-1])
    if i+1<n and j-2>-1 and board[i+1][j-2]==-1:
        stack.append([i+1,j-2])
    if i-1>-1 and j-2>-1 and board[i-1][j-2]==-1:
        stack.append([i-1,j-2])
    if i-2>-1 and j-1>-1 and board[i-2][j-1]==-1:
        stack.append([i-2,j-1])
    if i-2>-1 and j+1<n and board[i-2][j+1]==-1:
        stack.append([i-2,j+1])
    if i-1>-1 and j+2<n and board[i-1][j+2]==-1:
        stack.append([i-1,j+2])
    if i+1<n and j+2<n and board[i+1][j+2]==-1:
        stack.append([i+1,j+2])
    if i+2<n and j+1<n and board[i+2][j+1]==-1:
        stack.append([i+2,j+1])

    while (len(stack))>0:
        curr=stack.pop()
        if query==0:
            if(process(curr[0],curr[1],cnt,board,n,query)):
                return True
            else :
                board[curr[0]][curr[1]]=-1
        else:
            process(curr[0],curr[1],cnt,board,n,query)
            board[curr[0]][curr[1]]=-1
    return


########     Driver Code     ########



    query=input("If you want program to output all possible ways of KNIGHT'S TOUR, say Yes or else say No :- ")
    if query[0]=='y' or query[0]=='Y':
        query=input("This process may be too slow for N greater than 5, it will work fast if N is less than 6. Are u sure u want to go for it? (Yes/No) :- ")
    if query[0]=='y' or query[0]=='Y':
        query=1
    else :
        query=0
    n=int(input("Enter the value of N :- "))
    if(n<5):
        print("Not possible for N less than 5")
    else:
        board= [[-1]*n for i in range(n)]
        cnt=1
        process(0,0,cnt,board,n,query)

    

########     Some precomputed outputs     ########


# N = 5
#
# [1, 12, 3, 18, 21]
# [4, 17, 20, 13, 8]
# [11, 2, 7, 22, 19]
# [16, 5, 24, 9, 14]
# [25, 10, 15, 6, 23]


# N = 6
#
# [1, 20, 3, 18, 5, 22]
# [36, 11, 28, 21, 30, 17]
# [27, 2, 19, 4, 23, 6]
# [12, 35, 10, 29, 16, 31]
# [9, 26, 33, 14, 7, 24]
# [34, 13, 8, 25, 32, 15]


# N = 7
#
# [1, 14, 3, 38, 5, 34, 7]
# [12, 39, 10, 33, 8, 37, 26]
# [15, 2, 13, 4, 25, 6, 35]
# [40, 11, 32, 9, 36, 27, 44]
# [19, 16, 21, 24, 45, 48, 29]
# [22, 41, 18, 31, 28, 43, 46]
# [17, 20, 23, 42, 47, 30, 49]


# N = 8
#
# [1, 60, 39, 34, 31, 18, 9, 64]        
# [38, 35, 32, 61, 10, 63, 30, 17]      
# [59, 2, 37, 40, 33, 28, 19, 8]        
# [36, 49, 42, 27, 62, 11, 16, 29]      
# [43, 58, 3, 50, 41, 24, 7, 20]        
# [48, 51, 46, 55, 26, 21, 12, 15]      
# [57, 44, 53, 4, 23, 14, 25, 6]        
# [52, 47, 56, 45, 54, 5, 22, 13]

Upvotes: 1

Tarik
Tarik

Reputation: 11209

  • The recursive call to move() should come after setting board[x][y] = count.
    • Moreover, if move() returns false, then you should have board[x][y] = 0
  • In fact, count does not need to be stored in each board cell. It just needs to be passed and incremented in each recursive call. You can use a boolean indicating whether a cell has been visited or not.
  • Final thoughts: There are 2^64 board states and many more paths to hit failure states repeatedly. As such, the failure states should be stored in a hash to avoid searching the failed paths repeatedly.

Upvotes: 4

Related Questions