The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other. For example, following is a solution for 4 Queen problem.

For a larger N, this problem couldn’t be solved in polynomial time. So, it is an NP-Complete problem. However, this problem could be solved by backtracking in non-polynomial time.

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.

Solution of N Queen problem using backtracking checks for all possible arrangements of N Queens on the chessboard. And then checks for the validity of the solution. The code for the problem is below:

To read more: