[Leetcode] N Queens

Problem

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

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

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Algorithm

This problem is similar to Combination-Like problems. 

We can use a 2D board to store the solution. For each row, we have n possible positions to put a queen. In order to get a valid solution, we need a helper method to check the validity of the solution. Since the solution before current row are valid, we only need to check if current queen conflicts with previous queens. By checking this row, this column, and four different directions of diagonal, we can validate the solution. 

The above solution needs O(n^2) space. Note each row only have one queen, so the 2D array is more than needed. We can use a 1D array instead to store the column information of each queens. location[row] = col means, the queen at row = row is located at column = col. To validate newly placed queens, we only need to check 

for i = 0 to current row -1

        if(location(i) = current row || current row - i== abs(location(current row) - location(i))) 

              return false

return true

Code