write a python code to solve n-queen problem
- User
write a python code to solve n-queen problem
- Assistant
Sure! Here's a Python code that solves the N-Queen problem using backtracking:
def is_safe(board, row, col, N): # Check for attacks from left side for i in range(col): if board[row][i] == 1: return False # Check for attacks from upper diagonal on left side i = row j = col while i >= 0 and j >= 0: if board[i][j] == 1: return False i -= 1 j -= 1 # Check for attacks from lower diagonal on left side i = row j = col while j >= 0 and i < N: if board[i][j] == 1: return False i += 1 j -= 1 return True def solve_n_queens_util(board, col, N): # Base case: If all queens are placed, return True if col >= N: return True # Try placing queen in each row of this column for i in range(N): if is_safe(board, i, col, N): # Place the queen in the current position board[i][col] = 1 # Recur to place rest of the queens if solve_n_queens_util(board, col + 1, N): return True # Backtrack: If placing queen in board[i][col] doesn't lead to a solution, # remove queen from board[i][col] board[i][col] = 0 # If queen can't be placed in any row of this column, return False return False def solve_n_queens(N): # Create an empty chessboard board = [[0 for _ in range(N)] for _ in range(N)] if not solve_n_queens_util(board, 0, N): print(f"No solution exists for {N} queens.") return False # Print the solution print(f"Solution for {N} queens:") for i in range(N): for j in range(N): print(board[i][j], end=" ") print() return True # Test the code n = int(input("Enter the number of queens: ")) solve_n_queens(n)This code uses the backtracking algorithm to solve the N-Queen problem. The
is_safe()function checks if it is safe to place a queen at a given position on the board. Thesolve_n_queens_util()function recursively iterates over each column, trying to place a queen in each row of that column. If placing the queen in a given position leads to a solution, it returns True. If a solution cannot be found, it backtracks and removes the previously placed queen. Thesolve_n_queens()function creates an empty chessboard and calls thesolve_n_queens_util()function to solve the problem. Finally, it prints the solution if one exists.