Problem
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. (link)
Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
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
Solution
Brute force Approach
To place N queens on a nxn matrix such that no queen attacks another, 2 conditions must be met
Each column must contain exactly one queen
Each row must contain exactly one queen
We place the queens column by column. Starting with the first column, we find a safe row to place the queen. Before placing the queen, we check if the position is safe. Once placed, we move to the next column and repeat the process. After exploring all possibilities, we backtrack by removing the queen and trying the next row.
Checking for a safe placement:
When filling column-wise, we ensure safety by checking three conditions:
The row should not already have a queen (check to the left).
The upper diagonal should not already have a queen (check to the left).
The lower diagonal should not already have a queen (check to the left).
If all these checks pass, it is safe to place the queen.
Using Characters
class Solution {
public void findAll(List<List<String>> ans, char[][] matrix, int col){
if(col==matrix.length){
ans.add(new ArrayList<>(convertCharToString(matrix)));
return;
}
for(int i=0; i<matrix.length; i++){
if(isSafe(matrix, i,col)){
matrix[i][col] = 'Q';
findAll(ans, matrix, col+1);
matrix[i][col] = '.';
}
}
}
public boolean isSafe(char[][] matrix, int row, int col){
int i = 0;
int j =0;
//Left Row check
j = col;
while(j>=0){
if(matrix[row][j]=='Q') return false;
j-=1;
}
//Left Upper Diagonal Check
i = row;
j = col;
while(i>=0 && j>=0){
if(matrix[i][j]=='Q') return false;
i-=1;
j-=1;
}
//Left Lower Diagonal Check
i = row;
j = col;
while(i<matrix.length && j>=0){
if(matrix[i][j]=='Q') return false;
i+=1;
j-=1;
}
return true;
}
public List<String> convertCharToString(char[][] matrix){
List<String> listMatrix = new ArrayList<>();
for(int i=0; i<matrix.length; i++){
String row = "";
for(int j=0; j<matrix.length; j++){
row+=matrix[i][j];
}
listMatrix.add(row);
}
return listMatrix;
}
public List<List<String>> solveNQueens(int n) {
List<List<String>> ans = new ArrayList<>();
char[][] matrix = new char[n][n];
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
matrix[i][j] = '.';
}
}
findAll(ans, matrix, 0);
return ans;
}
}
Using strings
class Solution {
public void findAll(List<List<String>> ans, List<String> matrix, int col){
if(col==matrix.size()){
ans.add(new ArrayList<>(matrix));
return;
}
for(int i=0; i<matrix.size(); i++){
if(isSafe(matrix, i,col)){
modifyValueInMatrix(matrix, i, col, 'Q');
findAll(ans, matrix, col+1);
modifyValueInMatrix(matrix, i, col, '.');
}
}
}
public boolean isSafe(List<String> matrix, int row, int col){
int i = 0;
int j =0;
//Left Row check
j = col;
while(j>=0){
if(matrix.get(row).charAt(j)=='Q') return false;
j-=1;
}
//Left Upper Diagonal Check
i = row;
j = col;
while(i>=0 && j>=0){
if(matrix.get(i).charAt(j)=='Q') return false;
i-=1;
j-=1;
}
//Left Lower Diagonal Check
i = row;
j = col;
while(i<matrix.size() && j>=0){
if(matrix.get(i).charAt(j)=='Q') return false;
i+=1;
j-=1;
}
return true;
}
public void modifyValueInMatrix(List<String> matrix, int i, int j, char val){
StringBuilder currentRow = new StringBuilder(matrix.get(i));
currentRow.setCharAt(j,val);
matrix.set(i,currentRow.toString());
}
public List<List<String>> solveNQueens(int n) {
List<List<String>> ans = new ArrayList<>();
List<String> matrix = new ArrayList<>();
String row = "";
for(int i=0; i<n; i++){
row += ".";
}
for(int i=0; i<n; i++){
matrix.add(row);
}
findAll(ans, matrix, 0);
return ans;
}
}
Optimal Approach (map)
This approach optimizes the brute force method by using arrays as maps instead of hashmaps.
The key optimization is determining if a position is safe for the queen. We use three maps for the safety checks, each taking ( O(1) ) time:
Row map: Indicates if a row already has a queen for a given position ((i, j)).
Diagonal map: Indicates if any queen is already placed on the diagonal for a given position ((i, j)).
Anti-diagonal map: Indicates if any queen is placed on the anti-diagonal for a given position ((i, j)).
Diagonal Map ( i+j )
For a given position ((i, j)), all diagonal elements share a common characteristic: the sum of their indices is the same ((i + j)). There are (2n - 1) unique diagonal lines in total. For each diagonal line, all elements have the same (i + j) value. Therefore, we create an array of length (2n - 1) and update the value from 0 to 1 if a queen is placed on that diagonal line.
Anti Diagonal Map ( i-j )
For a given position ((i, j)), the anti-diagonal elements share a common feature: the difference between their indices is the same ((i - j)). We use this key to mark if a queen has already been placed on the anti-diagonal.
Anti diagonal Map with modified key ( n -1 + i - j )
Since arrays cannot have negative indices, we add ( n - 1 ) to the difference ( i - j ) to convert any potential negative values to positive ones. This adjusted value is then used as the key.
Code
class Solution {
public void findAll(List<List<String>> ans, char[][] matrix, int col, int[] rowMap, int[] diagMap, int[] antiDiagMap){
if(col==matrix.length){
ans.add(new ArrayList<>(convertCharToString(matrix)));
return;
}
for(int i=0; i<matrix.length; i++){
if(isSafe(i,col,rowMap, diagMap, antiDiagMap)){
matrix[i][col] = 'Q';
changeTheMaps(rowMap,diagMap,antiDiagMap, i, col, 1);
findAll(ans, matrix, col+1,rowMap,diagMap,antiDiagMap);
changeTheMaps(rowMap,diagMap,antiDiagMap, i, col, 0);
matrix[i][col] = '.';
}
}
}
private boolean isSafe(int row, int col, int[] rowMap, int[] diagMap, int[] antiDiagMap){
int antiDiagKey = row + col;
int diagKey = rowMap.length - 1 + (row-col);
if(rowMap[row]==1 || diagMap[diagKey]==1 || antiDiagMap[antiDiagKey]==1)
return false;
return true;
}
private void changeTheMaps(int[] rowMap, int[] diagMap, int[] antiDiagMap, int row, int col, int flag){
int antiDiagKey = row + col;
int diagKey = rowMap.length - 1 + (row-col);
rowMap[row]=flag;
diagMap[diagKey]=flag;
antiDiagMap[antiDiagKey]=flag;
}
public List<String> convertCharToString(char[][] matrix){
List<String> listMatrix = new ArrayList<>();
for(int i=0; i<matrix.length; i++){
String row = new String(matrix[i]);
listMatrix.add(row);
}
return listMatrix;
}
public List<List<String>> solveNQueens(int n) {
List<List<String>> ans = new ArrayList<>();
char[][] matrix = new char[n][n];
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
matrix[i][j] = '.';
}
}
int[] rowMap=new int[n];
int[] diagMap=new int[2*n-1];
int[] antiDiagMap=new int[2*n-1];
findAll(ans, matrix, 0, rowMap,diagMap,antiDiagMap);
return ans;
}
}
Time and space Complexity
Time Complexity: (O(n! x n))
For the first queen, we have (n) choices in the first column.
For the second queen, we have (n - 1) choices since it cannot be placed in the same row as the first queen.
Similarly, the third queen has (n - 2) choices, and so on.
Thus, the total number of possible arrangements is n x (n - 1) x (n - 2) x ... x 1 = n!.
Since we iterate through each column, the total complexity is O(n! x n).
Space Complexity: (O(n^2))