Throughout a person's coding journey, they might encounter numerous algorithms and problems, each with its purpose and agenda. While some algorithms are pretty straightforward, such as linear search, there are a few that require a bit more thinking to implement. Today, we are going to take a look at one of those algorithms, the N-Queens problem. Although the N-Queens is more of a problem than an algorithm, its solution can be widely used for various real-world problems. So what exactly is the N-Queens problem? Well, the basic premise of the problem is that there is a chessboard of NxN squares, where N is the number of queens present on the chessboard. Our goal is to arrange these 'N' queens in such a way that none of them are directly threatened by any of the other queens on the chessboard.
Let's start at N=1. At this value of N, there exists one queen, and only one chess square, thus eliminating the need to strategically position any of the queens.
Moving forward to N=2, we see that there are two queens, but only four chess squares to place them on. By doing this, we see that the queens are placed adjacent to each other, therefore threatening both the queens.
This trend follows till we come to N = 4. At this value of N, we have enough queens and chess squares(16) to come up with a creative solution to this problem. Now, there are multiple approaches to solving this problem, but the most popular approach has to be backtracking.
But what is backtracking? Backtracking is an approach used to solve many problems. The method basically says that we follow one possible path to finding the solution to our problem, and if the path turns out to be wrong, we retrace our steps to find a new path. We keep repeating this process until we arrive at the correct or most optimal solution to our problem.
Coming back to our original problem, we initially place the queen at any square on the chessboard. Then, we find out all the squares where the queen might pose a threat to the other queens. We then proceed to place the next queen. If the 2nd queen happens to be on one of the squares that were a threat square, we move it to a different square. Once the 2nd queen is placed, we check the new set of threat squares that arise from both the queens. Then we proceed to place the 3rd queen and repeat the same process to find the perfect square for the 3rd queen. We then do the same thing for the 4th queen too. At this point, we should have one solution for our problem. The process of going back to rectify the square to place our queen is backtracking.
We have now obtained one possible solution for the 4-Queens problem, but there exists another solution to this problem. Both of them are illustrated below.
The same can be done for N=5,6,7 and so on. The next most popular instance of this problem comes at N=8. At this point, there are 8 queens and 64 chess squares to arrange the queens in. Using the same backtracking approach we have used in the previous example, we can arrive at multiple solutions where the queens don't threaten each other. There are a total of 92 solutions for the 8-Queens problem.
We can keep creating an infinite number of cases, where N can take any value, but the approach to find the solution for that particular value of N remains the same. N-Queens is a very challenging and complex problem to solve, one which has multiple solutions. Backtracking is one of those approaches that makes it easier for us to figure out the solution for this problem where N can be any value. I hope this helps in understanding the N-Queens problem better and help figure out one of many approaches for this problem.
Top comments (0)