linear_programming.py

def solve_n_queens(board):
    import copy
    import pulp
    from collections import defaultdict

    # Create a deep copy of the board to preserve the original
    copy_board = copy.deepcopy(board)

    print(board)
    
    

    # Create a new LP problem
    prob = pulp.LpProblem("linkedin-queens-solver-math", pulp.LpMinimize)

    grid_size = len(board)

    # Create the 7x7 grid of binary variables
    matrix = [[pulp.LpVariable(f'matrix_{i}_{j}', 0, 1, cat='Binary') for j in range(grid_size)] for i in range(grid_size)]

    # Objective function (since we're not optimizing anything specific, we can set a dummy objective)
    # Let's minimize the sum of all variables
    prob += pulp.lpSum(matrix[i][j] for i in range(grid_size) for j in range(grid_size))

    # Row sum = 1 constraints
    for i in range(grid_size):
        prob += pulp.lpSum(matrix[i][j] for j in range(grid_size)) == 1

    # Column sum = 1 constraints
    for j in range(grid_size):
        prob += pulp.lpSum(matrix[i][j] for i in range(grid_size)) == 1

    # Adding your custom color constraints
    group_positions = defaultdict(list)
    # Populate the dictionary with the positions of each group
    for i in range(len(copy_board)):
        for j in range(len(copy_board[i])):
            group_positions[copy_board[i][j]].append((i, j))
    
    for _, positions in group_positions.items():
        prob += pulp.lpSum(matrix[i][j] for i,j in positions) == 1

    # Adding row-wise adjacent constraints (sum of horizontally adjacent cells <= 1)
    for i in range(grid_size):
        for j in range(grid_size - 1):  # Horizontally adjacent cells in the same row
            prob += matrix[i][j] + matrix[i][j + 1] <= 1

    # Adding column-wise adjacent constraints (sum of vertically adjacent cells <= 1)
    for j in range(grid_size):
        for i in range(grid_size - 1):  # Vertically adjacent cells in the same column
            prob += matrix[i][j] + matrix[i + 1][j] <= 1

    # Adding diagonal adjacent constraints (sum of diagonally adjacent cells <= 1)
    # Top-left to bottom-right diagonal constraint
    for i in range(grid_size - 1):
        for j in range(grid_size - 1):
            prob += matrix[i][j] + matrix[i + 1][j + 1] <= 1

    # Top-right to bottom-left diagonal constraint
    for i in range(grid_size - 1):
        for j in range(1, grid_size):
            prob += matrix[i][j] + matrix[i + 1][j - 1] <= 1

    # Solve the problem
    prob.solve()

    # Check if the problem has a feasible solution
    if pulp.LpStatus[prob.status] == 'Optimal':
        solution = [[pulp.value(matrix[i][j]) for j in range(grid_size)] for i in range(grid_size)]
        print("Solution found:")
        for row in solution:
            print(row)
    else:
        print("No solution found. The problem may be infeasible.")
    
    # Return the solved board
    return copy_board