Python solution for Kami 2 puzzle

kami.py

class Graph:
    def __init__(self, nodes=dict(), edges=[]):
        self.nodes = nodes
        self.edges = edges
        self.colors = len(set(nodes.values()))

    def connected(self, node):
        for edge in self.edges:
            if edge[0] == node:
                yield edge[1]
            elif edge[1] == node:
                yield edge[0]
        
    def color(self, node, color):
        to_merge = [node]
        to_merge += [n for n in self.connected(node) if self.nodes[n] == color]
        new_n = min(to_merge)

        new_nodes = { new_n: color }
        for node in self.nodes:
            if node not in to_merge:
                new_nodes[node] = self.nodes[node]
        
        new_edges = set()
        for edge in self.edges:
            if edge[0] in to_merge and edge[1] in to_merge:
                continue
            elif edge[0] in to_merge:
                new_edges.add(tuple(sorted((new_n, edge[1]))))
            elif edge[1] in to_merge:
                new_edges.add(tuple(sorted((edge[0], new_n))))
            else:
                new_edges.add(edge)

        return Graph(new_nodes, new_edges)


def solve(graph, steps, n):
    if len(graph.nodes) == 1:
        print(steps)
        exit()

    if n == 0:
        return

    if graph.colors > n + 1:
        return

    for node in graph.nodes:
        colors = list(set([graph.nodes[n] for n in graph.connected(node)]))
        for color in colors:
            g = graph.color(node, color)
            solve(g, steps + [(node, color)], n - 1)


g = Graph(
        nodes = {
            1: "Purple",
            2: "Yellow",
            3: "Red",
            4: "Yellow",
            5: "White",
            6: "Purple",
            7: "Yellow",
            8: "Purple",  
            9: "Yellow",
            10: "Red",
            11: "Purple",
            12: "White",
            13: "Purple",
            14: "Purple",
            15: "White",
            16: "Yellow",
            17: "Red",
            18: "Purple",
        },
        edges = [
            (1, 2),
            (1, 4),
            (2, 3),
            (2, 5),
            (2, 6),
            (3, 6),
            (3, 7),
            (4, 5),
            (4, 8),
            (5, 6),
            (5, 8),
            (6, 7),
            (6, 9),
            (7, 9),
            (7, 12),
            (8, 9),
            (8, 10),
            (9, 11),
            (9, 12),
            (10, 11),
            (10, 13),
            (10, 15),
            (12, 13),
            (12, 14),
            (12, 16),
            (13, 15),
            (13, 16),
            (13, 18),
            (15, 18),
            (16, 17),
            (16, 18),
            (17, 18),
        ])

solve(g, [], 5)

http://vladris.com/blog/2018/04/15/kami-2.html