Trusted answers to developer questions

The n-queen problem

Get Started With Data Science

Learn the fundamentals of Data Science with this free course. Future-proof your career by adding Data Science skills to your toolkit — or prepare to land a job in AI, Machine Learning, or Data Analysis.

Given a chessboard of n x n, the n-queen problem involves placing nn queens in such a way that they cannot attack each other.

The queens can attack each other if they are placed in:

  • the same column
  • the same row
  • the same diagonal

No valid solution exists for a 2 x 2 or a 3 x 3 chessboard.

Algorithm

Backtracking can be used to solve this​ problem.

  1. Begin with the left-most column.

  2. For every row in the column:

    2.1. Try placing the queen such that it cannot attack the queen in the previous columns.

    2.2. If such a placement is possible, add this cell to the solution set and recursively check if this leads to a solution by calling the function on the subsequent column. If it does, return one.

    2.3. Else, remove this cell from the solution set.

  3. Backtrack to the previous column by returning zero if no solution exists after the completion of step 2.

  4. Stop the recursion when all the queens are placed.

Dry run

The following illustration shows the algorithm in action on a 4 x 4 chessboard:

1 of 14

RELATED TAGS

n-queen
backtracking
recursion
Copyright ©2024 Educative, Inc. All rights reserved
Did you find this helpful?