Solve the N-Queens problem

Q: Solve the N-Queens problem

This question evaluates a candidate's competence in backtracking, constraint satisfaction, combinatorial search, recursion, and state representation. It is commonly asked in technical interviews because it probes algorithmic problem-solving and handling of combinatorial explosion within the Coding & Algorithms domain, testing both conceptual understanding and practical implementation skills.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

Problem

Given an integer n, place n queens on an n × n chessboard so that no two queens attack each other (i.e., no two queens share the same row, column, or diagonal).

Return all distinct valid boards.

Input

An integer n (typically 1 ≤ n ≤ 9 in interviews).

Output

A list of solutions, where each solution is an array of n strings of length n .
Each string contains only:
- 'Q' for a queen
- '.' for an empty cell

Example

For n = 4, one valid output format is:

[".Q..","...Q","Q...","..Q."]

(Your output may list solutions in any order.)

Notes

You may assume there is at most one queen per row (or per column) in your construction approach.