51. N-Queens
Last updated
Last updated
/**
* Time complexity : O(N!). There is N possibilities to put the first queen,
* not more than N (N - 2) to put the second one, not more than N(N-2)(N-4)
* for the third one etc. In total that results in O(N!) time complexity.
* Space complexity : O(N) to keep an information about diagonals and rows.
*/
class Solution {
private Set<Integer> col = new HashSet<>();
private Set<Integer> hill = new HashSet<>();
private Set<Integer> dale = new HashSet<>();
public List<List<String>> solveNQueens(int n) {
List<List<String>> resultList = new ArrayList<>();
backtrack(resultList, new ArrayList<String>(), 0, n);
return resultList;
}
private void backtrack(List<List<String>> resultList,
List<String> currList,
int row,
int n) {
if(row == n) {
resultList.add(new ArrayList(currList));
return;
}
for(int i = 0; i < n; i++) {
if(col.contains(i) ||
hill.contains(row+i) ||
dale.contains(row-i)) {
continue;
}
char[] rowArr = new char[n];
Arrays.fill(rowArr, '.');
rowArr[i] = 'Q';
String rowStr = new String(rowArr);
currList.add(rowStr);
col.add(i);
hill.add(row+i);
dale.add(row-i);
backtrack(resultList, currList, row+1, n);
currList.remove(currList.size()-1);
col.remove(i);
hill.remove(row+i);
dale.remove(row-i);
}
}
}/**
* Time complexity :
* Space complexity :
*/
class Solution {
private boolean[] cols;
private boolean[] hills;
private boolean[] dales;
public List<List<String>> solveNQueens(int n) {
List<List<String>> resultList = new ArrayList<>();
if(n == 0) resultList.add(new ArrayList<>());
if(n == 1) resultList.add(List.of("Q"));
if(n > 3) {
cols = new boolean[n];
hills = new boolean[n*2 - 1];
dales = new boolean[n*2 - 1];
char[][] board = new char[n][n];
for(char[] arr: board) {
Arrays.fill(arr, '.');
}
backtrack(resultList, board, 0, n);
}
return resultList;
}
private void backtrack(List<List<String>> resultList,
char[][] board,
int row,
int n) {
if(row == n) {
ArrayList<String> tempList = new ArrayList();
for(char[] arr: board) {
tempList.add(new String(arr));
}
resultList.add(tempList);
return;
}
for(int col = 0; col < n; col++) {
if(cols[col] || hills[row+col] || dales[row-col+n-1]) {
continue;
}
board[row][col] = 'Q';
cols[col] = true;
hills[row+col] = true;
dales[row-col+n-1] = true;
backtrack(resultList, board, row+1, n);
board[row][col] = '.';
cols[col] = false;
hills[row+col] = false;
dales[row-col+n-1] = false;
}
}
}