Level Order

 source code

N Queens

Given a positive integer N, determine if it's possible to arrange N queens on an NxN board such that no two queens attack the same squares.

Return the board if it's possible. Otherwise return null.

Input:   5
Output:  1 0 0 0 0
         0 0 1 0 0
         0 0 0 0 1
         0 1 0 0 0
         0 0 0 1 0

Note:    0 = an empty square
         1 = a square with a queen

Solutions

The space complexity depends on the board representation used. We could use an array with N x N elements. However, since we only need 1s and 0s for each square of the board, we can also use a single n2-bit number to represent the board.

The number of bits in an n2-bit number is log n2 = 2 log n

Space complexity of board representations:

  • N x N array = O(n2)
  • N2-bit number = O(log n)
Solution Time Space
Brute force O(n2 * nn) O(log n) or O(n2)
Backtracking O(n!) O(log n) or O(n2)
Closed-form solution O(n) O(log n) or O(n2)

Solution 1: Brute force

def n_queens(n)
  board = Array.new(n) { Array.new(n, 0) }
  directions = [
    [0, 1], [1, 1], [1, 0], [1, -1],
    [0, -1], [-1, -1], [-1, 0], [-1, -1]
  ]

  check_board = lambda do
    n_queens = 0
    (0 .. n-1).each do |row|
      (0 .. n-1).each do |col|
        next if board[row][col] == 0
        directions.each do |dir|
          i, j = row + dir[0], col + dir[1]
          while i >= 0 and i < n and j >= 0 and j < n
            return false if board[i][j] == 1
            i, j = i + dir[0], j + dir[1]
          end
        end
        n_queens += 1
      end
    end
    n_queens == n
  end

  n_sq = n**2
  positions = (0 .. n-1).to_a
  positions.each do |j|
    board[j / n][j % n] = 1
  end
  end_positions = (n_sq-n .. n_sq-1).to_a
  while !check_board.call
    i = n - 1
    positions[i] += 1
    board = Array.new(n) { Array.new(n, 0) }
    positions.each do |j|
      board[j / n][j % n] = 1
    end
    while positions[i] == end_positions[i]
      i -= 1
      positions[i] += 1
      return false if positions[i] == n_sq
      positions[i + 1] = positions[i]
    end
  end
  board
end
Time O(n2 * nn)
Space O(log n) or O(n2)

Solution 2: Backtracking

def n_queens(n)
  board = Array.new(n) { Array.new(n, 0) }
  diagonals = [[-1, -1], [1, -1], [1, 1], [-1, 1]]

  can_place_queen = lambda do |row, column|
    (0 .. n-1).each do |i|
      return false if board[row][i] == 1
      return false if board[i][column] == 1
    end
    diagonals.each do |diagonal|
      i, j = row + diagonal[0], column + diagonal[1]
      while i >= 0 and i < n and j >= 0 and j < n
        return false if board[i][j] == 1
        i, j = i + diagonal[0], j + diagonal[1]
      end
    end
    true
  end

  try_row = lambda do |row|
    return true if row == n
    (0 .. n-1).each do |column|
      next unless can_place_queen.call(row, column)
      board[row][column] = 1
      if try_row.call(row + 1)
        return board
      else
        board[row][column] = 0
      end
    end
    false
  end

  try_row.call(0)
end
Time O(n!)
Space O(log n) or O(n2)

Solution 3: Closed form

def n_queens(n)
  return false if n == 2 || n == 3
  board = Array.new(n+1) { Array.new(n+1, 0) }
  if n % 2 == 1
    board[n][n] = 1
    n -= 1
  end
  if n % 6 != 0
    (1 .. n/2).each do |i|
      j = (2*i + n/2 - 3) % n
      board[i][1 + j] = 1
      board[n + 1 - i][n - j] = 1
    end
  elsif (n - 2) % 6 != 0
    (1 .. n/2).each do |i|
      board[i][2*i] = 1
      board[n/2 + i][2*i - 1] = 1
    end
  end
  board[1 .. -1].map {|row| row[1 .. -1] }
end
Time O(n)
Space O(log n) or O(n2)

Resources