How to resolve the algorithm Peaceful chess queen armies step by step in the Java programming language
How to resolve the algorithm Peaceful chess queen armies step by step in the Java 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 Java programming language
Java Code Analysis
The provided Java code is designed to solve a problem known as "Peaceful Queens." The goal is to place a number of black and an equal number of white queens on an n x n chessboard such that no two queens are attacking each other.
Key Concepts
-
Chessboard and Queens: The chessboard is represented as a 2D array of
Pieceenum values:Empty,Black, orWhite. Queens are placed on the chessboard in specific positions. -
Attacking Queens: Queens attack each other if they are on the same row, column, or diagonal.
-
Backtracking: The algorithm uses a backtracking approach to explore possible queen placements. It starts by placing a black queen and then recursively places white queens. If a solution is not found, it backtracks and tries a different black queen placement.
Code Structure
The code is organized into the following classes and methods:
1. PeaceFul Class
- Enum Piece: Defines the three possible piece types: empty, black, and white.
- Class Position: Represents a position on the chessboard.
- Method place: This is the main recursive method that attempts to place m black and m white queens on an
n x nchessboard. - Method isAttacking: Checks if two queens at given positions are attacking each other.
- Method printBoard: Prints the chessboard with the placed queens.
2. Main Method
- Creates a list of test cases with different numbers of queens and board sizes.
- For each test case:
- Calls the
placemethod to try placing queens. - If a solution is found, it prints the solution chessboard.
- Otherwise, it prints a message indicating no solution was found.
- Calls the
Algorithm
The place method uses a recursive backtracking algorithm to explore possible queen placements. It starts by placing a black queen and then recursively tries all possible positions for white queens. If a valid placement is found, it places the next black queen and continues the recursion. If a position results in an attacking queen, it backtracks and tries a different position for the previous black queen.
Board Representation
The chessboard is represented as a 1D array of Piece enum values. The index of an element in the array corresponds to a position on the chessboard.
Output
The output displays the chessboard with the placed black and white queens. For example, the output for the first test case (2 black and 2 white queens on a 4 x 4 board) is:
2 black and 2 white queens on a 4 x 4 board:
• B • • •
• W • • ◦
◦ • • B ◦
◦ • W • •
Summary
The provided Java code solves the Peaceful Queens problem using a recursive backtracking algorithm. It efficiently places queens on a chessboard such that they don't attack each other. The code demonstrates the concepts of backtracking, chessboard representation, and queen attacking rules.
Source code in the java programming language
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Peaceful {
enum Piece {
Empty,
Black,
White,
}
public static class Position {
public int x, y;
public Position(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object obj) {
if (obj instanceof Position) {
Position pos = (Position) obj;
return pos.x == x && pos.y == y;
}
return false;
}
}
private static boolean place(int m, int n, List<Position> pBlackQueens, List<Position> pWhiteQueens) {
if (m == 0) {
return true;
}
boolean placingBlack = true;
for (int i = 0; i < n; ++i) {
inner:
for (int j = 0; j < n; ++j) {
Position pos = new Position(i, j);
for (Position queen : pBlackQueens) {
if (pos.equals(queen) || !placingBlack && isAttacking(queen, pos)) {
continue inner;
}
}
for (Position queen : pWhiteQueens) {
if (pos.equals(queen) || placingBlack && isAttacking(queen, pos)) {
continue inner;
}
}
if (placingBlack) {
pBlackQueens.add(pos);
placingBlack = false;
} else {
pWhiteQueens.add(pos);
if (place(m - 1, n, pBlackQueens, pWhiteQueens)) {
return true;
}
pBlackQueens.remove(pBlackQueens.size() - 1);
pWhiteQueens.remove(pWhiteQueens.size() - 1);
placingBlack = true;
}
}
}
if (!placingBlack) {
pBlackQueens.remove(pBlackQueens.size() - 1);
}
return false;
}
private static boolean isAttacking(Position queen, Position pos) {
return queen.x == pos.x
|| queen.y == pos.y
|| Math.abs(queen.x - pos.x) == Math.abs(queen.y - pos.y);
}
private static void printBoard(int n, List<Position> blackQueens, List<Position> whiteQueens) {
Piece[] board = new Piece[n * n];
Arrays.fill(board, Piece.Empty);
for (Position queen : blackQueens) {
board[queen.x + n * queen.y] = Piece.Black;
}
for (Position queen : whiteQueens) {
board[queen.x + n * queen.y] = Piece.White;
}
for (int i = 0; i < board.length; ++i) {
if ((i != 0) && i % n == 0) {
System.out.println();
}
Piece b = board[i];
if (b == Piece.Black) {
System.out.print("B ");
} else if (b == Piece.White) {
System.out.print("W ");
} else {
int j = i / n;
int k = i - j * n;
if (j % 2 == k % 2) {
System.out.print("• ");
} else {
System.out.print("◦ ");
}
}
}
System.out.println('\n');
}
public static void main(String[] args) {
List<Position> nms = List.of(
new Position(2, 1),
new Position(3, 1),
new Position(3, 2),
new Position(4, 1),
new Position(4, 2),
new Position(4, 3),
new Position(5, 1),
new Position(5, 2),
new Position(5, 3),
new Position(5, 4),
new Position(5, 5),
new Position(6, 1),
new Position(6, 2),
new Position(6, 3),
new Position(6, 4),
new Position(6, 5),
new Position(6, 6),
new Position(7, 1),
new Position(7, 2),
new Position(7, 3),
new Position(7, 4),
new Position(7, 5),
new Position(7, 6),
new Position(7, 7)
);
for (Position nm : nms) {
int m = nm.y;
int n = nm.x;
System.out.printf("%d black and %d white queens on a %d x %d board:\n", m, m, n, n);
List<Position> blackQueens = new ArrayList<>();
List<Position> whiteQueens = new ArrayList<>();
if (place(m, n, blackQueens, whiteQueens)) {
printBoard(n, blackQueens, whiteQueens);
} else {
System.out.println("No solution exists.\n");
}
}
}
}
You may also check:How to resolve the algorithm Arithmetic/Rational step by step in the Phix programming language
You may also check:How to resolve the algorithm Closest-pair problem step by step in the Raku programming language
You may also check:How to resolve the algorithm Temperature conversion step by step in the C# programming language
You may also check:How to resolve the algorithm Sieve of Eratosthenes step by step in the Fōrmulæ programming language
You may also check:How to resolve the algorithm CSV data manipulation step by step in the BaCon programming language