N - Queens Problem

Problem statement

You are given an empty chessboard of size N * N. Find the number of ways to place N queens on the board, such that no two queens can kill each other in one move. A queen can move vertically, horizontally, and diagonally.

Solution: Backtracking approach

The idea is to place queens one by one in different columns, starting from the leftmost column. When we place a queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes, we backtrack and return false.

This is a difficult problem so let’s try to understand the approach and see how the backtracking will work.