N-Queens

Try to solve the N-Queens problem.

We'll cover the following

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 both share the same row, column, or diagonal.

Constraints:

  • 1≤n≤91 \leq n \leq 9

Examples#

Created with Fabric.js 3.6.6 Sample example 1Input Output X X X X 2 The X on the board represents a square where a queen is placed. If we look carefully, the two valid configurations are mirror images of each other. X X X X n = 4

1 of 2

Created with Fabric.js 3.6.6 X X X X X X Sample example 2Input Output n = 6 4 One of the possible configurations isgiven on the right.

2 of 2

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

N-Queens

1

What is the correct solution to the 1-Queens problem?

A)

0

B)

1

C)

2

D)

4

Question 1 of 50 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Start by placing a queen in the first column of the first row of the chess board.

Since no other queen may be placed in a row that already has a queen, search for a safe position for the next queen in the next row.

Iterate over the rows to find a safe placement for the queens. Store the column number where a queen is placed in a list.

If a safe position is not found, backtrack to the previous valid placement. Search for another solution.

If a complete solution is found, add it to the results array, and backtrack to find other valid solutions in the same way.

Try it yourself#

Implement your solution in main.py in the following coding playground. We have provided some useful code templates in the other file that you may build on to solve this problem.

Python
main.py
backtracking.py
Input #1
N-Queens

Solution: Word Search

Solution: N-Queens