kami.py

import networkx as nx

def contract_edges(G,nodes, new_node, attr_dict=None, **attr):
    '''Contracts the edges of the nodes in the set "nodes" '''
    #Add the node with its attributes
    G.add_node(new_node, attr_dict, **attr)
    #Create the set of the edges that are to be contracted
    cntr_edge_set = G.edges(nodes, data = True)
    #Add edges from new_node to all target nodes in the set of edges that are to be contracted
    #Possibly also checking that edge attributes are preserved and not overwritten, 
    #especially in the case of an undirected G (Most lazy approach here would be to return a 
    #multigraph so that multiple edges and their data are preserved)
    G.add_edges_from(map(lambda x: (new_node,x[1],x[2]), cntr_edge_set)) 
    #Remove the edges contained in the set of edges that are to be contracted, concluding the contraction operation
    G.remove_edges_from(cntr_edge_set)
    #Remove the nodes as well
    G.remove_nodes_from(nodes)
    #Return the graph
    return G

def all_moves(G):
    for node in G.nodes():
        for color in ['R','G','B']:
            if not node[0] == color:
                yield (node, color)

def fill(G, node, color):
    samecolor = [n for n in G.nodes() if n[0] == color]
    newnode = color + (str(max([int(n[1:]) for n in samecolor]) + 1) if samecolor else '1')
    oldnodes = [node]
    oldnodes.extend([n for n in G.neighbors(node) if n[0] == color])
    contract_edges(G, oldnodes, newnode)
    #print node, color, G.size()
    #print [e for e in G.edges() if newnode in e]
    return G

def solve(G, max_moves=None, moves=[]):
    for (node, color) in all_moves(G):
        H = G.copy()
        fill(H, node, color)
        if H.size() < G.size():
            #print '-'*len(moves), node, color
            if H.size() == 0:
                moves.append((node, color))
                print 'solved in %d moves:' % len(moves), moves
                moves.pop()
            elif not max_moves or len(moves) < max_moves - 1:
                moves.append((node, color))
                solve(H, max_moves=max_moves, moves=moves)
                moves.pop()

G = nx.Graph()
G.add_edges_from([('G1', 'R1'), ('G1', 'B3'), ('G1', 'B2'), ('R1', 'B2'), ('R1', 'B1'), ('R2', 'B1'), ('B1', 'G3'), ('B2', 'G2'), ('R2', 'G2'), ('R2', 'G3'), ('G3', 'R3'), ('G2', 'R3'), ('B3', 'R3'), ('B3', 'G2')])

solve(G, max_moves = 4)

#manual solution:
#fill(G, 'B1', 'R')
#fill(G, 'R4', 'G')
#fill(G, 'G4', 'B')
#fill(G, 'R3', 'B')

#G = nx.Graph()
#G.add_edges_from([('B1', 'R1')])