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.

You May Also Like

More From Author

+ There are no comments

Add yours

Leave a Reply