A simple tutorial on the N Queens problem
I had just finished coding my solution to the N Queens problem and I was curious how others had done it, so I turned to my trusty friend Repl.it and searched up the N Queens problem. All I could find were repls with gibberish code and no description. Oh no! No tutorials on how to do it? At that moment, I thought...
I'm gonna change that.
So what is the N Queens problem? Simple. Suppose we have an N by N chessboard. We want to find out how many ways we can put N queens on our N by N chessboard so that no queens are attacking each other. For those of you that don't know how to play chess, the queen can move any amount of tiles in any row, column, or diagonal. So our problem can boil down to this:
How many ways can you put N pieces on an N x N grid so that no two pieces are in the same row, column, or diagonal?
Well, the N Queens problem is a classic case of backtracking. Let's say we have an 4 by 4 chessboard and we want to put 4 queens on it. We start out in the first column and test every square on that column: Is it being threatened by any other queens? If not, put the queen there and move on to the next column. If so, move the queen down one tile. If you hit the end of the column and there is no suitable location, we backtrack to the previous row and move on from where we put the queen. Here's a simple pseudocode.
If that tile shares a diagonal with a tile that has a queen on it: If we're in the last column: Add one to the amount of possible ways. Otherwise: Move on to the next column. Otherwise: If we're at the end of the column: Backtrack to the previous column and pick up from where we put our last queen. Otherwise: Move on to the next tile
That being said, we have a pseudocode for this problem. The logic behind it is simple: for each column, we can only put one queen. If we've put down the queen for that column, we move on to the next one. This is a classic case of backtracking: if you're at a dead end, go back to where you had an option. I've attached my C++ implementation of the N Queens problem here, but you can do it in any language. However, due to the nature of the N Queens problem, it has a wide variety of possibilities. At a 25 by 25 board, there are over 275 trillion solutions to the problem, and the amount of solutions multiplies by 10 for every higher size. As such, it is rather illogical to regard this problem on a large scale, which means we can afford inefficient solutions such as backtracking.