Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· OpenAIAi2 WildChat-4.8M (AI2)

write a python code to solve n-queen problem

  1. User

    write a python code to solve n-queen problem

  2. 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. The solve_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. The solve_n_queens() function creates an empty chessboard and calls the solve_n_queens_util() function to solve the problem. Finally, it prints the solution if one exists.