Scribd
Upload
8 views2 pages

N Queens Java Program - Backtracking

The document contains a Java implementation of the N-Queens problem, which involves placing N queens on an N x N chessboard such that no two queens threaten each other. It includes methods for checking if a position is safe for a queen, backtracking to find a solution, and printing the board configuration. The main method allows for solving the problem for a specified value of N, defaulting to 8.

Uploaded by

rachi.website
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
8 views2 pages

N Queens Java Program - Backtracking

The document contains a Java implementation of the N-Queens problem, which involves placing N queens on an N x N chessboard such that no two queens threaten each other. It includes methods for checking if a position is safe for a queen, backtracking to find a solution, and printing the board configuration. The main method allows for solving the problem for a specified value of N, defaulting to 8.

Uploaded by

rachi.website
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 2

public class NQueens {

// Method to print the solution


static void printSolution(int board[][], int N) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(board[i][j] == 1 ? "Q " : ". ");
}
System.out.println();
}
}

// Method to check if a queen can be placed on board[row][col]


static boolean isSafe(int board[][], int row, int col, int N) {
// Check the column
for (int i = 0; i < row; i++) {
if (board[i][col] == 1) {
return false;
}
}

// Check upper-left diagonal


for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 1) {
return false;
}
}

// Check upper-right diagonal


for (int i = row, j = col; i >= 0 && j < N; i--, j++) {
if (board[i][j] == 1) {
return false;
}
}

return true;
}

// Backtracking method to solve the N-Queens problem


static boolean solveNQueensUtil(int board[][], int row, int N) {
// If all queens are placed
if (row == N) {
return true;
}

// Try placing the queen in all columns one by one


for (int col = 0; col < N; col++) {
if (isSafe(board, row, col, N)) {
board[row][col] = 1; // Place the queen

// Recur to place the rest of the queens


if (solveNQueensUtil(board, row + 1, N)) {
return true;
}

// If placing queen in board[row][col] doesn't lead to a solution,


backtrack
board[row][col] = 0;
}
}

return false; // If the queen cannot be placed in any column


}

// Method to solve the N-Queens problem


static boolean solveNQueens(int N) {
int board[][] = new int[N][N];

if (!solveNQueensUtil(board, 0, N)) {
System.out.println("Solution does not exist");
return false;
}

printSolution(board, N);
return true;
}

public static void main(String[] args) {


int N = 8; // You can change this value to solve for different N
solveNQueens(N);
}
}

You might also like