N Queens Problem Editorial

Practice Problem Link: https://workat.tech/problem-solving/practice/n-queens

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given an n*n chess board with n queens. You need to find all the configurations of the pieces such that no two queens attack each other.

Naive Approach

We try to place the n queens in every possible cell and check if the current configuration is valid. If it is an invalid configuration, we go to the next configuration and try it out.

Analysis

• Time Complexity: Exponential
• Space Complexity: O(1) if recursion stack memory ignored

Optimal Approach

We can make the following observations,

• There can be exactly one queen per row, else they would collide.
• Each column needs to have exactly one queen.
• The left diagonal cannot have more than one queen.
• The right diagonal cannot have more than one queen.

We can start placing a queen per row. When placing a queen on a row, col, we need to check if the position is available based on what we have already placed. Then we move to the next row and solve again recursively.

Analysis

• Time Complexity: O(n!)
• Space Complexity: O(1)

Implementation

C++

bool isValid(vector<string> &matrix, int row, int col) {
	int n = matrix.size();
	for (int i = 0; i <= row; i++) {
		if(matrix[i][col] == 'Q') {
			return false;
		}
	}
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(row - i == j - col) {
				if(matrix[i][j] == 'Q') {
					return false;
				}
			}
			if(row - i == col - j) {
				if(matrix[i][j] == 'Q') {
					return false;
				}
			}

		}
	}
	return true;
}
bool solveNqueens(vector<string> &matrix, int n, int row, vector<vector<string>> &result) {
	if(row >= n) {
		result.push_back(matrix);
	}
	for (int col = 0; col < n; col++) {
		if(isValid(matrix, row, col)) {
			matrix[row][col] = 'Q';
			bool retValue = solveNqueens(matrix, n, row + 1, result);
			if(retValue) {
				return retValue;
			}
			matrix[row][col] = '.';
		}
	}
	return false;
}
vector<vector<string> > getNQueensSolutions(int n) {
    vector<vector<string>> result;
	vector<string> matrix;
	for (int i = 0; i < n; i++) {
		string row = "";
		for (int j = 0; j < n; j++) {
			row += '.';
		}
		matrix.push_back(row);
	}
	solveNqueens(matrix, n, 0, result);
	return result;
}

Java

class Solution {
	boolean isValid(int[] value, int n) {
		for (int i = 0; i < n; i++) {
			if(value[i] == value[n]) {
				return false;
			}
			if(value[i] + i == value[n] + n) {
				return false;
			}
			if(value[i] - i == value[n] - n) {
				return false;
			}
		}
		return true;
	}
	void solveNQueens(int[] value, int k, List<List<String>> result) {
		int n = value.length;
		if(k == n) {
			result.add(arrayToList(value));
		}
		else {
			for(int i = 0; i < n; i++) {
				value[k] = i;
				if(isValid(value, k)) {
					solveNQueens(value, k + 1, result);
				}
			}
		}
	}
	List<String> arrayToList(int[] value) {
		List<String> convert = new ArrayList<>();
		int n = value.length;
		for(int i = 0; i < n; i++) {
			String s = "";
			for(int j = 0; j < n; j++) {
				if(value[i] == j) {
					s += "Q";
				}
				else {
					s += ".";
				}
			}
			convert.add(s);
		}
		return convert;
	}
	List<List<String>> getNQueensSolutions(int n) {
	    List<List<String>> result = new ArrayList<>();
		int[] value = new int[n];
		solveNQueens(value, 0, result);
		return result;
	}
}