raskrižje.py

import functools, itertools

ceste = set('ABCDE')
rb_ceste = sorted(ceste).index
putovi = {odakle + kamo for odakle in ceste - {'C'}
                        for kamo in ceste - {'E', odakle}}
def kružno(put):
    odakle, kamo = put
    return sorted([rb_ceste(odakle) * 2, rb_ceste(kamo) * 2 + 1])

def sijeku_se(*kandidati):
    (a, b), (c, d) = map(kružno, kandidati)
    return a != c and b != d and (a < c < b) ^ (a < d < b)

@functools.lru_cache()
def sijeku(put): return {preko for preko in putovi if sijeku_se(put, preko)}

def oboji(boje, k):
    na_redu = next((put for put, boja in boje.items() if boja is None), None)
    if na_redu is None: yield boje
    for i in range(k):
        if any(boje[preko] == i for preko in sijeku(na_redu)): continue
        yield from oboji({**boje, na_redu: i}, k)

for broj_boja in itertools.count(1):
    print(f"broj boja: {broj_boja}")
    rezultat = next(oboji(dict.fromkeys(putovi), broj_boja), None)
    if rezultat: break

for i in range(broj_boja):
    print(i + 1, end='. faza: ')
    print(*sorted(put for put, boja in rezultat.items() if boja == i))