How to resolve the algorithm Peaceful chess queen armies step by step in the C++ programming language
How to resolve the algorithm Peaceful chess queen armies step by step in the C++ programming language
Table of Contents
Problem Statement
In chess, a queen attacks positions from where it is, in straight lines up-down and left-right as well as on both its diagonals. It attacks only pieces not of its own colour.
The goal of Peaceful chess queen armies is to arrange m black queens and m white queens on an n-by-n square grid, (the board), so that no queen attacks another of a different colour.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Peaceful chess queen armies step by step in the C++ programming language
The provided C++ code is a backtracking algorithm that attempts to solve the n-queens problem for different board sizes and numbers of queens. The n-queens problem involves placing n queens on an n x n chessboard such that they do not attack each other. Queens attack each other if they are on the same row, column, or diagonal.
The solution uses the backtracking approach, starting with an empty board and iteratively trying out various positions for the queens. It maintains two vectors, blackQueens and whiteQueens, to keep track of the positions of the black and white queens, respectively.
The core logic is contained in the place function, which returns a boolean indicating whether a valid configuration was found for the given number of queens. The function takes several parameters:
m: The remaining number of queens to place.n: The size of the chessboard.pBlackQueens: A reference to the vector of black queen positions.pWhiteQueens: A reference to the vector of white queen positions.
The place function uses a nested loop to iterate through all possible positions on the board. For each position, it checks if any existing queen (either black or white) is attacking it or if it is attacking any existing queen. If there are no conflicts, the function adds the new queen to the corresponding vector (blackQueens or whiteQueens) and sets the placingBlack flag to false to indicate that the next queen should be white.
After placing a new queen, the function recursively calls place with m - 1 to try out all possible positions for the next queen. If a valid configuration is found, it returns true. Otherwise, it backtracks by removing the last queen and restoring the placingBlack flag to true.
The main function calls the place function for a range of board sizes and numbers of queens, and prints the resulting board configurations. If a valid configuration cannot be found for a given set of parameters, it prints a message indicating that no solution exists.
Overall, the code provides an efficient solution to the n-queens problem. It iteratively explores all possible queen placements using backtracking and outputs the resulting board configurations if a valid solution is found.
Source code in the cpp programming language
#include <iostream>
#include <vector>
enum class Piece {
empty,
black,
white
};
typedef std::pair<int, int> position;
bool isAttacking(const position &queen, const position &pos) {
return queen.first == pos.first
|| queen.second == pos.second
|| abs(queen.first - pos.first) == abs(queen.second - pos.second);
}
bool place(const int m, const int n, std::vector<position> &pBlackQueens, std::vector<position> &pWhiteQueens) {
if (m == 0) {
return true;
}
bool placingBlack = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
auto pos = std::make_pair(i, j);
for (auto queen : pBlackQueens) {
if (queen == pos || !placingBlack && isAttacking(queen, pos)) {
goto inner;
}
}
for (auto queen : pWhiteQueens) {
if (queen == pos || placingBlack && isAttacking(queen, pos)) {
goto inner;
}
}
if (placingBlack) {
pBlackQueens.push_back(pos);
placingBlack = false;
} else {
pWhiteQueens.push_back(pos);
if (place(m - 1, n, pBlackQueens, pWhiteQueens)) {
return true;
}
pBlackQueens.pop_back();
pWhiteQueens.pop_back();
placingBlack = true;
}
inner: {}
}
}
if (!placingBlack) {
pBlackQueens.pop_back();
}
return false;
}
void printBoard(int n, const std::vector<position> &blackQueens, const std::vector<position> &whiteQueens) {
std::vector<Piece> board(n * n);
std::fill(board.begin(), board.end(), Piece::empty);
for (auto &queen : blackQueens) {
board[queen.first * n + queen.second] = Piece::black;
}
for (auto &queen : whiteQueens) {
board[queen.first * n + queen.second] = Piece::white;
}
for (size_t i = 0; i < board.size(); ++i) {
if (i != 0 && i % n == 0) {
std::cout << '\n';
}
switch (board[i]) {
case Piece::black:
std::cout << "B ";
break;
case Piece::white:
std::cout << "W ";
break;
case Piece::empty:
default:
int j = i / n;
int k = i - j * n;
if (j % 2 == k % 2) {
std::cout << "x ";
} else {
std::cout << "* ";
}
break;
}
}
std::cout << "\n\n";
}
int main() {
std::vector<position> nms = {
{2, 1}, {3, 1}, {3, 2}, {4, 1}, {4, 2}, {4, 3},
{5, 1}, {5, 2}, {5, 3}, {5, 4}, {5, 5},
{6, 1}, {6, 2}, {6, 3}, {6, 4}, {6, 5}, {6, 6},
{7, 1}, {7, 2}, {7, 3}, {7, 4}, {7, 5}, {7, 6}, {7, 7},
};
for (auto nm : nms) {
std::cout << nm.second << " black and " << nm.second << " white queens on a " << nm.first << " x " << nm.first << " board:\n";
std::vector<position> blackQueens, whiteQueens;
if (place(nm.second, nm.first, blackQueens, whiteQueens)) {
printBoard(nm.first, blackQueens, whiteQueens);
} else {
std::cout << "No solution exists.\n\n";
}
}
return 0;
}
You may also check:How to resolve the algorithm Time a function step by step in the True BASIC programming language
You may also check:How to resolve the algorithm Repeat step by step in the AppleScript programming language
You may also check:How to resolve the algorithm Totient function step by step in the S-BASIC programming language
You may also check:How to resolve the algorithm Sequence of non-squares step by step in the MATLAB programming language
You may also check:How to resolve the algorithm Stack traces step by step in the Wren programming language