Solve N-Queens Problem

Find how many ways N queens may be placed on an N x N chessboard, such that the queens do not attack each other.

Statement

Given a chessboard of size N×NN \times N, determine how many ways NN queens can be placed on the board, such that no two queens attack each other.

A queen can move horizontally, vertically, and diagonally on a chessboard. One queen can be attacked by another queen if it is present in the same row, column, or diagonal of that queen.

Example 1

Below is a valid placement of 44 queens on a 4×44 \times 4 chessboard. The XX on the board represents a square where a queen is placed:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.