Leetcode 51 N queen

leetcode_51_n_queen.rb

Leetcode 51 N queen

def solve_n_queens(n)
  @n = n
  @solutions = []

  board = Array.new(n) { Array.new(n, '.') }
  place_queens(board, 0)
  
  @solutions
end

def place_queens(board, row)
  if row == @n
    @solutions << board.map(&:join)
    return
  end

  (0...@n).each do |col|
    if valid_move?(board, row, col)
      board[row][col] = 'Q'
      place_queens(board, row + 1)
      board[row][col] = '.'
    end
  end
end

def valid_move?(board, row, col)
  # Check the column
  (0...row).each { |i| return false if board[i][col] == 'Q' }

  # Check upper-left diagonal
  i, j = row - 1, col - 1
  while i >= 0 && j >= 0
    return false if board[i][j] == 'Q'
    i -= 1
    j -= 1
  end

  # Check upper-right diagonal
  i, j = row - 1, col + 1
  while i >= 0 && j < @n
    return false if board[i][j] == 'Q'
    i -= 1
    j += 1
  end

  true
end