LeetCode51-N皇后
LeetCode51-N皇后 递归加剪枝 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 50 51 52 53 54 55 List<List<String>> res = new ArrayList <>(); public List<List<String>> solveNQueens (int n) { cols = new int [n]; place(0 ); return res; } int [] cols; void place (int row) { if (row == cols.length) { res.add(show()); return ; } for (int col = 0 ; col < cols.length; col++) { if (isValid(row, col)) { cols[row] = col; place(row + 1 ); } } } boolean isValid (int row, int col) { for (int i = 0 ; i < row; i++) { if (cols[i] == col) { return false ; } if (row - i == Math.abs(col - cols[i])) { return false ; } } return true ; } List<String> show () { List<String> list = new ArrayList <>(); for (int row = 0 ; row < cols.length; row++) { StringBuffer buffer = new StringBuffer (); for (int col = 0 ; col < cols.length; col++) { if (cols[row] == col) { buffer.append("Q" ); } else { buffer.append("." ); } } list.add(buffer.toString()); } return list; }
优化 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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 List<List<String>> res = new ArrayList <>(); int [] queens; boolean [] cols; boolean [] leftTop; boolean [] rightTop; public List<List<String>> solveNQueens (int n) { if (n < 1 ) return res; queens = new int [n]; cols = new boolean [n]; leftTop = new boolean [(n << 1 ) - 1 ]; rightTop = new boolean [leftTop.length]; place(0 ); return res; } void place (int row) { if (row == cols.length) { res.add(show()); return ; } for (int col = 0 ; col < cols.length; col++) { if (cols[col]) continue ; int ltIndex = row - col + cols.length - 1 ; if (leftTop[ltIndex]) continue ; int rtIndex = row + col; if (rightTop[rtIndex]) continue ; queens[row] = col; cols[col] = true ; leftTop[ltIndex] = true ; rightTop[rtIndex] = true ; place(row + 1 ); cols[col] = false ; leftTop[ltIndex] = false ; rightTop[rtIndex] = false ; } } List<String> show () { List<String> list = new ArrayList <>(); for (int row = 0 ; row < cols.length; row++) { StringBuffer buffer = new StringBuffer (); for (int col = 0 ; col < cols.length; col++) { if (queens[row] == col) { buffer.append("Q" ); } else { buffer.append("." ); } } list.add(buffer.toString()); } return list; }