647. Queens Boards
A park designer wants to place n watchtowers on an n x n square of land so that no two towers see each other. A tower sees every cell in its own row, its own column and along both diagonals.
Return every valid layout. A layout is an array of n strings of length n, one per row from top to bottom, where T marks a tower and . an empty cell. Each layout must be listed once and the layouts may be returned in any order. If no layout exists, return an empty array.
Example 1
- Input:
- n = 4
- Output:
- [[".T..","...T","T...","..T."],["..T.","T...","...T",".T.."]]
- Explanation:
Two layouts exist for a 4 x 4 square; they are mirror images of each other.
Example 2
- Input:
- n = 1
- Output:
- [["T"]]
- Explanation:
A single cell holds the only tower.
Example 3
- Input:
- n = 3
- Output:
- []
- Explanation:
On a 3 x 3 square any two towers see each other, so no layout exists.
Constraints
- 1 ≤
n≤ 7
How this problem is judged
- Answers
- The outer list may be in any order. Everything inside each item must match exactly.
Expected complexity
- Time
- O(n!)
- Space
- O(n)