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
|
private boolean[] column; private boolean[] diagonal1; private boolean[] diagonal2;
public List<List<String>> solveNQueens(int n) { List<List<String>> result = new ArrayList<>(); column = new boolean[n]; diagonal1 = new boolean[2 * n - 1]; diagonal2 = new boolean[2 * n - 1]; char[][] board = new char[n][n];
for (int i = 0; i < n; i++) Arrays.fill(board[i], '.');
helper(result, board, n, 0); return result; }
private void (List<List<String>> result, char[][] board, int n, int x) { if (x == n) { List<String> list = new ArrayList<>();
for (char[] row : board) list.add(new String(row));
result.add(list); return; }
for (int y = 0; y < n; y++) { if (!isValid(n, x, y)) continue;
update(board, n, x, y, true); helper(result, board, n, x + 1); update(board, n, x, y, false); } }
private boolean isValid(int n, int x, int y) { return !column[y] && !diagonal1[x + y] && !diagonal2[y - x + n - 1]; }
private void update(char[][] board, int n, int x, int y, boolean put) { column[y] = put; diagonal1[x + y] = put; diagonal2[y - x + n - 1] = put; board[x][y] = put ? 'Q' : '.'; }
|
近期评论