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.
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.
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:
The decisions at each step that determine how you proceed.
The rules to consider to identify if the path followed is correct and when to stop or not consider a given path
The desired output.
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.
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
The time complexity is O(n2) because we are using a brute force approach in checking all combinations of rows and columns.