Question

Give an algorithm to find the number of ways you can place knights on an N by M (M < N) chessboard such that no two knights can attack each other (there can be any number of knights on the board, including zero knights). Clear describe your algorithm and prove its correctness. The runtime should be O(2^3M * N).

Answer 1

• Consider that  K knights are to placed  on an M*N chessboard such that they don’t attack each other.
• A knight can move two squares vertically and one square horizontally or two squares horizontally and one square vertically.
• The knights attack each other if one of them can reach the other one in a single move.

----------------------------------------------------------------------------------------------------------------------------------------------------------------------

This can be solved using a backtracking algorithm.
Algorithm:

i) Start

ii) Enter the  knights position one by one starting from first row and first column

ii)Iterate forward to first row and second column such that they don’t attack each other.

iii)When one row is exhausted ,iterate over  to the next row.

iv)Before placing a knight, Insert a checking condition to check if the block is safe i.e. it is not an attacking position of some other knight.

v)If (block == safe),

  place the knight and mark it’s attacking position on the board

else

move forward and check for other blocks.

vi)In this process, make a new board every time a new knight is inserted into the board.

vii)continue until all possible solutions are obtained.

viii)Stop the program

----------------------------------------------------------------------------------------------------------------------------------------------------------------------

Correctness of this algorithm:

Since this algorithm is based on backtracking i.e, if we get one solution and we need the rest of the solutions, then we can backtrack to our old board with old configuration of knights and that can be used to find the other possible solutions.