N-Queens - Hard Python Backtracking Interview Problem

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution represents a valid board configuration as a list of n strings. Each string is a row of the board: 'Q' marks a queen and '.' marks an empty cell.

A valid placement requires that no two queens attack each other; no two queens share a row, column, or diagonal.

Example 1

Input: n = 4
Output: [[".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."]]
Explanation: There are 2 distinct solutions for n = 4.

Example 2

Input: n = 1
Output: [["Q"]]
Explanation: A single queen on a 1x1 board is trivially valid.

Constraints

1 <= n <= 9

Hints