N3s

The N-Queens problem, is about placing N number of Queens in a board of size NxN without threatening each other.

If you are into chess or you have been into Computer Science enough you probably have heard about this classical problem. 

This is a little puzzle where the objective is to find a way to place the same number of queens in a chess board than rows and columns, being the classical size 8 queens for a board of 8 rows and 8 columns. The puzzle is very simple to understand and solve, but not so easy when you try to code it. This is because in real life is very clear for us where or where not is posible to place a queen, in real life boards is pretty easy to validate a position. But that is the limit "real life boards", because once we move on to bigger sizes of boards, the validation problem turns hard and some times even impossible, that is why we code it.

We could separate the puzzle in 2 parts.

• The way we walk through the board.
• The validation of the cell.

1. The Approach.

The approach actually is very simple and probably is the easiest way to solve it, this solution is to go through every row and column, validating every cell of the board, validating and if the cell is not threathened already then we place there a queen a move to the next row or column and so on. If there is a column or row where there is no cell available for positioning a queen, it means we must go back and change a queen to get other options. And on the other side, if you reach the final row and column and we are able to place a queen without it is threatened, then it means we found a solution.

The simplest type of validating the cell is by creating loops and validating each direction, if there is one which found another queen, then the cell is not available. But in the next point we will find a way to optimize the validation cycle.

2. Optimization.

2.1. Randomness

One way to optimize this is the path we use, the algorithm that tell us how to travel the board. In this case I didn´t change it too much. There is a thing we must talk about here, "Randomness", sometimes taking an standarized path is not the fastest path, and in situations like this where we just need to find one solution where there are several of them, a little of randomness could be a good fit to our algorithm.

I randomized the selection of the first cell to check in every row. This also give us the possibility to find a different solution each time we run the code.

2.2. Validation.

When you are learning about optimization, you learn that there are times where a loop is not the most optimal way of implementation. And this is one of those cases. Changing the way we validate if the cell is available or not.

I used hash tables to eliminate the for loops. There is a method of the hash tables called "Has" which by passing a value, the method will return a boolean value depending if the value is already on the structure. This is a validation by it self, so it more helpful for the diagonals. 

For use this optimization for the diagonals, we must assign a value to each diagonal. In my case, for example, for the positive diagonal (the one from the bottom left to the top right) I called it the diagonal zero (0), each diagonal above it was a +1, and each diagonal bellow it was a -1, this giving us a structure which have an index of diagonals identified from -7 to 7 (for a board of size 8). The negative diagonal (top left to bottom right) followed the same approach.

The next stop was to find a way to get the value of every diferent diagonal using the coordenates of each cell. This is actually simple, for the positive diagonal, we used some substractions, the size of board less one, less the number of row (starting from 0) less the number of column (starting from 0). And from the negative diagonal, was easier, it was just number of column less number of row.

3. Learnings.

I implemented the same approach in different languages, my favorite was on JavaScript, because It was really efficient, capable of finding solutions for boards of size 100, in less than a second. And I actually made a web application from it, called Web Queens, with some limitations about the size of the board. But you can find the original CLI application in my GitHub.

So... How far could we go? I could say we can go further than boards of size 100, well at least that was my approach, I can´t say it is the optimal or the fastest, but it is fast and it is great.

From this project I also learned to print in different colors in the terminal making the result easier to look and understand. 

I´m very proud of my results and efforts with this project and I hope you like it too.

Thank you for your time.

See you soon on my next post. 😁