NikCreate

When I was working on PlayingWithCards, I had thought a lot about how cool it would be to have an AI that would determine its moves by playing through each possible possible combination of moves in imaginary games against another AI and determine which move led to more wins. At the time, I suspected something like recursion existed, but couldn’t see past making a bunch of for loops. My imagination has began to run again now with my introduction to backtracking algorithms and my first experience with the N-Queen’s challenge.

The N-Queen’s challenge is a popular programming challenge that asks for a function to take in a number (N), create a chess board with a length and width of that number and then find all possible solutions where that number of queens can be placed without being in range of another queen.

Having some experience with recursion but not quite seeing it’s full potential (I probably still don’t), I could understand how it was useful for searching through tree’s, but N-queen’s seemed like a totally different beast and the only way I could visualize solving it was to create an array containing all possible combinations of N queens, using a series of for loops, and then running through each one to see if it had a conflict, filtering them out to get an array that only contained the ones that didn’t. Had this gone forward, it’s likely it would have changed to check if the combination had a conflict before putting it into an array, but either way, for bigger boards, it was likely this program would take a long time to run.

Of course, I was introduced to a better way of solving it, which was easily the most eye opening moment for me with recursion so far. Instead of creating and storing who knows how many board states at once, a backtracking algorithm could be used to make and undo minor changes only going as far down a path as it needs to. Let’s take a look at how this process works.

In JavaScript, there is no grid like structure, so the best way to model a grid is an array of arrays, with each inner array containing a row. For a four by four grid, this would look like [[0,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0]]. With a four by four grid, the program would search for a combination of four queens that would be unable to attack each other. While there aren’t any successful combinations at this number, it should be a good size to demonstrate how the program searches.

In order to solve this, it’s best to go row by row, creating a for loop that will place a queen in each column in that row, removing the other queens as it places a new one. A conflict will be created if another queen is place in the same row, column or diagonal, so once a queen is placed in a row, the rest of that row can be ignored while the program is testing combinations using that spot.

After placing a queen in the first spot, the program will then move on to the next row by calling another iteration of the function on the next row. This will temporarily pause the current for loop, while the new iteration runs. On the second row, the loop starts by placing a queen in the first spot, then checking for a conflict and removing it if so. It continues a “for loop” through the columns until it successfully places a queen.

Once it’s placed the queen, it will again call another iteration of the column loop function.

Although with this combination, there is nowhere for it to place in the next row, and the problem is impossible to solve without a queen in each row, so after looping through the third row, it stops and doesn’t go any further.

At this point, the third iteration of the column loop function has failed and the program removes the last piece it placed and returns to its loop through the second row, right where it left off, placing a queen and calling the function again on the third loop.

While this combination will succeed on the third row, it won’t be able to successfully place in the fourth. The fourth row’s loop will break, running through the rest of the third row’s loop, which will also fail. The second row’s loop is already at it’s end, which means…

We’re all the way back at the very first iteration of our function, which will now move to the second spot and try everything all over until it’s looped through each path as far as it needs to realize they won’t work.

While a four by four grid with four queens won’t have any successes, in the event that one days, it can be detected through an if statement that will check if the row it is on is equal to the number passed into the function. Since the first row has an index of zero, the function being called again on the sixth row (index five) in the below example would mean that all five queens had been successfully placed with no conflicts, and the program has hit a success.

From there, while the current state of the board can be stored in an array of success or a count can be updated depending on what the goal of the user is, but make sure to store something as once this state ends, the last piece will be removed and the program will continue on with its many loops until it’s found each success.

Overall, this was a very interesting problem and really opened up a new way to approach problems for me. Through the recursive method, the program is able to stop as soon as it can’t continue instead of a normal for loop which would loop through each row regardless. Given the way the program looks ahead from a point, I wonder if the game of chess could be approached in the same way. If a program could see each possible move in a chess game and follow each of them until the end of the game, it could probably see the move that had the highest chance of success and possibly come up with a solid strategy. In that case, the opponent it played against would probably play a great role in what it learned, so it wouldn’t be perfect, but it’s still a fun idea that I’d like to approach in the future.

Then again, given the amount of combinations it had to test at higher numbers, this program alone was causing Chrome to crash at times. Before I attempt solving a game in a similar style, I’ll probably need to work on cutting down runtimes.