51. N-Queens

https://leetcode.com/problems/n-queens/

Python

Backtracking

from typing import List


class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        max_index = n-1
        board = [['.']*n for i in range(n)]
        result = []

        def backtrack(row: int):
            if row > max_index:
                result.append([''.join(row) for row in board])
                return

            for col in range(n):
                # print("Checking", row, col)
                if not self.is_valid(board, n, row, col):
                    continue

                board[row][col] = 'Q'
                backtrack(row+1)
                board[row][col] = '.'
        backtrack(0)

        return result

    def is_valid(self, board, n, row, col):
        tl_col, tr_col = min(col-1, n-1), max(col+1, 0)
        for r in range(row-1, -1, -1):
            # Check up
            if board[r][col] == 'Q':
                return False

            # Check top right
            if tr_col < n:
                if board[r][tr_col] == 'Q':
                    return False
                tr_col += 1

            # Check top left
            if tl_col >= 0:
                if board[r][tl_col] == 'Q':
                    return False
                tl_col -= 1
        return True

Javascript

 var solveNQueens = function(n) {
   const boarder = new Boarder(n);
   const emptyBoard = boarder.getEmptyBorad();
   const result = [];

   const backtrack = function(
     row, board, cols = new Set(), diagonals = new Set(), antiDiagonals = new Set()
   ) {
    if (row === n) {
      result.push(boarder.getResult(board.slice()));
      return;
    }

    for (let col = 0; col < n; col++) {
      const diagonal = row - col;
      const antiDiagonal = row + col;

      if (cols.has(col) || diagonals.has(diagonal) || antiDiagonals.has(antiDiagonal))
        continue

      cols.add(col);
      diagonals.add(diagonal);
      antiDiagonals.add(antiDiagonal);
      board[row][col] = 'Q'
      backtrack(row + 1, board, cols, diagonals, antiDiagonals);
      cols.delete(col);
      diagonals.delete(diagonal)
      antiDiagonals.delete(antiDiagonal)
      board[row][col] = '.'
    }
   }
    
   backtrack(0, emptyBoard)

   return result;
};

class Boarder {
  constructor(n) {
    this.n = n;
  }

  getEmptyBorad() {
    const board = [];
    for (let i = 0; i < this.n; i++) {
      board[i] = []
      for (let j = 0; j < this.n; j++) {
        board[i][j] = '.';
      }
    }
    return board;
  }

  getResult(board) {
    const result = []
    for (const row of board) {
      result.push(row.join(''));
    }
    return result;
  }
}