-
Notifications
You must be signed in to change notification settings - Fork 2
/
NQueens.java
90 lines (77 loc) · 2.48 KB
/
NQueens.java
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
package Leetcode;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
* @author kalpak
*
* The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
*
* 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.
*
*
* Example 1:
* Input: n = 4
* Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
* Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
*
* Example 2:
* Input: n = 1
* Output: [["Q"]]
*
*
* Constraints:
*
* 1 <= n <= 9
*
*/
public class NQueens {
static List<List<String>> result;
public static List<List<String>> solveNQueens(int n) {
result = new ArrayList<>();
placeQueen(new int[n][n], 0, new HashSet<>(), new HashSet<>(), new HashSet<>());
return result;
}
private static void placeQueen(int[][] board, int i, Set<Integer> diagonal, Set<Integer> antiDiagonal, Set<Integer> vertical) {
if(i == board.length) {
// call the function that adds the strings
addToList(board);
return;
}
for(int j = 0; j < board.length; j++) {
if(!diagonal.contains(i + j) && !antiDiagonal.contains(j - i) && !vertical.contains(j)) {
board[i][j] = 1;
diagonal.add(i + j);
antiDiagonal.add(j - i);
vertical.add(j);
placeQueen(board, i + 1, diagonal, antiDiagonal, vertical);
board[i][j] = 0;
diagonal.remove(i + j);
antiDiagonal.remove(j - i);
vertical.remove(j);
}
}
}
private static void addToList(int[][] board) {
List<String> boardState = new ArrayList<>();
StringBuilder temp;
for(int i = 0; i < board.length; i++) {
temp = new StringBuilder();
for(int j = 0; j < board.length; j++) {
if(board[i][j] == 0)
temp.append(".");
else
temp.append("Q");
}
boardState.add(temp.toString());
}
result.add(boardState);
}
public static void main(String[] args) {
System.out.println(solveNQueens(8));
}
}