Solution: N-Queens

Let's solve the N-Queens problem using the Backtracking pattern.

We'll cover the following

Statement
Solution
- Naive solution
- Optimized solution using backtracking

Statement

Given a chessboard of size $n \times n$ , determine how many ways $n$ queens can be placed on the board, such that no two queens attack each other.

A queen can move horizontally, vertically, and diagonally on a chessboard. One queen can be attacked by another queen if both share the same row, column, or diagonal.

Constraints:

$1 \leq n \leq 9$

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive solution

In order to find the optimal placement of the queens on a chessboard, we could find all configurations with all possible placements of $n$ queens and then determine for every configuration if it is valid or not.

However, this would be very expensive, since there would be a very large number of possible placements and only a handful of valid ones. For example, when trying to place $6$ queens on a $6 \times 6$ chessboard using brute force, suppose we place the first two queens side by side on the first two squares, there still remain $34 \times 33 \times 32 \times 31 = 1113024$ possible ways to place the remaining $4$ queens. All of these ways are invalid since placing two queens next to each other is invalid. The time complexity of this solution would be $O(\binom{n^2}{n})$ and the space complexity would be $O(n)$ , where $n$ is the dimension of the chessboard.

Optimized solution using backtracking

A better and more optimized approach would be to only check for valid placements. This can be achieved by backtracking to a previously valid state in case there is no safe move left. Through backtracking, we avoid an exhaustive search and thus improve the algorithm’s performance. Therefore, this problem is a great fit for the backtracking pattern.

Problem analysis

As stated in the problem statement, we have an $n \times n$ chessboard to place the queens such that no two queens attack each other. Let’s understand the implications of these two conditions:

Once we place the first queen anywhere in the first row, no other queen may be placed in that row. Therefore, the search for a safe position for the next queen starts from the next row. This gives us a simple means to store a solution: we simply need to store the column for each row, that is, a list of $n$ column indices, each representing a safe placement.
As there are $n$ rows in the given board, and each row may safely hold just one queen, in any valid solution, all $n$ rows would be used, each holding exactly one queen. This gives us both a condition to check the validity of a solution, as well as a way to check whether a solution is complete.

Solution 1

The backtracking algorithm to solve the $n-$ queens problem is very similar to a depth-first search of a tree.

There are two conditions that cause us to backtrack, but for two different purposes:

When we find that we cannot place the current queen in a particular row, we have to backtrack and alter the position of the queen whose position was decided before the current one. Next, we move forward again to find a safe position for the current queen.
Once we find a valid solution, we still have to identify all the other valid solutions. So, we backtrack by removing the last queen placed on the board and resuming our search for solutions from that point. In order to be sure to find all possible solutions, we’ll need to backtrack, row by row, all the way back to the first queen placed on the board, changing its position and then looking for alternative solutions.

Let’s run our example on a $4 \times 4$ board with $4$ queens:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction

The algorithm proceeds through the following steps:

Place a queen in the first column of the first row.
Now place a queen in the first such column of the second row where placement is permissible. This means that the current queen is not attacked by any queen already on the board.
If no such column is found, we’ll backtrack to the previous row and try to place the queen in the next column of that row.
We continue this until we reach the last row of the board.
When we are able to successfully place the $n^{th}$ queen in the $n^{th}$ row, we’ll have found one valid solution.
After we find a solution, we backtrack to the previous row to find the next solution. Next, we try to find another column in the previous row where placement is permissible.

We’ll start by declaring a results array that will store all possible solutions for $n$ queens, and a solution array that will keep track of the current solution. We’ll also implement a isValidMove() function that checks whether the desired move can place a queen at a safe position. A move is valid if the queen is not vulnerable to attack from other queens on the board.

import java.util.*;
class NQueen {
	public static int tab = 2;
	public static String repeat(String str, int count) {
		String result = "";
		for (int i = 0; i<count; i++) {
			result += str;
		}
		return result;
	}
	public static void printSolutiononBoard(int n, List<Integer> solution, int proposedRow, int proposedCol, int indent) {
		if (solution.size() != n) return;
		indent += tab;
		for (int i = 0; i<n; i++) {
			if (i == 0) System.out.println(repeat(" ", indent) + " " + repeat("_", ((4 * n) - 1)));
			System.out.print(repeat(" ", indent) + "|");
			if (solution.get(n - (i + 1)) != -1) {
				for (int j = 0; j<n; j++) {
					if (solution.get(n - (i + 1)) == j) System.out.print("_X_|");
					else System.out.print("___|");
				}
			} else if (n - (i + 1) == proposedRow) {
				for (int j = 0; j<n; j++) {
					if (proposedCol == j) System.out.print("_?_|");
					else System.out.print("___|");
				}
			} else {
				System.out.print(repeat("___|", n));
			}
			System.out.println();
		}
	}
	// Function to solve N-Queens problem
	public static int solveNQueens(int n) {
		System.out.println("\n Initialising variables");
		List<Integer> results = new ArrayList<Integer> ();
		List<Integer> solution = Arrays.asList(0, 2, -1, -1);
		System.out.println("  Results: " + results);
		System.out.println("  An intermediate solution: " + solution);
		// Let's check the is_valid_move function with an intermediate solution
		// and some proposed moves
		List<List<Integer>> moves = Arrays.asList(Arrays.asList(2, 0), Arrays.asList(2, 1), Arrays.asList(2, 2), Arrays.asList(2, 3));
		for (int i = 0; i<moves.size(); i++) {
			isValidMove(moves.get(i).get(0), moves.get(i).get(1), solution);
		}
		return results.size();
	}
	// this method determines if a queen can be placed at proposed_row, proposed_col
	// with current solution i.e. this move is valid only if no queen in current
	// solution may attack the square at proposed_row and proposed_col
	public static boolean isValidMove(int proposedRow, int proposedCol, List<Integer> solution) {
		int tempTab = tab;
		tempTab += 1;
		int oldRow =0, oldCol = 0, diagonalOffset = 0;
		System.out.println("\n" + repeat(" ", tempTab) + "Proposed row: " + proposedRow);
		System.out.println(repeat(" ", tempTab) + "Proposed column: " + proposedCol);
		// we need to check if any queen on the board in this solution can attack the proposed cell
		printSolutiononBoard(solution.size(), solution, proposedRow, proposedCol, tempTab + 2);
		for (int i = 0; i<proposedRow; i++) {
			oldRow = i;
			oldCol = solution.get(i);
			diagonalOffset = proposedRow - oldRow;
			System.out.println();
			System.out.println(repeat(" ", tempTab) + (i + 1) + ". Old row: " + i);
			System.out.println(repeat(" ", tempTab + 1) + "  Old column: " + solution.get(i));
			System.out.println(repeat(" ", tempTab + 1) + "  Diagonal offset to check: " + diagonalOffset);
			// oldCol == proposedCol --> Checks if there are any queens in the proposed column
			// oldCol == proposedCol - diagonalOffset --> Checks if there are any queens on the bottom left diagonal to the proposed place
			// oldCol == proposedCol + diagonalOffset --> Checks if there are any queens on the bottom right diagonal to the proposed place
			if (oldCol == proposedCol || oldCol == proposedCol - diagonalOffset || oldCol == proposedCol + diagonalOffset) {
				System.out.println(repeat(" ", tempTab + 1) + "  Invalid move: the proposed cell is vulnerable to attack from the queen at [" + i + "," + solution.get(i) + "].");
				return false;
			} else {
				System.out.println(repeat(" ", tempTab + 1) + "  The proposed cell is safe from the queen at [" + i + "," + solution.get(i) + "].");
			}
		}
		System.out.println(repeat(" ", tempTab + 1) + "Valid move: the proposed cell is safe.");
		return true;
	}
  
	public static void main(String args[]) {
		List<Integer> n = Arrays.asList(4);
		for (int i = 0; i<n.size(); i++) {
			System.out.println(i + 1 + ". Queens: " + n.get(i) + ", Chessboard: (" + n.get(i) + "x" + n.get(i) + ")");
			solveNQueens(n.get(i));
			System.out.println(repeat("-", 100));
		}
	}
}

Check if a move is valid

import java.util.*;
class NQueen {
	public static int tab = 2;
	public static String repeat(String str, int count) {
		String result = "";
		for (int i = 0; i<count; i++) {
			result += str;
		}
		return result;
	}
	public static void printBoardState(int n, List<Integer> solution, int indent) {
		if (solution.size() != n) return;
		indent += tab;
		for (int i = 0; i<n; i++) {
			if (i == 0) System.out.println(repeat(" ", indent) + " " + repeat("_", ((4 * n) - 1)));
			System.out.print(repeat(" ", indent) + "|");
			if (solution.get(n - (i + 1)) != -1) {
				for (int j = 0; j<n; j++) {
					if (solution.get(n - (i + 1)) == j) System.out.print("_X_|");
					else System.out.print("___|");
				}
			} else {
				System.out.print(repeat("___|", n));
			}
			System.out.println();
		}
	}
	public static void printSolutiononBoard(int n, List<Integer> solution, int proposedRow, int proposedCol, int indent) {
		if (solution.size() != n) return;
		indent += tab;
		for (int i = 0; i<n; i++) {
			if (i == 0) System.out.println(repeat(" ", indent) + " " + repeat("_", ((4 * n) - 1)));
			System.out.print(repeat(" ", indent) + "|");
			if (solution.get(n - (i + 1)) != -1) {
				for (int j = 0; j<n; j++) {
					if (solution.get(n - (i + 1)) == j) System.out.print("_X_|");
					else System.out.print("___|");
				}
			} else if (n - (i + 1) == proposedRow) {
				for (int j = 0; j<n; j++) {
					if (proposedCol == j) System.out.print("_?_|");
					else System.out.print("___|");
				}
			} else {
				System.out.print(repeat("___|", n));
			}
			System.out.println();
		}
		System.out.println();
	}
	public static void solveNQueensRec(int n, List<Integer> solution, int row, List<Integer> results) {
		int temp = 0;
		for (int i = 0; i<n; i++) {
			System.out.println(repeat(" ", tab) + "Placing queen " + (i + 1) + " in row " + row);
			tab += 1;
			System.out.println(repeat(" ", tab) + "Checking if the move is valid");
			boolean valid = isValidMove(row, i, solution);
			if (valid) {
				temp = tab + 1;
				// Add this valid move to the current solution
				System.out.println(repeat(" ", temp) + "Since the move is valid, we'll add it to the current solution");
				System.out.print(repeat(" ", temp) + solution + " ⟶ ");
				solution.set(row, i);
				System.out.println(solution);
				printBoardState(n, solution, temp + 2);
				System.out.println("");
				solution = new ArrayList<Integer> (Collections.nCopies(n, -1));
			}
		}
	}
	// Function to solve N-Queens problem
	public static int solveNQueens(int n) {
		System.out.println("\n Initialising variables");
		List<Integer> results = new ArrayList<Integer> ();
		List<Integer> solution = new ArrayList<Integer> (Collections.nCopies(n, -1));
		System.out.println("  Results: " + results);
		System.out.println("  solution: " + solution);
		printBoardState(n, solution, 2);
		System.out.println("\n Placing the queens");
		solveNQueensRec(n, solution, 0, results);
		return results.size();
	}
	// this method determines if a queen can be placed at proposed_row, proposed_col
	// with current solution i.e. this move is valid only if no queen in current
	// solution may attack the square at proposed_row and proposed_col
	public static boolean isValidMove(int proposedRow, int proposedCol, List<Integer> solution) {
		int tempTab = tab;
		tempTab += 1;
		int oldRow =0, oldCol = 0, diagonalOffset = 0;
		System.out.println("\n" + repeat(" ", tempTab) + "Proposed row: " + proposedRow);
		System.out.println(repeat(" ", tempTab) + "Proposed column: " + proposedCol);
		// we need to check if any queen on the board in this solution can attack the proposed cell
		printSolutiononBoard(solution.size(), solution, proposedRow, proposedCol, tempTab + 2);
		for (int i = 0; i<proposedRow; i++) {
			oldRow = i;
			oldCol = solution.get(i);
			diagonalOffset = proposedRow - oldRow;
			System.out.println();
			System.out.println(repeat(" ", tempTab) + (i + 1) + ". Old row: " + i);
			System.out.println(repeat(" ", tempTab + 1) + " Old column: " + solution.get(i));
			System.out.println(repeat(" ", tempTab + 1) + " Diagonal offset to check: " + diagonalOffset);
			// oldCol == proposedCol --> Checks if there are any queens in the proposed column
			// oldCol == proposedCol - diagonalOffset --> Checks if there are any queens on the bottom left diagonal to the proposed place
			// oldCol == proposedCol + diagonalOffset --> Checks if there are any queens on the bottom right diagonal to the proposed place
			if (oldCol == proposedCol || oldCol == proposedCol - diagonalOffset || oldCol == proposedCol + diagonalOffset) {
				System.out.println(repeat(" ", tempTab + 1) + " Invalid move: the proposed cell is vulnerable to attack from the queen at [" + i + "," + solution.get(i) + "].");
				return false;
			} else {
				System.out.println(repeat(" ", tempTab + 1) + " The proposed cell is safe from the queen at [" + i + "," + solution.get(i) + "].");
			}
		}
		System.out.println(repeat(" ", tempTab + 1) + "Valid move: the proposed cell is safe.");
		return true;
	}
  
	public static void main(String args[]) {
		List<Integer> n = Arrays.asList(4, 5, 6, 7, 8);
		for (int i = 0; i<n.size(); i++) {
			System.out.println(i + 1 + ". Queens: " + n.get(i) + ", Chessboard: (" + n.get(i) + "x" + n.get(i) + ")");
			solveNQueens(n.get(i));
			tab = 2;
			System.out.println(repeat("-", 100));
		}
	}
}

Placing the queens

import java.util.*;
class NQueen {
	public static int tab = 2;
	public static boolean printVar = true;
	public static String repeat(String str, int count) {
		String result = "";
		for (int i = 0; i<count; i++) {
			result += str;
		}
		return result;
	}
	public static void printBoardState(int n, List<Integer> solution, int indent) {
		if (solution.size() != n) return;
		indent += tab;
		for (int i = 0; i<n; i++) {
			if (i == 0) System.out.println(repeat(" ", indent) + " " + repeat("_", ((4 * n) - 1)));
			System.out.print(repeat(" ", indent) + "|");
			if (solution.get(n - (i + 1)) != -1) {
				for (int j = 0; j<n; j++) {
					if (solution.get(n - (i + 1)) == j) System.out.print("_X_|");
					else System.out.print("___|");
				}
			} else {
				System.out.print(repeat("___|", n));
			}
			System.out.println();
		}
	}
	public static void solveNQueensRec(int n, List<Integer> solution, int row, List<List<Integer>> results) {
		//int temp = 0;
		// We have reached the last row (the nth row) with a valid
		// set of n queen positions
		if (row == n) {
			// Save this valid solution and backtrack so that the search for alternative solutions may continue
			System.out.println("  A valid solution found. Adding it to the results array");
			System.out.println("  Solution: " + solution);
			results.add(solution);
			printBoardState(n, solution, 1);
			if (printVar)
				System.out.println("\n Similarly, we'll find other such valid solutions");
			printVar = false;
			System.out.println();
			return;
		}
		for (int i = 0; i<n; i++) {
			if (printVar)
				System.out.println(repeat(" ", tab) + "Placing queen " + (row + 1) + " in row " + row);
			boolean valid = isValidMove(row, i, solution);
			if (valid) {
				int temp = tab + 1;
				// Add this valid move to the current solution
				if (printVar) {
					System.out.println(repeat(" ", temp) + " Since the move is valid, we'll add it to the current solution");
					System.out.print(repeat(" ", temp) + " " + solution + " ⟶ ");
				}
				solution.set(row, i);
				if (printVar) {
					System.out.println(solution);
					System.out.println("");
				}
				solveNQueensRec(n, solution, row + 1, results);
			} else {
				if (printVar)
					System.out.println(repeat(" ", 100) + "   Backtracking...\n");
			}
		}
	}
	// Function to solve N-Queens problem
	public static int solveNQueens(int n) {
		System.out.println("\n Initialising variables");
		List<List<Integer>> results = new ArrayList<>();
		List<Integer> solution = new ArrayList<Integer> (Collections.nCopies(n, -1));
		System.out.println("  Results: " + results);
		System.out.println("  solution: " + solution);
		printBoardState(n, solution, 2);
		System.out.println("\n Placing the queens");
		solveNQueensRec(n, solution, 0, results);
		return results.size();
	}
	// this method determines if a queen can be placed at proposed_row, proposed_col
	// with current solution i.e. this move is valid only if no queen in current
	// solution may attack the square at proposed_row and proposed_col
	public static boolean isValidMove(int proposedRow, int proposedCol, List<Integer> solution) {
		int tempTab = tab;
		tempTab += 1;
		int oldRow =0, oldCol = 0, diagonalOffset = 0;
		for (int i = 0; i<proposedRow; i++) {
			oldRow = i;
			oldCol = solution.get(i);
			diagonalOffset = proposedRow - oldRow;
			// oldCol == proposedCol --> Checks if there are any queens in the proposed column
			// oldCol == proposedCol - diagonalOffset --> Checks if there are any queens on the bottom left diagonal to the proposed place
			// oldCol == proposedCol + diagonalOffset --> Checks if there are any queens on the bottom right diagonal to the proposed place
			if (oldCol == proposedCol || oldCol == proposedCol - diagonalOffset || oldCol == proposedCol + diagonalOffset) {
				if (printVar)
					System.out.println(repeat(" ", tempTab + 1) + "Invalid move: the proposed cell is vulnerable to attack from the queen at [" + i + "," + solution.get(i) + "].");
				return false;
			}
		}
		if (printVar) {
			System.out.println(repeat(" ", tempTab + 1) + "Valid move: the proposed cell [" + proposedRow + ", " + proposedCol + "] is safe");
			System.out.println();
		}
		return true;
	}
  
	public static void main(String args[]) {
		List<Integer> n = Arrays.asList(4, 5, 6, 7, 8);
		for (int i = 0; i<n.size(); i++) {
			System.out.println(i + 1 + ". Queens: " + n.get(i) + ", Chessboard: (" + n.get(i) + "x" + n.get(i) + ")");
			int res = solveNQueens(n.get(i));
			tab = 2;
			System.out.println("\nTotal solutions count for " + n.get(i) + " queens on a " + n.get(i) + "x" + n.get(i) + " chessboard: " + res);
			System.out.println(repeat("-", 100));
		}
	}
}

N-Queens

import java.util.*;
class NQueen {
	public static String repeat(String str, int count) {
		String result = "";
		for (int i = 0; i<count; i++) {
			result += str;
		}
		return result;
	}
	public static void solveNQueensRec(int n, List<Integer> solution, int row, List<List<Integer>> results) {
		if (row == n) {
			results.add(solution);
			return;
		}
		for (int i = 0; i<n; i++) {
			boolean valid = isValidMove(row, i, solution);
			if (valid) {
				solution.set(row, i);
				solveNQueensRec(n, solution, row + 1, results);
			} 
		}
	}
	// Function to solve N-Queens problem
	public static int solveNQueens(int n) {
		List<List<Integer>> results = new ArrayList<>();
		List<Integer> solution = new ArrayList<Integer> (Collections.nCopies(n, -1));
		solveNQueensRec(n, solution, 0, results);
		return results.size();
	}
	
	// this method determines if a queen can be placed at proposed_row, proposed_col
	// with current solution i.e. this move is valid only if no queen in current
	// solution may attack the square at proposed_row and proposed_col
	public static boolean isValidMove(int proposedRow, int proposedCol, List<Integer> solution) {
		int oldRow =0, oldCol = 0, diagonalOffset = 0;
		for (int i = 0; i<proposedRow; i++) {
			oldRow = i;
			oldCol = solution.get(i);
			diagonalOffset = proposedRow - oldRow;
			if (oldCol == proposedCol || oldCol == proposedCol - diagonalOffset || oldCol == proposedCol + diagonalOffset) {
				return false;
			}
		}
		return true;
	}
  
	public static void main(String args[]) {
		List<Integer> n = Arrays.asList(4, 5, 6, 7, 8);
		for (int i = 0; i<n.size(); i++) {
			System.out.println(i + 1 + ".\tQueens: " + n.get(i) + ", Chessboard: (" + n.get(i) + "x" + n.get(i) + ")");
			int res = solveNQueens(n.get(i));
			System.out.println("\n\tTotal solutions count for " + n.get(i) + " queens on a (" + n.get(i) + "x" + n.get(i) + ") chessboard: " + res);
			System.out.println(repeat("-", 100));
		}
	}
}

N-Queens

Solution summary

To recap, the solution to this problem can be divided into the following parts:

Place a queen in the first column of the first row.
Place a queen wherever permissible in the next row.
Backtrack if no safe configuration exists.
Once a solution is found, backtrack to find other possible configurations.

Time complexity

The recurrence relation for the time complexity of this solution is:

T(n)=nT(n-1)+O(n^2).

Deriving a precise upper bound for this recurrence relation is beyond the scope of this course. However, we can prove by induction that the time complexity, given this recurrence relation, is no worse than $O(n!)$ .

Space complexity

The space complexity of this solution is $O(n)$ , where $n$ is the dimension of the chessboard. This is because the maximum number of calls to the recursive worker function is $n$ , one for each row, and each call takes up $O(1)$ space on the call stack.

Solution 2

We may also implement an iterative form of the backtracking search function, using a stack to keep track of the current solution. The stack holds only the column values and one solution is stored in the stack at a time. When one solution is complete, we save the solution present in the stack to a separate list of valid solutions. We then backtrack by popping from the stack and resuming the search for the next solution.

Let’s run the above example using this solution and see how backtracking is achieved using the stack:

import java.util.*;
class NQueen {
	// This solution uses a stack to store the solution.
	// Stack will hold only the column values and one solution
	// will be stored in the stack at a time.
	static boolean isValidMove(int proposedRow, int proposedCol, List<Integer> solution) {
		// we need to check with all queens
		// in current solution
		int oldRow =0, oldCol = 0, diagonalOffset = 0;
		for (int i = 0; i<proposedRow; ++i) {
			oldRow = i;
			oldCol = solution.get(i);
			diagonalOffset = proposedRow - oldRow;
			// oldCol == proposedCol --> Checks if there are any queens in the proposed column
			// oldCol == proposedCol - diagonalOffset --> Checks if there are any queens on the bottom left diagonal to the proposed place
			// oldCol == proposedCol + diagonalOffset --> Checks if there are any queens on the bottom right diagonal to the proposed place
			if (oldCol == proposedCol || oldCol == proposedCol - diagonalOffset || oldCol == proposedCol + diagonalOffset) {
				return false;
			}
		}
		return true;
	}
	// This solution uses stack to store the solution.
	// Stack will hold only the column values and one solution
	// will be stored in the stack at a time.
	static int solveNQueens(int n) {
		List<List<Integer>> results = new ArrayList<List<Integer>> ();
		List<Integer> solution = new ArrayList<Integer> (Collections.nCopies(n, -1));
		Stack<Integer> solStack = new Stack<Integer> ();
		//
		// for (int i = 0; i<n; ++i) {
		// solution.add(-1);
		// }
		int row = 0;
		int col = 0;
		while (row<n) {
			// For the current state of the solution, check if a queen can be placed in any
			// column of this row
			while (col<n) {
				if (isValidMove(row, col, solution)) {
					// If this is a safe position for a queen (a valid move), save
					// it to the current solution on the stack...
					solStack.push(col);
					solution.set(row, col);
					row++;
					col = 0;
					// ... and move on to checking the next row (breaking out of the inner loop)
					break;
				}
				col++;
			}
			// If we have checked all the columns
			if (col == n) {
				// If we are working on a solution
				if (!solStack.empty()) {
					// Backtracking, as current row does not offer a safe spot given the previous
					// move
					// So, get set up to check the previous row with the next column
					col = solStack.peek() + 1;
					solStack.pop();
					row--;
				} else {
					// If we have backtracked all the way and found this to be a dead-end,
					// break out of the inner loop as no more solutions exist
					break;
				}
			}
			// If we have found a safe spot for a queen in each of the rows
			if (row == n) {
				// Add the solution into results
				results.add(new ArrayList<Integer> (solution));
				// Backtrack to find the next solution
				row--;
				col = solStack.peek() + 1;
				solStack.pop();
			}
		}
		return results.size();
	}
	
	public static void main(String args[]) {
		List<Integer> n = Arrays.asList(4, 5, 6, 7);
		for (int i = 0; i<n.size(); i++) {
			int res = solveNQueens(n.get(i));
			System.out.println((i + 1) + ".  Total solutions count for " + n.get(i) + " queens on the chessboard (" + n.get(i) + "x" + n.get(i) + "): " + res);
			System.out.println("-------------------------------------------------------------------------------------\n");
		}
	}
}

N-Queens

Solution summary

To recap, the solution to this problem can be divided into the following parts:

Place a queen in the first column of the first row.
Use a stack to keep track of the current solution.
Place a queen wherever permissible in the next row.
Backtrack by popping from the stack to find the next solution.

Time complexity

The time complexity of this solution is $O(n!)$ , where $n$ is the dimension of the chessboard.

Space complexity

The space complexity of this solution is $O(n)$ , where $n$ is the dimension of the chessboard.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.

Getting Started

Two Pointers

Fast and Slow Pointers

Sliding Window

Merge Intervals

In-Place Manipulation of a Linked List

Two Heaps

K-way merge

Top K Elements

Modified Binary Search

Subsets

Greedy Techniques

Backtracking

Dynamic Programming

Cyclic Sort

Topological Sort

Sort and Search

Matrices

Stacks

Graphs

Tree Depth-First Search

Tree Breadth-First Search

Trie

Hash Maps

Knowing What to Track

Union Find

Custom Data Structures

Bitwise Manipulation

Challenge Yourself

Conclusion

Solution: N-Queens

Statement

Solution

Naive solution

Optimized solution using backtracking

Problem analysis

Solution 1

Step-by-step solution construction

Just the code

Solution summary

Time complexity

Space complexity

Solution 2

Solution summary

Time complexity

Space complexity