Last Updated: 15 Feb, 2021

Knight Tour

Moderate

Asked in companies

Solve now

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

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

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

In this approach, we incrementally build the solution. In each step we check if moving to this cell violates the problem constraint, if it does then we remove that move and try other alternatives. If none of the alternatives works out then we go to the previous stage and remove the moves in the previous stages. If we reach the initial stage back then we say that no solution exists.

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.
Assign order[0][0] := 0, as it is the initial position of knight.
Make a recursive function knightTourHelper(order, N, M, x, y, move) that returns boolean true if it is possible to complete a tour of the chessboard satisfying all constraints from cell (x, y,) when ‘move’ moves are already completed, else it returns false. In each recursive step, we will do the following.
- If all the cells are visited, return true
- Otherwise check all possible 8 cells i.e (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) where knight can move from cell (x, y). For each of the unvisited and valid cells among these 8 cells assign move+1 to this cell in matrix order, and call knightTourHelper with new values, if knightTourHelper returns true for any of these possible moves then return true, else assign -1 again to this cell in order matrix, i.e., backtrack.
- If there is no possible way to complete the tour, i.e all recursive calls return false, then it means no solution exists, so we return false.
We call knightTourHelper(order, N, M, 0, 0, 0). If it returns false, fill each cell of the matrix order by -1 to indicate no solution exists.
Return matrix ‘order’.

Solve now