##### 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.

You are viewing a single comment. View All
DynamicSquid (5016)

Cool!

But why are you using <bits/stdc++.h>?

Also why are you using and?

FlaminHotValdez (712)
1. Because I'm a competitive programmer and I don't like to have 10 lines of headers

2. Because C++ is my second(although my main) language. My first language was Python, but I don't use it very often. But the and stuff rubbed off on me so I use it to this day.

DynamicSquid (5016)

@FlaminHotValdez Ah, okay.

I'm also doing some competitive programming. What kind of contests do you do?

FlaminHotValdez (712)

@DynamicSquid Mostly just USACO, I'm on silver level right now but I average 1 problem correct :(

DynamicSquid (5016)

@FlaminHotValdez Oh nice! That's way above my level :)

I live in Canada, so I have the CCO instead, but to even qualify for that I have to get a high score on the CCC, and I can't even do half the problems on that yet!

FlaminHotValdez (712)

@DynamicSquid Wow, that's cool! But USACO silver really isn't all that high, it's the 2nd level out of 4 and I literally can only do 1 problem out of 3 :((((((

DynamicSquid (5016)

@FlaminHotValdez Oh I'm sure it's still challenging! I have to give it a try something soon