LeetCode-in-All

51. N-Queens

Hard

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

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

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

Example 1:

Input: n = 4

Output: [[“.Q..”,”…Q”,”Q…”,”..Q.”],[”..Q.”,”Q…”,”…Q”,”.Q..”]]

Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1

Output: [[“Q”]]

Constraints:

Solution

# @param {Integer} n
# @return {String[][]}
def solve_n_queens(n)
  pos = Array.new(2 * n - 1 + 2 * n - 1, false)
  pos2 = Array.new(n, 0)
  ans = []
  helper_queens(n, 0, pos, pos2, ans)
  ans
end

private

def helper_queens(n, row, pos, pos2, ans)
  return construct(n, pos2, ans) if row == n

  (0...n).each do |i|
    index = n + 2 * n - 1 + n - 1 + i - row
    next if pos[i] || pos[n + i + row] || pos[index]

    pos[i] = true
    pos[n + i + row] = true
    pos[index] = true
    pos2[row] = i
    helper_queens(n, row + 1, pos, pos2, ans)
    pos[i] = false
    pos[n + i + row] = false
    pos[index] = false
  end
end

def construct(n, pos, ans)
  sol = []
  (0...n).each do |r|
    queen_row = Array.new(n, '.')
    queen_row[pos[r]] = 'Q'
    sol << queen_row.join
  end
  ans << sol
end