Solving the N-Queens Problem with JavaScript

Here, I’ll walk you through the solution to the famous ‘N Queens’ math problem using pure JS, which I did as a project during my time studying at Hack Reactor.

The problem

The N Queens problem is a classic puzzle that asks “how many different ways can you fit N queens on a N*N chess board without any of them being in a position to attack each other?”. Besides being a great brain teaser, it is also very useful in computer science when demonstrating optimization techniques and time complexity in programs.

The approach

I chose to start this problem by writing several functions that would test whether a chess piece could be put on a particular spot on the board without creating any conflicts. From there, I knew I could write a function that goes across the top row of the board (left to right), systematically puts a piece down, and tests whether or not that piece creates conflicts. If it doesn’t, I could repeat the process for the row below it, and when the function had gotten to the bottom row, it would know it had found a solution. Because of the decision-tree like structure of the process, I knew that the solution may require the use of recursion.

Helper functions

I started by creating 6 functions, which served to test whether a particular spot on the board would create a conflict if a piece was placed there. The first two function are shown below, which simply loop through each spot on the board and test if there are any ‘row’ conflicts.

After these two functions were finished, I used the same technique to write functions that test for column conflicts as well as (both directions of) diagonal conflicts. Finally, I combined them to create a final function called hasQueensConflicts. I also created a ‘board’ prototype that could create a new board of size n*n.

Solver function

To the left is the actual solver function itself. On line 138, I create a ‘solutionCount’ variable to keep track of how many solutions have been found so far. I also hardcode the function to automatically return zero if the board size is 2*2 or 3*3, because boards of that size cannot have any solutions and checking them would waste time.

On line 145 I define a function called ‘solver’. This function loops through each spot on a particular row and checks to see if placing a piece there would create a conflict. If it not, then it calls itself on the row below. As a result, the function will eventually end up on the bottom row, and will find a spot where placing a piece creates no conflicts.

At this point, it has found an arrangement of pieces on the board where there is a piece on each row (so there are n pieces) and none of them have a conflict, which means we have a solution! This is the ‘base case’, and as shown on line 146, iterates the solutionCount counter.

The last step, as shown on line 158, is to pick up the piece (using a togglePiece method which I had pre-written). This is important to ensure the function properly loops through the row analyzing and counting answers for only one top piece position at a time.