Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains an n-length board where 'Q' marks a queen and '.' marks an empty space. The runner accepts the solutions in any order.
Build one partial choice at a time, recurse, then undo that choice before exploring the next option. Pay close attention to duplicate handling and stopping conditions.
Examples
Input: n = 4 Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Input: n = 1 Output: [["Q"]]
Constraints
- 1 <= n <= 9