How can I stop getting false solutions to a CSP problem?

I am given test cases but my codes comes up with solutions that aren't part of the solutions given. Also every-time I run the code I get a different solution. Any help debugging this will be greatly appreciated.

Here are the constraints:

Red - No constraints
Yellow - equals the rightmost digit of of the product of all its neighbors
Green - equals the rightmost digit of the sum of all its neighbors
Blue - equals the leftmost digit of the sum of all its neighbors
Violet - equals the leftmost digit of the product of all of its neighbors

Each node has a domain of {1,2,...,9}

My Code:

import random

def get_neighbors(node, arcs):
    # Returns the neighbors of the given node
    neighbors = []
    for arc in arcs:
        if arc[0] == node:
            neighbors.append(arc[1])
        elif arc[1] == node:
            neighbors.append(arc[0])
    return neighbors

def is_valid_coloring(node, value, node_values, arcs):
    # Checks if the current node coloring satisfies the constraints
    neighbors = get_neighbors(node, arcs)
    color = node_values[node]
    
    if color == 'Y':
        product = 1
        for neighbor in neighbors:
            product *= node_values[neighbor]
        return value == product % 10
        
    elif color == 'G':
        s = sum(node_values[neighbor] for neighbor in neighbors)
        return value == s % 10

    elif color == 'B':
        sum = 0
        for neighbor in neighbors:
            sum += node_values[neighbor]
        return value == sum % 10
        
    elif color == 'V':
        product = 1
        for neighbor in neighbors:
            product *= node_values[neighbor]
        return value == product % 10
    else:
        return True

def select_unassigned_variable(node_values, nodes, arcs):
    """
    Returns an unassigned node that has the most conflicts with its neighbors.
    """
    unassigned_nodes = [i for i, val in enumerate(node_values) if val == 0]
    max_conflicts = -1
    max_conflict_nodes = []
    for node in unassigned_nodes:
        neighbors = get_neighbors(node, arcs)
        node_conflicts = 0
        for neighbor in neighbors:
            if node_values[neighbor] != 0 and not is_valid_coloring(neighbor, node_values[neighbor], node_values, arcs):
                node_conflicts += 1
        if node_conflicts > max_conflicts:
            max_conflicts = node_conflicts
            max_conflict_nodes = [node]
        elif node_conflicts == max_conflicts:
            max_conflict_nodes.append(node)
    if len(max_conflict_nodes) == 0:
        return None
    return random.choice(max_conflict_nodes)


def get_conflicts(node_values, node, arcs, nodes):
    conflicts = 0
    node_idx = node
    for arc in arcs:
        if node_idx == arc[1]:
            if node_values[node_idx] == node_values[arc[0]]:
                conflicts += 1
        if node_idx == arc[0]:
            if node_values[node_idx] == node_values[arc[1]]:
                conflicts += 1
    return conflicts

def min_conflicts(node_values, nodes, arcs, max_steps):
    # Solves the csp using the mini conflicts algorithm
    for step in range(max_steps):
        unassigned_node = select_unassigned_variable(node_values, nodes, arcs)
        if unassigned_node is None:
            return node_values
        domain = [i for i in range(1, 10)]
        conflicts = [get_conflicts(node_values, unassigned_node, arcs, nodes)]
        min_conflicts = float('inf')
        min_conflict_values = []
        for value in domain:
            new_node_values = node_values.copy()
            new_node_values[unassigned_node] = value
            if is_valid_coloring(unassigned_node, value, new_node_values, arcs):
                num_conflicts = get_conflicts(new_node_values, unassigned_node, arcs, nodes)
                if num_conflicts < min_conflicts:
                    min_conflicts = num_conflicts
                    min_conflict_values = [value]
                elif num_conflicts == min_conflicts:
                    min_conflict_values.append(value)
        if min_conflict_values:
            new_value = random.choice(min_conflict_values)
            node_values[unassigned_node] = new_value
        else:
            # If there are no values that result in a minimum number of conflicts,
            # choose a random value from the domain
            new_value = random.choice(domain)
            node_values[unassigned_node] = new_value
        # If the new node values lead to an invalid coloring, try again with a different value
        if not is_valid_coloring(unassigned_node, new_value, node_values, arcs):
            node_values[unassigned_node] = random.choice([x for x in domain if x != new_value])
    return None


def solve_csp(nodes, arcs, max_steps):
    # Convert nodes to strings
    nodes = [str(node) for node in nodes]
    node_values = [0] * len(nodes)
    return min_conflicts(node_values, nodes, arcs, max_steps)



def main():
    # test Case 1

    nodes = 'YGVRB'
    arcs = [(0,1), (0,2), (1,2), (1,3), (1,4), (2,3), (2,4)]
    max_steps = 1000

    for _ in range(max_steps):
        sol = solve_csp(nodes, arcs, max_steps)
        if sol != []:
            break
            
    all_solutions = [[1, 1, 1, 7, 2],[2, 1, 2, 4, 3],[2, 6, 7, 6, 1],[2, 8, 9, 6, 1],
                    [3, 3, 1, 5, 4],[6, 2, 8, 7, 1],[6, 7, 8, 2, 1],[6, 9, 4, 8, 1]]

    if sol == []:
        print('No solution')
    else:
        if sol in all_solutions:
            print('Solution found:', sol)
        else:
            print('ERROR: False solution found:', sol)


if __name__ == '__main__':
    main()

Output:

ERROR: False solution found: [7, 4, 2, 1, 8]

I have also tried changing to a bigger step size and have not had any luck. I have double checked to make sure my constraints were accurate. Please let me know if there is something I have missed

Upvotes: 1

Answers (2)

Caridorc

Reputation: 6641

Another possibility to debug graph based code is using the networkx package to visualize your graph visually to make the inconsistencies of your solution more intuitive.

You can choose different colors for different nodes, that will help you differentiate the different kinds of nodes in your project:

G.add_nodes_from([
    (4, {"color": "red"}),
    (5, {"color": "green"}),
])

Upvotes: 0

Caridorc

Reputation: 6641

Here is something to get you started on your bug-hunt.

The code below adds tests to your get_neighbors function using the doctest library. That function looks to be working correctly so the bug is most likely elsewhere. If you continue in this fashion adding simple tests to all of your functions and dividing the larger functions in more pieces you will eventually find the bug(s) in your code:

import random
import doctest

def get_neighbors(node, arcs):
    """
    Returns the neighbors of the given node
    
    >>> get_neighbors(0, [(0, 1), (0, 2), (1, 2), (2, 3), (4, 0)])
    [1, 2, 4]
    >>> get_neighbors(1, [(0, 1), (0, 2), (1, 2), (2, 3), (4, 0)])
    [0, 2]
    """
    neighbors = []
    for arc in arcs:
        if arc[0] == node:
            neighbors.append(arc[1])
        elif arc[1] == node:
            neighbors.append(arc[0])
    return neighbors

def is_valid_coloring(node, value, node_values, arcs):
    # Checks if the current node coloring satisfies the constraints
    neighbors = get_neighbors(node, arcs)
    color = node_values[node]
    
    if color == 'Y':
        product = 1
        for neighbor in neighbors:
            product *= node_values[neighbor]
        return value == product % 10
        
    elif color == 'G':
        s = sum(node_values[neighbor] for neighbor in neighbors)
        return value == s % 10

    elif color == 'B':
        sum = 0
        for neighbor in neighbors:
            sum += node_values[neighbor]
        return value == sum % 10
        
    elif color == 'V':
        product = 1
        for neighbor in neighbors:
            product *= node_values[neighbor]
        return value == product % 10
    else:
        return True

def select_unassigned_variable(node_values, nodes, arcs):
    """
    Returns an unassigned node that has the most conflicts with its neighbors.
    """
    unassigned_nodes = [i for i, val in enumerate(node_values) if val == 0]
    max_conflicts = -1
    max_conflict_nodes = []
    for node in unassigned_nodes:
        neighbors = get_neighbors(node, arcs)
        node_conflicts = 0
        for neighbor in neighbors:
            if node_values[neighbor] != 0 and not is_valid_coloring(neighbor, node_values[neighbor], node_values, arcs):
                node_conflicts += 1
        if node_conflicts > max_conflicts:
            max_conflicts = node_conflicts
            max_conflict_nodes = [node]
        elif node_conflicts == max_conflicts:
            max_conflict_nodes.append(node)
    if len(max_conflict_nodes) == 0:
        return None
    return random.choice(max_conflict_nodes)


def get_conflicts(node_values, node, arcs, nodes):
    conflicts = 0
    node_idx = node
    for arc in arcs:
        if node_idx == arc[1]:
            if node_values[node_idx] == node_values[arc[0]]:
                conflicts += 1
        if node_idx == arc[0]:
            if node_values[node_idx] == node_values[arc[1]]:
                conflicts += 1
    return conflicts

def min_conflicts(node_values, nodes, arcs, max_steps):
    # Solves the csp using the mini conflicts algorithm
    for step in range(max_steps):
        unassigned_node = select_unassigned_variable(node_values, nodes, arcs)
        if unassigned_node is None:
            return node_values
        domain = [i for i in range(1, 10)]
        conflicts = [get_conflicts(node_values, unassigned_node, arcs, nodes)]
        min_conflicts = float('inf')
        min_conflict_values = []
        for value in domain:
            new_node_values = node_values.copy()
            new_node_values[unassigned_node] = value
            if is_valid_coloring(unassigned_node, value, new_node_values, arcs):
                num_conflicts = get_conflicts(new_node_values, unassigned_node, arcs, nodes)
                if num_conflicts < min_conflicts:
                    min_conflicts = num_conflicts
                    min_conflict_values = [value]
                elif num_conflicts == min_conflicts:
                    min_conflict_values.append(value)
        if min_conflict_values:
            new_value = random.choice(min_conflict_values)
            node_values[unassigned_node] = new_value
        else:
            # If there are no values that result in a minimum number of conflicts,
            # choose a random value from the domain
            new_value = random.choice(domain)
            node_values[unassigned_node] = new_value
        # If the new node values lead to an invalid coloring, try again with a different value
        if not is_valid_coloring(unassigned_node, new_value, node_values, arcs):
            node_values[unassigned_node] = random.choice([x for x in domain if x != new_value])
    return None


def solve_csp(nodes, arcs, max_steps):
    # Convert nodes to strings
    nodes = [str(node) for node in nodes]
    node_values = [0] * len(nodes)
    return min_conflicts(node_values, nodes, arcs, max_steps)



def main():
    # test Case 1

    nodes = 'YGVRB'
    arcs = [(0,1), (0,2), (1,2), (1,3), (1,4), (2,3), (2,4)]
    max_steps = 1000

    for _ in range(max_steps):
        sol = solve_csp(nodes, arcs, max_steps)
        if sol != []:
            break
            
    all_solutions = [[1, 1, 1, 7, 2],[2, 1, 2, 4, 3],[2, 6, 7, 6, 1],[2, 8, 9, 6, 1],
                    [3, 3, 1, 5, 4],[6, 2, 8, 7, 1],[6, 7, 8, 2, 1],[6, 9, 4, 8, 1]]

    if sol == []:
        print('No solution')
    else:
        if sol in all_solutions:
            print('Solution found:', sol)
        else:
            print('ERROR: False solution found:', sol)


if __name__ == '__main__':
    doctest.testmod(verbose=True)
    main()

Upvotes: 2

How can I stop getting false solutions to a CSP problem?

Answers (2)

Related Questions