Scribd
Upload
2 views3 pages

Pract 4

The document presents a Java implementation of the N-Queens problem using backtracking, a common constraint satisfaction problem. It includes functions to print the board, check if a queen can be safely placed, and solve the N-Queens puzzle recursively. The main method initializes the board and attempts to find a solution, printing the result accordingly.

Uploaded by

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

Pract 4

The document presents a Java implementation of the N-Queens problem using backtracking, a common constraint satisfaction problem. It includes functions to print the board, check if a queen can be safely placed, and solve the N-Queens puzzle recursively. The main method initializes the board and attempts to find a solution, printing the result accordingly.

Uploaded by

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

// N-Queens Problem using Backtracking (Constraint Satisfaction Problem)

public class NQueens {

static int N = 4;

// Function to print board


static void printBoard(int board[][]) {

for (int i = 0; i < N; i++) {

for (int j = 0; j < N; j++) {

[Link](board[i][j] + " ");


}

[Link]();
}
}

// Check if queen can be placed


static boolean isSafe(int board[][], int row, int col) {

int i, j;

// Check left side row


for (i = 0; i < col; i++) {

if (board[row][i] == 1)
return false;
}

// Check upper diagonal


for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {

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

if (board[i][j] == 1)
return false;
}

return true;
}

// Backtracking function
static boolean solveNQ(int board[][], int col) {

// All queens placed


if (col >= N)
return true;

// Try placing queen in every row


for (int i = 0; i < N; i++) {

if (isSafe(board, i, col)) {

// Place queen
board[i][col] = 1;

// Recursive call
if (solveNQ(board, col + 1))
return true;

// Backtracking
board[i][col] = 0;
}
}

return false;
}
// Main method
public static void main(String[] args) {

int board[][] = new int[N][N];

if (solveNQ(board, 0)) {

[Link]("Solution Exists:");

printBoard(board);

} else {

[Link]("No Solution");
}
}
}

You might also like