N-Queens

1package pkg5leetcode.top100;2 3/*4 * N-Queens | LC 515 * APPROACH: Backtrack place queens row by row checking columns/diagonals.6 * COMPLEXITY: Time O(n!), Space O(n^2)7 */8import java.util.*;9 10public class top100_LC51NQueens {11    static List<List<String>> solveNQueens(int n) {12        List<List<String>> res = new ArrayList<>();13        char[][] board = new char[n][n];14        for (char[] row : board) java.util.Arrays.fill(row, '.');15        backtrack(board, 0, res);16        return res;17    }18 19    static void backtrack(char[][] b, int r, List<List<String>> res) {20        if (r == b.length) {21            List<String> sol = new ArrayList<>();22            for (char[] row : b) sol.add(new String(row));23            res.add(sol);24            return;25        }26        for (int c = 0; c < b.length; c++) {27            if (!ok(b, r, c)) continue;28            b[r][c] = 'Q';29            backtrack(b, r + 1, res);30            b[r][c] = '.';31        }32    }33 34    static boolean ok(char[][] b, int r, int c) {35        for (int i = 0; i < r; i++) if (b[i][c] == 'Q') return false;36        for (int i = r - 1, j = c - 1; i >= 0 && j >= 0; i--, j--)37            if (b[i][j] == 'Q') return false;38        for (int i = r - 1, j = c + 1; i >= 0 && j < b.length; i--, j++)39            if (b[i][j] == 'Q') return false;40        return true;41    }42 43    public static void main(String[] args) {44        check(solveNQueens(4).size() == 2, "case1");45        check(solveNQueens(1).size() == 1, "case2");46        System.out.println("all tests passed");47    }48 49    static void check(boolean cond, String name) {50        if (!cond) throw new AssertionError("FAILED: " + name);51        System.out.println("  PASS " + name);52    }53}