Leetcode: N Queens
This question is asked at Amazon, Facebook, Microsoft, Tiktok, and Apple.
It is the following:
The n-queens puzzle is the problem of placing n queens on an nxn chessboard such that no two queens attack each other, and I want to return all distinct solutions to an n queens puzzle.
Now the first question is how we are going to enumerate this. This is with an array of nxn rows and a queen in a column square of each array row. These are 2 solutions to this particular puzzle:
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
The other example is if n = 1 then the solution is just a queen placed on an 1x1 square:
Input: n = 1
Output: [["Q"]]
This uses a backtracking algorithm, and the explanation is as follows:
Initially, we try to use a brute force optimization, and since there are N ways to place N queens, there are N^N possible locations which gets big fast. For example, in an 8x8 chessboard there are 16,777,216 possible test solutions.
To optimize this, we can perform constrained programming which in lieu means to put restrictions after each queen placement, and restricts certain combinations after placing the queen on a particular spot on the board.
The second option is backtracking. If we can't find an optimal combination we backtrack and change positions of the previous queen.
So here are some rules:
There can only be one queen for each row, and one queen for each column. We can just iterate through the columns on the board to get the diagonals, which will add up to a constant.
Now we can write the backtracking algorithm, which starts from the first row, and iterate through each column placing each queen on a square and excluding one row one column from further consideration. If all rows are filled out, then add the solution, otherwise backtrack and remove the queen from the square and try another solution.
class Solution {
int rows[];
int hills[];
int dales[];
int n;
List<List<String>> output = new ArrayList();
int queens[];
public boolean isNotUnderAttack(int row, int col) {
int res = rows[col] + hills[row - col + 2 * n] + dales[row + col];
return (res == 0) ? true : false;
}
public void placeQueen(int row, int col) {
queens[row] = col;
rows[col] = 1;
hills[row - col + 2 * n] = 1;
dales[row + col] = 1;
}
public void removeQueen(int row, int col) {
queens[row] = 0;
rows[col] = 0;
hills[row - col + 2 * n] = 0;
dales[row + col] = 0;
}
public void addSolution() {
List<String> solution = new ArrayList<String>();
for (int i = 0; i < n; ++i) {
int col = queens[i];
StringBuilder sb = new StringBuilder();
for(int j = 0; j < col; ++j) sb.append(".");
sb.append("Q");
for(int j = 0; j < n - col - 1; ++j) sb.append(".");
solution.add(sb.toString());
}
output.add(solution);
}
public void backtrack(int row) {
for (int col = 0; col < n; col++) {
if (isNotUnderAttack(row, col)) {
placeQueen(row, col);
if (row + 1 == n) addSolution();
else backtrack(row + 1);
removeQueen(row, col);
}
}
}
public List<List<String>> solveNQueens(int n) {
this.n = n;
rows = new int[n];
hills = new int[4 * n - 1];
dales = new int[2 * n - 1];
queens = new int[n];
backtrack(0);
return output;
}
}
Now the part that many people are confused about is the hills and dales, so I think I will attempt another solution.
Someone attempted to yield a Java solution that claims to be intuitive and easy to understand, using an nxn board, and while this slightly increases complexity, it's a lot better for users to work with, especially in workplaces.
It runs depth first search on the boards, which you can technically say that backtracking is a form of dfs.
This adds the board when the board length is full and for every row, attempt to add a queen in the board and iterate if the queen is able to be added onto the board.
There must be no conflict in the rows, no conflict in the columns and no conflict in the diagonals. If we have a column interference, then there is a queen, but we don't have to check that since we are iterating up to the column. If there is a queen on the same row which means that x == i then we have an interference. The diagonal part is more interesting. If x + y = i + j means for a greater x there is a lesser y and vice versa which indicates the diagonal moving from the top left to the bottom right. x + j = y + i means that for every point, x - y = i - j which means if x > i, y > j, which goes from the top right to the bottom left.
Here are the equations
if x > i then y > j so x + j = y + i
if x < i, y < j so x + j = y + i
if x > i, y < j so x + y = i + j
if x < i, y > j so x + y = i + j and everything from x and y moves the same magnitude units, which is evidenced by the equivalent expression.
and finally, now that we have everything understood, here's the final code:
public class Solution {
public List<List<String>> solveNQueens(int n) {
char[][] board = new char[n][n];
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
board[i][j] = '.';
List<List<String>> res = new ArrayList<List<String>>();
dfs(board, 0, res);
return res;
}
private void dfs(char[][] board, int colIndex, List<List<String>> res) {
if(colIndex == board.length) {
res.add(construct(board));
return;
}
//dfs is kind of backtracking here.
for(int i = 0; i < board.length; i++){
if(validate(board, i, colIndex)){
board[i][colIndex] = 'Q';
dfs(board, colIndex + 1, res);
board[i][colIndex] = '.';
}
}
}
private boolean validate(char[][] board, int x, int y){
for(int i = 0; i < board.length; i++){
for(int j = 0; j < y; j++) {
if(board[i][j] == 'Q' && (x + j == y + i || x + y == i + j || x == i) return false;
}
}
return true;
}
private List<String> construct(char[][] board){
List<String> res = new LinkedList<String>();
for(int i = 0; i < board.length; i++){
String s = new String(board[i]);
res.add(s);
}
return res;
}
}
Comments
Post a Comment