The N-Queens problem is a classic problem in computer science and mathematics, particularly in the field of combinatorial optimization and artificial intelligence. The problem is defined as follows:
code:
public class nQueen {
public static boolean isSafe(char chessBoard[][], int row, int col) {
// for check vertical
for (int i = row - 1; i >= 0; i--) {
if (chessBoard[i][col] == 'Q') {
return false;
}
}
// for heck up left diagonal
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (chessBoard[i][j] == 'Q') {
return false;
}
}
// for check down left diagonal
for (int i = row - 1, j = col + 1; i >= 0 && j < chessBoard.length; i--, j++) {
if (chessBoard[i][j] == 'Q') {
return false;
}
}
return true;
}
public static void nQueens(char chessBoard[][], int row) {
if (row == chessBoard.length) {
displayBoard(chessBoard);
countWays++;
return;
}
for (int j = 0; j < chessBoard.length; j++) {
if (isSafe(chessBoard, row, j)) {
chessBoard[row][j] = 'Q';
nQueens(chessBoard, row + 1);
chessBoard[row][j] = 'X';
}
}
}
public static void displayBoard(char chessBoard[][]) {
System.out.println("------------------");
for (int i = 0; i < chessBoard.length; i++) {
for (int j = 0; j < chessBoard.length; j++) {
System.out.print(chessBoard[i][j] + " ");
}
System.err.println();
}
}
static int countWays = 0;
public static void main(String[] args) {
int n = 4;
char chessBoard[][] = new char[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
chessBoard[i][j] = 'X';
}
}
nQueens(chessBoard, 0);
System.out.println("Total Count of Ways for Solution: " + countWays);
}
}
output:
------------------
X Q X X
X X X Q
Q X X X
X X Q X
------------------
X X Q X
Q X X X
X X X Q
X Q X X
Total Count of Ways for Solution: 2
Given an N×N chessboard, the task is to place N queens on the board in such a way that no two queens threaten each other. In chess, a queen can attack any piece horizontally, vertically, or diagonally along any number of squares.
The objective is to find all possible arrangements of N queens on the board such that no two queens threaten each other. In other words, there should be no two queens in the same row, column, or diagonal.
The problem is challenging due to its exponential nature. As the board size (N) increases, the number of possible arrangements grows very rapidly, making it computationally intensive to find solutions.
More Solution:
No comments: