# Backtracking - N-Queens

All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.

Difficulty: Easy

DFS, Backtracking, 3 visited sets

## Problem

The **n-queens** puzzle is the problem of placing `n`

queens on an `n x n`

chessboard such that no two queens attack each other.

Given an integer `n`

, return *all distinct solutions to the n-queens puzzle*. You may return the answer in

**any order**. Each solution contains a distinct board configuration of the n-queens’ placement, where

`'Q'`

and `'.'`

both indicate a queen and an empty space, respectively.**Example 1:**

1
2
3

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

**Example 2:**

1
2

Input: n = 1
Output: [["Q"]]

## Solution

This is a classic backtracking algorithm. Even though in LeetCode it’s **Hard** problem, you need to understand and practice this such a way that it becomes a simple problem to solve.

At a high level, we have to go through every row and col and find out if we can place a **Queen** there. We are going to use backtracking algorithm as not all path will lead to the solution. Also understand there are multiple solutions and we need to find all.

As you know the **Queen** in the **Chess** game one of the most powerful unit as the queen can move in all direction including diagonal. Now in every iteration we can find if there are existing Queen in the same col and two diagonals.

Refer the figure below, in order to place a queen we need to make sure there is no queen in the same col or diagonally.

Two questions arises from here:

Why not find in

`row`

as well? Why just col and two diagonals.- We are going to process each row one by one, so we can be sure that in the current row there are no queen. Hence no need to keep track of
`row`

- We are going to process each row one by one, so we can be sure that in the current row there are no queen. Hence no need to keep track of
Identifying if a queen exists in the same

`col`

is a very simple comparison, however, how to find the same for all diagonals as both the row and col value will be different for each diagonals.There is a trick we will be using. I feel due to this trick the question was flagged as

**Hard**in LeetCode.There is a concept of

**negative constant**and**positive constant**. Let’s look at the diagram below.As you notice,

`row-col`

and`row+col`

stays constant diagonally. We can use to track if there is any queen diagonally.

Remaining of the problem is very simple. Let’s start the step by step process.

Create three sets for storing `col_tracker`

, `positive_constant`

and `negative_constant`

. Create an `output_boards`

array for storing all the solutions. There will be more than one solution, hence we need an array. Consider these are 3 `visited`

sets.

1
2
3

col_tracker, positive_constant , negative_constant = set(), set(), set()
output_boards=[]

Next part is creating an empty board with all dots `.`

. We will be creating a 2D Array as we need to track `col_tracker`

, `positive_constant`

and `negative_constant`

. Before adding the solution to `output_boards`

we will transform it to array of strings.

1
2
3
4
5
6

[
['.', '.', '.', '.'],
['.', '.', '.', '.'],
['.', '.', '.', '.'],
['.', '.', '.', '.']
]

1

board = [["."]*n for i in range(n)]

The backtracking algorithm takes the row number to process. We will use a basic `dfs()`

for backtracking.

1
2
3

def dfs(row):
...

As in all the `dfs()`

function we need to define the base condition. Here once the `row_number`

reaches `n`

(passed the last row `n-1`

) we know that we were able to place all our queens. So we can add the result to `output_boards`

and return. We convert the 2D array to 1D array with strings and append that to the `output_boards`

1
2
3
4

def dfs(row):
if row == n:
output_boards.append(["".join(r) for r in board])
return

So if we have not processed all the rows yet, we need to try to place a Queen in the current now. Now it’s the time to loop through each column in the current row to identify in which `col`

a queen can be places. If no queen can be placed we just return.

1
2

for col in range(n):
...

Inside the loop, we fist need to find if the current `col`

is eligible to have a queen by looking into `col`

, `positive_constant`

and `negative_constant`

sets. If not then just `continue`

and pick the next `col`

.

1
2
3

for col in range(n):
if col in col_tracker or (row+col) in positive_constant or (row-col) in negative_constant:
continue

Once we past the above step we know a queen can be placed in current `col`

. So let’s track all three of them.

1
2
3
4
5

col_tracker.add(col)
positive_constant.add(row+col)
negative_constant.add(row-col)
board[row][col]="Q"

Now we can call the `dfs(row)`

function again to process the next `row`

1

dfs(row+1)

Now, the backtracking part, we need to reset all the visited sets and the board so that another combination can be found.

1
2
3
4
5

board[row][col]="."
negative_constant.remove(row-col)
positive_constant.remove(row+col)
col_tracker.remove(col)

At this point we are pretty much done. Call the `dfs()`

function by passing `row=0`

and return `output_boards`

.

1
2

dfs(0)
return output_boards

## Final Code

Here is the full code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def n_queen(n):
col_tracker, negative_constant, positive_constant = set(), set(), set()
output_boards = []
board = [["."]*n for i in range(n)]
def dfs(row):
if row == n:
output_boards.append(["".join(r) for r in board])
return
for col in range(n):
if col in col_tracker or (row+col) in positive_constant or (row-col) in negative_constant:
continue
col_tracker.add(col)
positive_constant.add(row+col)
negative_constant.add(row-col)
board[row][col] = "Q"
dfs(row+1)
board[row][col] = "."
negative_constant.remove(row-col)
positive_constant.remove(row+col)
col_tracker.remove(col)
dfs(0)
return output_boards