N Queens - Leetcode Solution

The N Queens problem is a classic problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share a row, column, or diagonal.

The LeetCode challenge for the N Queens problem asks you to return all possible solutions for a given n (size of the chessboard).

Here is a step-by-step solution for the N Queens problem on LeetCode:

1. Create an empty 2D list of size n×n to represent the chessboard.

2. Define a function is_valid(row, col, board) to check whether a queen can be placed in a given cell on the board. This function will check if there is already a queen in the same row, same column, and diagonals (both upper left and upper right) as the cell given by (row, col).

3. Define a function n_queens_helper(row, board) that will recursively call itself, placing one queen on the board at a time, starting from the top row. It takes the current row and the current state of the board as input.

4. In the helper function, loop over the columns in the current row to check whether a queen can be placed in each cell.

5. If a cell is valid, place a queen in that cell and call the n_queens_helper(row+1, board) function recursively with the updated board and the next row.

6. If none of the columns in the current row allow a queen to be placed, return from the helper function (this is the base case of the recursion).

7. In the main solve_n_queens(n) function, call the helper function n_queens_helper(0, [[]]*n) to generate all possible solutions.

8. Finally, format the solutions as required by LeetCode, which is a list of lists where each inner list represents a single solution and each element of the list represents a string of the chessboard with 'Q' indicating the position of the queen and '.' indicating an empty cell.

Here is the Python code for the N Queens problem on LeetCode:

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def is_valid(row, col, board):
            n = len(board)
            # check if there is already a queen in the same row or same column
            if any(board[row][i] == 'Q' for i in range(n)):
                return False
            if any(board[i][col] == 'Q' for i in range(n)):
                return False
            # check if there is already a queen in the same diagonal
            for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
                if board[i][j] == 'Q':
                    return False
            for i, j in zip(range(row, -1, -1), range(col, n)):
                if board[i][j] == 'Q':
                    return False
            return True

        def n_queens_helper(row, board):
            n = len(board)
            if row == n:
                # base case: all queens have been placed
                solutions.append([''.join(row) for row in board])
                return
            for col in range(n):
                if is_valid(row, col, board):
                    # place a queen in the current cell
                    board[row][col] = 'Q'
                    # recursively place the rest of the queens
                    n_queens_helper(row+1, board)
                    # remove the queen from the current cell
                    board[row][col] = '.'
        
        # initialization
        solutions = []
        board = [['.' for _ in range(n)] for _ in range(n)]
        n_queens_helper(0, board)
        return solutions

This code will generate all possible solutions for the N Queens problem for a given value of n.

1