FilesExpand file tree

 main

/

0051-n-queens.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

126 lines (111 loc) · 3.73 KB

 main

/

0051-n-queens.java

Copy path

Top

File metadata and controls

• Code
• Blame

126 lines (111 loc) · 3.73 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

// Solution 1:

class Solution {

public List<List<String>> solveNQueens(int n) {

List<List<String>> ans = new ArrayList<List<String>>();

boolean[][] board = new boolean[n][n];

queens(board, 0, ans);

return ans;

}

public void queens(boolean[][] board, int row, List<List<String>> ans2) {

//base case

if (row == board.length) {

ArrayList<String> ans = new ArrayList<String>();

createAnswer(board, ans);

ans2.add(ans);

return;

}

for (int col = 0; col < board.length; col++) {

if (isSafe(board, row, col)) {

board[row][col] = true;

queens(board, row + 1, ans2);

board[row][col] = false;

}

}

}

public void createAnswer(boolean[][] board, ArrayList<String> ans) {

for (int i = 0; i < board.length; i++) {

StringBuilder str = new StringBuilder();

for (int j = 0; j < board[0].length; j++) {

if (board[i][j]) {

str.append("Q");

} else str.append(".");

}

ans.add(str.toString());

}

}

public boolean isSafe(boolean[][] board, int row, int col) {

for (int i = 0; i < row; i++) {

if (board[i][col]) {

return false;

}

}

int maxLeft = Math.min(row, col);

for (int i = 1; i <= maxLeft; i++) {

if (board[row - i][col - i]) {

return false;

}

}

int maxRight = Math.min(row, board.length - 1 - col);

for (int i = 1; i <= maxRight; i++) {

if (board[row - i][col + i]) return false;

}

return true;

}

}

// Solution 2:

/*

* This solution uses 3 hashsets to check whether the current queen has conflicts with previous

* columns and two diagonals, avoiding the use of 2D boolean array and the isSafe checking function.

*

*/

class Solution {

public List<List<String>> solveNQueens(int n) {

List<List<String>> result = new ArrayList<>();

List<String> cur = new ArrayList<>();

if (n <= 0) {

return result;

}

Set<Integer> leftSet = new HashSet<>(); // diag \ row - col

Set<Integer> rightSet = new HashSet<>(); // diag / row + col

Set<Integer> colSet = new HashSet<>(); // column | col

dfs(n, result, cur, leftSet, rightSet, colSet);

return result;

}

private void dfs(int n, List<List<String>> result, List<String> cur, Set<Integer> leftSet,

Set<Integer> rightSet, Set<Integer> colSet) {

if (cur.size() == n) {

result.add(new ArrayList(cur));

return;

}

int row = cur.size();

// i is column index

for (int i = 0; i < n; i++) {

if (leftSet.contains(row - i) || rightSet.contains(row + i) || colSet.contains(i)) {

continue;

}

// current col index is added to the solution list cur

cur.add(convert(n, i));

leftSet.add(row - i);

rightSet.add(row + i);

colSet.add(i);

// go to dfs next level

dfs(n, result, cur, leftSet, rightSet, colSet);

// backtracking

cur.remove(cur.size() - 1);

leftSet.remove(row - i);

rightSet.remove(row + i);

colSet.remove(i);

}

}

private String convert(int n, int col) {

StringBuilder res = new StringBuilder();

for (int i = 0; i < n; i++) {

if (i == col) {

res.append("Q");

} else {

res.append(".");

}

}

return res.toString();

}

}