Untitled

mail@pastecode.io avatar
unknown
java
a year ago
1.1 kB
1
Indexable
Never
public static void placeQueens(int row, boolean[][] positions, List<boolean[][]> results) {
    int N = positions.length;
    if (row == N) {
        results.add(positions.clone());
    } else {
        for (int col = 0; col < N; col++) {
            if (isSafe(row, col, positions)) {
                positions[row][col] = true;
                placeQueens(row + 1, positions, results);
                positions[row][col] = false;
            }
        }
    }
}

public static boolean isSafe(int row, int col, boolean[][] positions) {
    int N = positions.length;
    // Check this row on left side
    for (int c = 0; c < col; c++) {
        if (positions[row][c]) {
            return false;
        }
    }
    // Check upper diagonal on left side
    for (int r = row, c = col; r >= 0 && c >= 0; r--, c--) {
        if (positions[r][c]) {
            return false;
        }
    }
    // Check lower diagonal on left side
    for (int r = row, c = col; r < N && c >= 0; r++, c--) {
        if (positions[r][c]) {
            return false;
        }
    }
    return true;
}