Backtracking is an algorithmic paradigm that tries different solutions until finds a solution that . Problems which are typically solved using backtracking technique have the following property in common. These problems can only be solved by trying every possible configuration and each configuration is tried only once. A Naive solution for these problems is to try all configurations and output a configuration that follows given problem constraints. Backtracking works in an incremental way and is an optimization over the Naive solution where all possible configurations are generated and tried.Problem :Given a N*N board with the Knight placed on the first block of an empty board. Moving according to the rules of chess knight must visit each square exactly once. Print the order of each the cell in which they are visited.Time Complexity : There are N2 Cells and for each, we have a maximum of 8 possible moves to choose from, so the worst running time is O(8N^2).Naive Algorithm for Knights tour The Naive Algorithm is to generate all tours one by one and check if the generated tour satisfies the constraints. `while there are untried tours{ generate the next tour if this tour covers all squares { print this path; }}`knightTour(x, y, move, sol, xMove, yMove)Input       (x, y) place, number of moves, solution matrix, and possible x and y movement lists.Output   The updated solution matrix if it exists.Backtracking Algorithm for Knights tour Following is the Backtracking algorithm for Knights tour problem. `If all squares are visited print the solutionElse a) Add one of the next moves to solution vector and recursively check if this move leads to a solution. (A Knight can make maximum eight moves. We choose one of the 8 moves in this step). b) If the move chosen in the above step doesn't lead to a solution then remove this move from the solution vector and try other alternative moves. c) If none of the alternatives work then return false (Returning false will remove the previously added item in recursion and if false is returned by the initial call of recursion then "no solution exists" )`Source code:n = 8def isSafe(x, y, board):    if(x >= 0 and y >= 0 and x < n and y < n and board[x][y] == -1):        return True    return Falsedef printSolution(n, board):    for i in range(n):        for j in range(n):            print(board[i][j], end=' ')        print()        def solveKT(n):    board = [[-1 for i in range(n)]for i in range(n)]    move_x = [2, 1, -1, -2, -2, -1, 1, 2]    move_y = [1, 2, 2, 1, -1, -2, -2, -1]    board[0][0] = 0    pos = 1    if(not solveKTUtil(n, board, 0, 0, move_x, move_y, pos)):        print("Solution does not exist")    else:        printSolution(n, board)def solveKTUtil(n, board, curr_x, curr_y, move_x, move_y, pos):    if(pos == n**2):        return True    for i in range(8):        new_x = curr_x + move_x[i]        new_y = curr_y + move_y[i]        if(isSafe(new_x, new_y, board)):            board[new_x][new_y] = pos            if(solveKTUtil(n, board, new_x, new_y, move_x, move_y, pos+1)):                return True            board[new_x][new_y] = -1    return Falseif __name__ == "__main__":    solveKT(n)Output:` 0  59  38  33  30  17   8  6337  34  31  60   9  62  29  1658   1  36  39  32  27  18   735  48  41  26  61  10  15  2842  57   2  49  40  23   6  1947  50  45  54  25  20  11  1456  43  52   3  22  13  24   551  46  55  44  53   4  21  12`

More Articles of Bhanu Prakash Reddy M:

Name Views Likes
Python Geolocation with GeoIP2 1191 61
Python Geoip2 Modules 1237 34
Python Geoip Enriching MMDB files 1088 16
Python Geoip2 Configuring geolocation 1160 24
Python Random Module 1039 22
Python GeoIP2 Precision Services 1065 24
GeoIP - MaxMind GeoIP2 API 1566 21
Python Generate secure random numbers 1055 41
Python - Generic output formatting 716 11
Python - Prims minimum spanning tree 807 22
Python Program for Choosing Balls 1367 17
Python - Dijkstras shortest path algorithm 1452 24
Python Cryptographic Secure hashes and message digests 1168 65
Python program for Smallest Palindrome 1822 13
Python program for Friends on Facebook 1253 21
Python Cryptographic Generating tokens 975 13
Python - Cookies in CGI 1608 23
Python - Stream Encoding and Decoding 999 16
Python program for frequency is a function that takes as input a list of integers and returns a pair of the form (minfreqlist,maxfreqlist) 1682 42
Python - Stateless Encoding and Decoding in Binary data service 821 22
Python Binary Data Services 789 92
Python CGI Environment Variables 864 20
Python GeoIP2 JavaScript Client API 1103 33
Python - CGI Programming 629 39
Python program for panagram 1364 30
Plotting Series in Python 1273 24
GeoIP in PYTHON 1358 23
Python Concrete exceptions 1140 12
Python Geoip Maxmind 1206 34
Python Random module --2 939 18
Python-- Programs 1176 14
Python Types of Anonymous IPs and How They Affect Your Business 1049 19
Python Cryptographic Introduction 991 11
Geoip-IP geolocation information in Python. 1241 15
Python Geoip Database Reader Exceptions 1185 30
Python Data Changes to GeoIP Legacy 973 10
Python - Binary Data Services - 2 721 33
Python Program for Rotate Matrix Elements 1141 11
Python Program post-order traversal of a tree without using recursion 902 22
Python Program In-order traversal of a tree without using recursion 1151 28
Python MaxMind GeoIP2 1313 33
Python The Easy Way to Use MaxMind GeoIP 1546 25
Python Program 1277 20
Python GeoIP2 Databases with HAProxy Enterprise 1053 25
Python The Knights tour problem 1791 47
Python User-defined Exceptions 897 57
Python Program pre-order traversal of a tree without using recursion 1019 29
Python - Standard Encodings in Binary Data service 753 29
Python Binary Data Service Error Handlers 696 51
Python program for Domino Solitaire 2005 22
Python Built-in Exceptions 938 13
CGI Programming-2 860 49
GeoIP -- Flask. 1368 15
Python IP Geolocation 1018 13
Python Concrete exceptions part-2 1329 28