problem Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 Example: Input: 4 Output: [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]
approach1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 class Solution public List<List<String>> solveNQueens(int n) { List<List<String>> res = new ArrayList<>(); helper(res, new int [n], 0 ); return res; } private void helper (List<List<String>> res, int [] queens, int pos) if (pos == queens.length) { addResult(res, queens); return ; } for (int i = 0 ; i < queens.length; i++) { queens[pos] = i; if (isValid(pos, queens)) { helper(res, queens, pos + 1 ); } } } private boolean isValid (int pos, int [] queens) for (int i = 0 ; i < pos; i++) { if (queens[i] == queens[pos]) { return false ; } else if (Math.abs(queens[pos] - queens[i]) == Math.abs(i - pos)) { return false ; } } return true ; } private void addResult (List<List<String>> res, int [] queens) List<String> list = new ArrayList<>(); for (int i = 0 ; i < queens.length; i++) { StringBuilder sb = new StringBuilder(); for (int j = 0 ; j < queens.length; j++) { if (j == queens[i]) { sb.append("Q" ); } else { sb.append("." ); } } list.add(sb.toString()); } res.add(list); } }
approach2 approach3 summery