Week 2 at Hack Reactor proved to be as challenging as the first if not a little tougher. We were introduced to a new excercise which was to solve the nQueens problem. The n stands for the set number of queens placed on an n x n board. The queens have to be placed on the board so that they do cannot attack each other on the first move. The idea is very easy to understand. The real trick is returning every possible board configuration each time.
During our excercise we were given an already set up version of how the program should work. It was up to us to figure out how to create the boards and return the number of possible boards that n could configure.
A board is represented by an arrays within an array.
//an example of the chessboard if n = 5
[[1,0,0,0,0], [0,0,1,0,0], [0,0,0,0,1], [0,1,0,0,0], [0,0,0,1,0]]
0’s represent an empty space and the 1 represents a queen. Queens can move horizontally, vertically and also in all diagonals. In this case none of the queens can attack each other on the first turn, so this is a succesfully board. If this function were completely finished if n = 5 there are 10 possible solutions to the problem.
nQueens is a very unique problem to solve due to the fact that there is no easy or quick way to solve it. This problem has exponential time complexity when trying to solve it and can crash your computer if you try to input a high number. To date, I believe nQueens has only been solved up to a 26 x 26 board. To give you an idea of how hard this problem is on your computer a 23 x 23 board has 2,423,393,764,440 different solutionas.
If you have a trick that you implemented or a question about how to go about solving nQueens leave me a comment or share this with your fellow programmers.