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.

## + There are no comments

Add yours