8 Queens Problem in C
Placing eight queens on a normal 8x8 chessboard so that no two queens threaten each other is known as the "Eight Queens Problem," a classic chess puzzle. Finding an arrangement where neither queens are in the same row, column, or diagonally. This implies that every queen needs to be able to see well in every direction without having to pass any other queens.
Since Max Bezzel first posed and resolved the issue in 1848, it has grown in popularity among computer science and machine learning professionals. Algorithmic and programming classes sometimes utilize the Eight Queens Problem to illustrate a constraint satisfaction problem.
To solve the Eight Queens Problem, each queen's placement must be carefully thought out to prevent attacks on one another. It's a classic example of how to solve problems, create algorithms, and apply restrictions to arrive at a workable solution. The Eight Queens task has several solutions, but only one is easy to identify, and it's a fun computational task to find all the solutions.
Explanation:
- The 8 Queen problem, which entails setting up 8 queens on a chessboard so that no two queens may threaten each other, is solved by this pseudocode using a backtracking method.
- The method begins by inserting a queen into the first column. It then moves on to the second column and inserts a queen into its first safe row.
- The algorithm prints the game board and answers true if it reaches the eighth column and all the queens are positioned safely.
- The algorithm returns to the previous column and attempts a different row if it cannot position a queen in a secure location in that column.
- By determining whether there are any queens in the same row, diagonal, or anti-diagonal, the "safe" function determines whether it is safe to place a queen on a given row and column.
- It's important to remember that this is merely a high-level pseudocode and that, depending on your particular implementation and language, it could need to be modified.
Example Code:
#include <stdio.h>
#include <stdbool.h>
#define M 8
void printBoard(int board[M][M]) {
for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) {
printf("%d ", board[i][j]);
}
printf("\n");
}
}
bool isSafe(int board[M][M], int row, int col) {
for (int i = 0; i < col; i++) {
if (board[row][i])
return false;
}
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j])
return false;
}
for (int i = row, j = col; i < M && j >= 0; i++, j--) {
if (board[i][j])
return false;
}
return true;
}
bool solveMQueens(int board[M][M], int col) {
if (col >= M)
return true;
for (int i = 0; i < M; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveMQueens(board, col + 1))
return true;
board[i][col] = 0;
}
}
return false;
}
int main() {
int board[M][M] = {0};
if (solveMQueens(board, 0)) {
printf("Solution exists:\n");
printBoard(board);
} else {
printf("Solution doesn't exist.\n");
}
return 0;
}
Output:
important elements of the Eight Queens Problem used in C
- Definition of the Problem:
Placing eight monarchs on an 8 × 8 chessboard is the aim.
It is forbidden for two queens to be in a single row, column, or diagonal since they shouldn't pose a threat to one another.
- Board Participation:
The chessboard can be written as a 2D array in the code, board[N][N], where N is the board's size, 8 by 8.
- Print Board Features:
The location of queens on the chessboard can be shown using the function printBoard.
- The function of Safety Check:
Use the safe function to determine if it is safe to move a queen to a specific location on the chessboard. It confirms that the new placement is not dangerous to any other queens.
- Return Path Algorithm:
A recursive backtrack algorithm (solveNQueens) is used to find the solution.
The algorithm looks at every placement option, returns when it finds a conflict and keeps going until it finds a workable solution or runs out of options.
- Principal Role:
The solver function is called by the main function, which also initializes the chessboard.
It displays the board if an answer is found; if not, it shows that none is possible.
- Output of the Solution:
The application prints the final queen location on the chessboard if there is a solution.
The software informs that there isn't a solution if one cannot be identified.