N-Queens

Instructions

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.

Note that:

Queens on a chessboard are attacking each other if:
a) They are in the same column.
b) They are in the same row.
c) They are on each other’s diagonal.

Therefore, you cannot place another queen on the row above, below or across it.

Approach

We will use BackTracking.
The backtracking strategy involves finding every possible combination for solving a problem where if the current solution is not suitable it is eliminated and the algorithm goes back to find another solution until a suitable solution is reached.

Backtracking implements recursion such that after taking a step you check if it will lead to a possible correct solution and you go back to the previous step if the step does not yield the correct solution. Backtracking algorithms use a brute force approach to find the required output that meets the set constraints at each stage of the problem.

The backtracking strategy is useful where there are possibilities of multiple solutions for a given problem. Different sets of decisions can lead to different solutions. Backtracking is also applicable when some key piece of information is missing and you can backtrack to find possible missing information using different decisions.

Steps to consider in Backtracking:

• Choices/Decisions.

The decisions at each step that determine how you proceed.

• Constraints/Rules.

The rules to consider to identify if the path followed is correct and when to stop or not consider a given path

• Goals.

The desired output.

The Algorithm

Each queen has n choices because each has to be in its own row.

After placing a queen in a given row move to the next row and check where you can place it without attacking other queens; it cannot be across, or in the same column as another queen.

Keep track of the columns we place the queen, and their diagonals; The negative diagonal is row-column while the positive diagonal is row + column

We will try placing a queen in a row and if it is in the column list or in the positive or negative diagonal you cannot place it at that position. Backtrack to placing the queen in another row.

Python Implementation

 class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:

        columnsList = list()     # keep track of the columns
        positiveDiagonal = list() # row+column
        negativeDiagonal = list() # row-column
        endGame = []               #final result
        board = [['.'] * n for i in range(n)] # initialize board with 0 in all rows
        def backtrack(row):
            if row==n: # all rows have been visited  
                copyBoard= [''.join(row)for row in board]
                endGame.append(copyBoard)
                return
            for col in range(n):
                if col in columnsList or (row+col) in positiveDiagonal or (row-col) in negativeDiagonal: # cannot place a queen in this position
                    continue
                # update the variables we are keeping track of
                columnsList.append(col)
                positiveDiagonal.append(row+col)
                negativeDiagonal.append(row-col)
                board[row][col] = 'Q'

                backtrack(row+1) # move to next row and 

                columnsList.remove(col)
                positiveDiagonal.remove(row+col)
                negativeDiagonal.remove(row-col)
                board[row][col] = '.'
        backtrack(0)#call the function
        return endGame

Time Complexity;

The time complexity is O(n²) because we are using a brute force approach in checking all combinations of rows and columns.