Grafický hlavolam

 Zajímavý úkol z teorie grafů.

Máte deset číslic 0-9. Do každého z deseti polí na obrázku je třeba umístit jedno číslo bez opakování tak, aby vyhovovalo klíči dole. Přičemž první sloupec (0-9) jsou čísla, která dosazujete do polí a druhý sloupec ( 7,17,22,9,18,11,12,8,9,11) jsou součty všech sousedních polí. Umístění čísla vám tak určuje i součet na vybraném poli, ze všech navazujících polí.

Př:

 Když třeba do oranžového pole dosadíte č. 7 , pak modré a žluté pole musí dát součet 12 ( protože 7=12), tzn: 9+3 nebo 8+4. 5+7 nejde, protože 7 je již použita.

Grafický př.:

Řešení mi pár hodin zabralo, hlavně při hledání jiného než náhodného postupu. Teorii grafů jsem jako předmět neměl, Matlab  je (pro začátečníka) na toto trochu nepraktický a hledat náhodně jednu z více než 3,6 milionu možností je na dlouho. Nakonec vyřešeno napůl pomocí excelu a úvahy.

Přidávám i řešení od Tyfa, kde je mimochodem dokázané, že existuje právě jedno řešení. 

import itertools

# pro číslo 0  1   2   3  4   5   6   7  8  9
hledame = [11, 7, 17, 22, 9, 18, 11, 12, 8, 9] #součty

#jména uzlů jsou
#1 2 3 4 5 6 7 8 viz obrázek
#zapsaný jako seznam sousedů
graf = [
        # 1
        [2,8],
        #2
        [1,8,5,3],
        #3
        [2,6,4],
        #4
        [3,6,10],
        #5
        [2,7],
        #6
        [3,4,7],
        #7
        [8,5,6],
        #8
        [1,2,7,9],
        #9
        [8,10],
        #10
        [4,9]
    ]

vsechny = list(itertools.permutations([0,1,2,3,4,5,6,7,8,9])) #generuje
všechny možnosti

for jp in vsechny:  #jp je jedna permutace
    i = 0
    test = True
    for c in jp: #beru postupně čísla z aktuálně testované permutace
        s = 0    #vynuluju součet
        for index in graf[i]:   #beru indexy sousedů z grafu
            s = s + jp[index-1]  #přičtu  (index -1 je proto, že jsou
pojmenované uzly 1-10
        if s != hledame[c]:   #pokus součet pro konkrétní číslo nesedí
s klíčem
            test = False      #je test negativní
            break             #další čísla se netestují
        i = i + 1
    if test:
        print(jp)  #vytiskne řešení pokud existuje

Kdyby měl někdo matematický postup a důkaz možného početu řešení, tak mi ho pošlete.