Knight Tour

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
12 upvotes
Asked in companies
SamsungIBMRupeek

Problem statement

You are given a chessboard consisting of ‘N’ rows and ’M’ columns. Rows are numbered from 0 to ‘N-1’ and columns are numbered from 0 to ‘M-1’. Cell(i, j) is the cell at the intersection of the ith row and the jth column.

A knight is a chess piece that can move from cell (x1, y1) to the cell (x2, y2) if one of the following conditions is met:

|x1−x2| = 2 and |y1−y2| = 1, or

|x1−x2| = 1 and |y1−y2| = 2.

A knight cannot move outside the chessboard.

Initially a knight is placed at the cell(0, 0) of this chessboard, Moving according to the rules of chess, the knight must visit each cell exactly once. Find out the order of each cell in which they are visited.

Note :

1. There are multiple possible orders in which a knight can visit each cell of the chessboard exactly once. You can find any valid order.
2. It may be possible that there is no possible order to visit each cell exactly once. In that case, return a matrix having all the values equal to -1.

Example :

Consider an 8*8 chessboard, one possible order for visiting each cell exactly once is shown in the image below. Numbers in cells indicate the move number of the Knight.

alt text

Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The next T lines represent the ‘T’ test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’ representing the number of rows and columns in the chessboard respectively.
Output format : 
For each test case, In a separate line print ‘Possible’ If knight tour exist otherwise print ’Impossible’

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N, M <= 8

Where ‘T’ is the total number of test cases, ‘N’, ‘M’ is the number of rows and columns respectively.

Time limit: 1 sec
Sample Input 1 :
2
1 2
8 8
Sample Output 1 :
Impossible
Possible
Explanation of Sample Input 1 :
Test case 1 :
In this case,  it is not possible to visit each cell exactly once. Knight cannot move from cell (0, 0) to any other cell. ‘Impossible’ will be the output if you report it correctly.

Test case 2 :
See the problem statement for an explanation.
Sample Input 2 :
2
5 5
1 3
Sample Output 2 :
Possible
Impossible
Hint

Find out all possible ways to visit each cell of the chessboard exactly once, and verify whether it is a possible knight tour or not.

Approaches (2)
Brute Force

There are N*M cells in the chessboard thus, we can assign a unique integer between 0 to N*M-1 to each cell in  (N*M)! Ways. For each of these ways, we will check whether it represents a possible knight tour or not.  We can one by one generate all the permutations using the  nextPermuation method as described below.

 

  • Create a function nextPermution(permutation, n) that finds the next permutation of a given array 'permutation’ of size ‘n’. In this function, we do the following.
    • Start iterating the array from backward and find an index ‘i’ such that permutation[i] < permutation[i+1]. Return false, if such an index doesn’t exist.
    • Find an index ‘j’ such that permutation[j] is the smallest integer in the suffix starting from ‘i’  for which condition permutation[j] > permutation[i] holds true.
    • Swap permutation[i] with permutation[j].
    • Reverse suffix starting from ‘i’.
    • Return true as it indicates the next permutation exists. Note, in this approach, we have modified the given permutation to its lexicographically next permutation.  

 

Algorithm

  • Create an integer matrix order[][] of size ‘N’ * ‘M’ and fill it with -1 initially, order[i][j] will indicate the move number of Knight to reach cell (i, j). If order[i][j] is -1, it indicates the cell(i, j) is not yet visited.
  • Create a list ‘permutation’ of size N*M. Initially permutation[i] = i.
  • Find out all permutations of array ‘permutation’ in which ‘permutation[0]’ is 0. For each of the permutation do the following
    • Run a loop where ‘i’ ranges from 0 to N*M-1 and for each ‘i’ assign order[i/N][i%N] := permutation[i].
    • Initialize boolean variable ‘flag’:= false.
    • Check out whether that matrix order represents a valid knight tour or not. This can be done by initializing an integer variable ‘move’:= 0, and ‘x’, ‘y’ to 0, and then run a loop till move < N*N, in each iteration we check 8 cells {(x+2, y+1), (x+2, y-1), (x-2, y+1), (x-2,y-1), (x+1, y+2), (x+1, y-2), (x-1, y+2), (x-1, y-2) } that whether any of them has integer move+1, if yes then we increment move by ‘1’ and change ‘x’, ‘y’ to that cell, if not then we break the loop by updating flag to false.
    • If flag is true, return matrix order.
  • If there is no possible way, fill the matrix order by -1, and then return it. A matrix completely filled by -1 indicates no solution exists.
Time Complexity

O(N*M*(N*M!)), where  ‘N’, ‘M’ is the number of rows and columns respectively.

 

There are N*M! Permutation and for each permutation, we take O(N*M) time to verify whether it is a valid knight tour or not. Thus, the final time complexity will be 

O(N*M*(N*M!)).

Space Complexity

O(N*M), where  ‘N’, ‘M’ is the number of rows and columns respectively.

 

The size of the matrix order is N*M. Thus, the final space complexity will be O(N*M).

Code Solution
(100% EXP penalty)
Knight Tour
Full screen
Console