# How to Solve the N-Queen Problem Using Python?

Estimated read time 2 min read

The N-Queen problem is a classic algorithmic problem that asks you to place N chess queens on an N x N chessboard such that no two queens threaten each other. Here is an example of how to solve this problem in Python using a backtracking algorithm:

``````def solveNQueens(n):
def backtrack(row, queens, xy_dif, xy_sum):
if row == n:
result.append(queens)
return
for col in range(n):
if col not in queens and row-col not in xy_dif and row+col not in xy_sum:
backtrack(row+1, queens+[col], xy_dif+[row-col], xy_sum+[row+col])

result = []
backtrack(0, [], [], [])
return [['.'*i + 'Q' + '.'*(n-i-1) for i in sol] for sol in result]``````

In this solution, we use a nested function `backtrack` to recursively generate all possible solutions to the N-Queen problem. The function takes four input lists: `row`, `queens`, `xy_dif`, and `xy_sum`.

`row` is the current row we are considering, `queens` is a list of the columns of the queens placed so far, `xy_dif` is a list of the differences between the row and column of each queen placed so far, and `xy_sum` is a list of the sums of the row and column of each queen placed so far.

In the main function, we initialize an empty list `result` and call `backtrack` with initial values of 0 and empty lists for `queens`, `xy_dif`, and `xy_sum`.

Inside the `backtrack` function, we first check if we have placed queens in all rows (`row == n`). If this is the case, we append the current `queens` list to the `result` list of solutions and return.

Otherwise, we iterate through each column in the current row and check if placing a queen in that column would result in a valid solution. A solution is valid if no two queens are in the same row, column, or diagonal. If the placement is valid, we recursively call `backtrack` with the updated values of `row`, `queens`, `xy_dif`, and `xy_sum`.

Finally, in the main function, we format the solutions in `result` as a list of lists of strings, where each string is either ‘.’ or ‘Q’ representing an empty square or a queen, respectively.

To use this function, simply call `solveNQueens(n)` with the appropriate integer value of `n`. The function will return a list of all valid solutions to the N-Queen problem.

Add yours