N Queens

Place n queens on an n by n chessboard so that no two queens share a row, a column or a diagonal. Implement solveNQueens(n) and return every distinct legal…

Place n queens on an n by n chessboard so that no two queens share a row, a column or a diagonal. Implement solveNQueens(n) and return every distinct legal board exactly once. Represent a queen by Q and an empty cell by a dot. Each board is an ordered list of row strings; the order of boards in the outer result does not matter. Return an empty list when no legal board exists.

- 1 <= n <= 9. - Each returned board has n rows, each containing n Q/dot characters. - Return every legal board once; never reorder the rows within a board.

Example 1: input n = 1; output [["Q"]]. One queen occupies the only cell.

Example 2: input n = 2; output []. Any two queens placed on a two-by-two board attack each other.

Example 3: input n = 4; output [["..Q.","Q...","...Q",".Q.."],[".Q..","...Q","Q...","..Q."]]. There are two complete legal boards. The row order in each board is significant.

Category: Recursion. Topic: recursion. Difficulty: Hard. Patterns: backtracking.