Learn to Code via Tutorials on Repl.it!

← Back to all posts
A simple tutorial on the N Queens problem
FlaminHotValdez (750)

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.

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.

Comments
hotnewtop
programmeruser (618)

smh

Should be in snake case: is_safe

Why and?

FlaminHotValdez (750)

@programmeruser

  1. I'm a competitive programmer. It's inconvenient to type many lines of headers and add std:: in front of a ton of different things.

  2. My keyboard is massive so I can't afford to type underscores

  3. Because my first language is Python and it rubbed off on me.

programmeruser (618)

@FlaminHotValdez also, am I the only person that thinks that functional (map/filter/reduce) is better than imperative (for)?

FlaminHotValdez (750)

@programmeruser Me no understand. I'm smallbrain when it comes to functions, I'm more of a logic guy than an actual programming guy.

EpicGamer007 (1794)

@programmeruser in c++, should you generally use camelCase or snake_case? I see people use both so I am not sure..

FlaminHotValdez (750)

@EpicGamer007 Yes I know but I'm lazy lol, both work. Like I said my keyboard is massive so if I can avoid using the shift key I'll do it.

EpicGamer007 (1794)

also, @programmeruser, I was talking to xh about how to store passwords in a db, but he said you would know more about this so... what is the best way to store passwords in a db? I obviously do not want to put passwords in the db just like that without modifying it, but what steps do we need to take?

DynamicSquid (5070)

Cool!

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

Also why are you using and?

FlaminHotValdez (750)

@DynamicSquid

  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 (5070)

@FlaminHotValdez Ah, okay.

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

FlaminHotValdez (750)

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

DynamicSquid (5070)

@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 (750)

@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 (5070)

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