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).
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.)
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.
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:
The C++ code that solves this problem is:
Hi, I'm srcmake. I play video games and develop software.
Pro-tip: Click the "DIRECTORY" button in the menu to find a list of blog posts.
License: All code and instructions are provided under the MIT License.