Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
2.0 kB
2
Indexable
Never
import java.util.Scanner;

public class NQueensProblem {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the number of queens (N): ");
        int n = scanner.nextInt();

        int[] queens = new int[n];

        if (solveNQueens(queens, 0)) {
            System.out.println("Solution found:");
            printBoard(queens);
        } else {
            System.out.println("No solution exists.");
        }
    }

    private static boolean solveNQueens(int[] queens, int row) {
        if (row == queens.length) {
            return true; // All queens are placed successfully
        }

        for (int col = 0; col < queens.length; col++) {
            if (isValid(queens, row, col)) {
                queens[row] = col; // Place queen in the current cell

                // Recursively solve for the next row
                if (solveNQueens(queens, row + 1)) {
                    return true;
                }

                // Backtrack if the current placement doesn't lead to a solution
                queens[row] = -1;
            }
        }

        return false; // No valid placement for the current row
    }

    private static boolean isValid(int[] queens, int row, int col) {
        // Check if placing a queen in the current cell is valid
        for (int i = 0; i < row; i++) {
            if (queens[i] == col || queens[i] - i == col - row || queens[i] + i == col + row) {
                return false;
            }
        }

        return true;
    }

    private static void printBoard(int[] queens) {
        for (int i = 0; i < queens.length; i++) {
            for (int j = 0; j < queens.length; j++) {
                if (queens[i] == j) {
                    System.out.print("Q ");
                } else {
                    System.out.print(". ");
                }
            }
            System.out.println();
        }
    }
}
Leave a Comment