Python The Knights tour problem














































Python The Knights tour problem





The Knights tour problem:


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 solution
Else
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 = 8
def isSafe(x, y, board):

    if(x >= 0 and y >= 0 and x < n and y < n and board[x][y] == -1):
        return True
    return False
def 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 False
if __name__ == "__main__":

    solveKT(n)


Output:


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





More Articles of Bhanu Prakash Reddy M:

Name Views Likes
Python - Generic output formatting 360 11
Python - Standard Encodings in Binary Data service 330 29
Python - Stream Encoding and Decoding 379 16
Python - Stateless Encoding and Decoding in Binary data service 355 22
Python Binary Data Service Error Handlers 353 51
Python - Binary Data Services - 2 373 33
Python Binary Data Services 390 92
Python - Dijkstras shortest path algorithm 467 24
Python - Prims minimum spanning tree 403 22
Python - Cookies in CGI 346 23
Python CGI Environment Variables 377 20
CGI Programming-2 389 49
Python - CGI Programming 385 39
Python The Knights tour problem 538 47
Python User-defined Exceptions 627 57
Python Concrete exceptions part-2 630 28
Python Concrete exceptions 617 12
Python Built-in Exceptions 631 13
Python Program In-order traversal of a tree without using recursion 645 28
Python Program pre-order traversal of a tree without using recursion 641 29
Python Program post-order traversal of a tree without using recursion 652 22
Python Cryptographic Generating tokens 709 13
Python Cryptographic Secure hashes and message digests 697 65
Python Cryptographic Introduction 734 11
Python Generate secure random numbers 733 41
Python Random module --2 735 18
Python Random Module 736 22
Python IP Geolocation 754 13
Python Data Changes to GeoIP Legacy 749 10
Python Geoip Enriching MMDB files 758 16
Python The Easy Way to Use MaxMind GeoIP 795 25
Python Types of Anonymous IPs and How They Affect Your Business 774 19
Python GeoIP2 Databases with HAProxy Enterprise 773 25
Python Geoip Maxmind 798 34
Python Geoip2 Configuring geolocation 810 24
Python Geolocation with GeoIP2 808 61
Python GeoIP2 JavaScript Client API 814 33
Python GeoIP2 Precision Services 816 24
Python Geoip2 Modules 880 34
Python Geoip Database Reader Exceptions 880 30
Python MaxMind GeoIP2 863 33
Python program for panagram 891 30
Python program for Smallest Palindrome 916 13
Python program for Friends on Facebook 938 21
Python Program for Choosing Balls 896 17
Python program for frequency is a function that takes as input a list of integers and returns a pair of the form (minfreqlist,maxfreqlist) 928 42
Python Program for Rotate Matrix Elements 895 11
GeoIP -- Flask. 911 15
Geoip-IP geolocation information in Python. 908 15
GeoIP - MaxMind GeoIP2 API 918 21
Python Program 919 20
Python program for Domino Solitaire 925 22
Python-- Programs 910 14
Plotting Series in Python 931 24
GeoIP in PYTHON 965 23

Comments