What is the 8 Queens Problem in C++?
The n-queens’ or 8 queens’ problem refers to the situation in which you want to place the given number of queens on a chessboard in a way that no queen can be attacked by another vertically, horizontally, or diagonally, i.e., all the queens should be positioned so intelligently that none of them can be attacked by the other in any way.
How to Solve the 8 Queens Problem in C++ in Ubuntu 20.04?
In this segment, we will share with you the procedure of solving the 8 queens’ problem in C++. For achieving this objective, we have designed a C++ code shown in the image below. However, before proceeding with explaining this code, we would like to share with you that we have broken down this code into small snippets for your easy understanding. We have roughly divided this C++ program into a function for printing all the different states of the chessboard that satisfy the solution of the 8 queens’ problem, a function for checking whether a particular position is safe for placing the queen or not, a function for solving the 8 queens’ problem using the backtracking algorithm, and finally, the main driver function. We will be discussing all of these snippets one by one.
In the first snippet of our code, after including the library and namespace, we have defined a chessboard of size 10 x 10 in the form of a 2D array. It means that our program will be capable of taking 10 queens’ at maximum for solving the n-queens’ problem in C++. However, in this article, we are mainly concerned with the 8 queens’ problem. After defining the chessboard, we have our “PrintBoard” function that takes an integer “n” as input which refers to the number of queens, i.e., 8 in this particular case. Within this function, we have a nested “for” loop to simply print the chessboard on the terminal every time this function is called. Then, we have some “cout” statements for printing adequate spaces between the different states of the solved chessboard.
In the second snippet of our C++ code, we have the “isSafe” function that is there to check whether it will be safe to place a queen at a particular position or not. By “safe” we mean that no other queen can attack a particular queen vertically, horizontally, or diagonally. Then, we have three independent “for” loops within this function that are there to verify all the three conditions separately. If any of these conditions become true, then the “isSafe” function will return “false” because in these cases, there will always be a chance of attack, because of which we will not be able to place a queen at the particular position. However, if all of these conditions become false, i.e., there is no chance of attack at that position vertically, horizontally, or diagonally, only then the “isSafe” function will return “true” i.e., it will be safe to place a queen at the particular position.
In the third snippet of our C++ code, we have the “Solution” function that will devise the solution of the n-queens’ problem by using the backtracking algorithm. Within this function, the first “if” statement is used to check whether the queen number is equal to the total number of queens or not. If this statement evaluates to be true, then the “PrintBoard” function will instantly be called. Otherwise, a Boolean variable “result” will be defined whose initial state is kept “false”. Then, we have another “for” loop within which we iteratively call the “isSafe” function for each of the queens to find out if the given position is safe for placing it or not. Within this condition, we have used recursion to perform the backtracking for placing the queens at the safest positions so that they cannot be attacked by any other queen. Here, “1” will represent that a queen is placed at a particular position, whereas “0” will represent all the empty positions of the chessboard. Finally, we have returned the “result” variable to notify whether the solution to the given number of queens is possible or not.
In the last snippet of our C++ code, we have the main driver function. The reason behind using the first two statements within our “main()” function is performance optimization because, for a larger number of queens, your program might execute unreasonably slower. However, you can skip these if you wish so. Then, we have defined an integer “n” that corresponds to the number of queens. After that, we have displayed a message on the terminal to prompt the user to enter the number of queens for which he/she wants to solve the n-queens’ problem. Then, we have simply acquired this as input from the user. After that, we have a nested “for” loop in which we have called the “ChessBoard” function. Then, we have called the “Solution” function and stored its output in the “result” variable. If the value of the “result” variable will be “false” then, it will mean that no solution exists for the given number of queens. At last, we have the “return 0” statement for wrapping up our code.
To compile this code, we have used the following command:
To run this code, we have used the command appended below:
We were first asked to enter the number of queens as shown in the following image:
We have entered “8” for our particular case, as shown in the image below:
As soon as you provide the number of queens, all the possible solutions to the 8 queens’ problem will appear on the terminal as shown in the following image:
To test this code for the other case, i.e., the solution does not exist, we have provided “3” as the number of queens. This is shown in the image below:
We understand that for a 3 x 3 chessboard, no solution exists; that is why we received the following output:
Conclusion
This article was all about the 8 queens’ problem in C++ in Ubuntu 20.04. We explained to you briefly about this problem and all the conditions that must be satisfied to solve this problem. After that, we shared with you a full-fledged C++ program that will solve this problem for you for 8 queens or at max 10 queens. Moreover, we also tested this code for a case where the solution to this problem is impossible. Hopefully, after reading through this guide, you will get a good understanding of the famous 8 queens’ problem in C++.
from https://ift.tt/3yaJGSZ
0 Comments