Something a Little Different

Some of you may know that I recently started Hack Reactor Remote, an online computer coding bootcamp, with the aim of changing careers and becoming a software developer.  The reasons for doing so are myriad and I won't go into them now, but if you want to know, just ask!  (But don't expect an answer anytime soon as my schedule is now jam-packed.)

I want to write about one of the modules I just completed, called n-queens, which is a mathematical question that asks, "For an n x n chessboard, how many different ways can I place n number of queens in such a way that they cannot attack one another?"  You could also ask the same question for rooks as well, which is what I will be focusing on in this post.

One could fairly easily draw the problem out on pen and paper for small values of n (i.e., the number of solutions for n values of 1, 2, 3, 4 are 1, 2, 6, 24, respectively).  However, that quickly gets out of hand, as the number of solutions for an n of 5 and 6 are 120 and 720, respectively.

This is where programming and computers come into play, as they can find those 720 solutions in a matter of seconds, and won't complain about you wasting their time either.

To start the problem, we were given an outline for helper functions that would work together to find a solution for us.

Below is the "hasAnyRooksConflicts" function:

As you can see, it calls on two helper functions itself, which check for any column and row conflicts to make sure a given rook placement is valid and does not conflict with any other rooks on the board.

Using this helper function we can then write a function "countNRooksSolutions" that uses recursion to check for valid solutions, as such:

You can see we call "hasAnyRooksConflicts" on line 60.  When we run the given tests, which give the function an n values of 1 through 8, it takes my computer almost 16 seconds to find all the solutions, as seen in the red box below:

As I mentioned above, it takes this long because there are a lot of solutions for my computer to calculate, here are just how many, as seen in the console of my Chrome dev tools:

Over 40,000 solutions for an n of 8!  Told you it gets out of hand quickly.  

Now, my computer is brand new, and it still took 16 sec to complete.  Imagine how much harder an older computer would have to work.  Saving time and computing power would be even more essential.  What if I said there was a way to cut that time in half?  

Let's take a look at our function again.  The way it's written, with each iteration of the for loop in lines 57 to 64, we are looking at the next row of the board.  Since we're already skipping rows, we don't need to check for row conflicts.  

So let's replace "hasAnyRooksConflicts" on line 60 with "hasAnyColConflicts" which just checks for column conflicts, because that's what we're really interested in:  

When we run it now, it takes less than 7 seconds: 

We cut our run time by over half!  To be honest, I'm slightly surprised by our result as I expected it to be closer to 7.7 seconds.  Perhaps the mechanics of what exactly are going on here would make a good future post.  In the meantime, I hope this helps some of my Hack Reactor classmates who's computer fans scream at them when they run this function.