[Interview Question] N-Queens w/ Backtracking (Leetcode Hard)

To watch the youtube video explaining this topic, please click here.

Introduction - N-Queens

N-Queens is an interesting problem. It requires knowing the Backtracking algorithm to solve efficiently, and also requires a fair bit of code compared to standard algorithm questions.

In this blogpost, we'll solve the N-Queens problem. If this is your first time seeing Backtracking, please look at the previous tutorial on Backtracking on an easier problem. Additionally, our solution will show "good object oriented code" since we'll utilize a class structure to solve this (as opposed to pure code inside of functions).

Problem Statement

Given a number n, return all valid nxn chessboards that have n queens placed on them such that no Queens are attacking each other. (Problem on Leetcode.)

A 4x4 chessboard with 4 Queens on it. Notice their attack patterns.

---

---

Solution

We're going to create an nxn chessboard and we continually try to place Queens on it (and if the board ends up valid with n queens on it, then we add it to our solution set), but we're going to be smart about how we place the Queens. Specifically, we're going not going to place Queens on a spots that are already being attacked. 

Let's represent the chessboard as a matrix of integers. -1 means a Queen is on a cell, otherwise the number represents the number of Queens that are attacking that cell.

The flow is to try adding Queens on a valid cell -> update the board to mark the positions she attacks, and then try adding more queens. Whenever we reach the end of a board (no more Queens can be added or we're at the final cell), we add the board if possible, and then we backtrack by removing the previous Queen we added and try placing a new Queen somewhere else.

The flow of solving the N Queens problem using backtracking. We continuously place Queens and update the board with the positions being attacked.

In our case of backtracking, our shared state is the chess board, and we recursively place Queens (and update the board) and then remove that Queen (and update the board).

In addition, some optimizations we'll take advantage of are:

1. Every row needs to have exactly one Queen.
2. After placing a Queen on a tile and trying all possibilities for the rest of the board, you never need to try placing a Queen on that tile again.

​The C++ code that solves this problem is:

​​Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels. 

Twitter: @srcmake
Discord: srcmake#3644
Youtube: srcmake
Twitch: www.twitch.tv/srcmake
​Github: srcmake