Ziffern = "0123456789ABCDEF"
def code(Feld):
    return "".join(Ziffern[i] for Zeile in Feld for i in Zeile)

Ziffern_to_int = {z:i for i,z in enumerate(Ziffern)}

def erzeugeFeld(code):
    l = [Ziffern_to_int[x] for x in code]
    return [l[i:i+4] for i in range(0,16,4)]

def finde_frei(Feld):
    for i,Zeile in enumerate(Feld):
        for j,x in enumerate(Zeile):
            if x==0:
                return i,j
   
def alleZüge(st):
    f = erzeugeFeld(st)
    i,j = finde_frei(f)
    for (i2,j2) in (i-1,j),(i+1,j),(i,j-1),(i,j+1):
        if 0<=i2<=3 and 0<=j2<=3:
            f[i2][j2],f[i][j] = 0,f[i2][j2]
            yield f
            f[i2][j2],f[i][j] = f[i][j],0
    
def zeige(Feld):
    return "\n--+--+--+--\n".join("|".join(
        f"{i:2}" if i>0 else "  " for i in Zeile)
                                  for Zeile in Feld)
def Stellungstabelle(Feld):
    return {x:(i,j)
            for i,Zeile in enumerate(Feld)
            for j,x in enumerate(Zeile)}
def Abstand(Feld,Stellungstabelle):
    return sum(abs(i-i2)+abs(j-j2)
               for i,Zeile in enumerate(Feld)
               for j,x in enumerate(Zeile)
               for i2,j2 in (Stellungstabelle[x],)
               )

    
Start = [[5,3,2,13], # Beispiel vom 21. Übungsblatt
         [7,1,12,15],
         [11,9,8,10],
         [4,0,6,14]]

Ziel = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,0]]

Zieltabelle = Stellungstabelle(Ziel)

#Start = [[2,1,4,3],[5,6,7,8],[9,10,11,12],[13,14,15,0]]
Start = [[1,2,3,4],[5,6,7,8],[10,9,12,11],[13,14,15,0]]

cStart = code(Start)
print(zeige(Start))
print(cStart)

Stellungen = [[cStart]]
# Stellungen[d] enthält die Stellungen mit Abstand d

minabst = startAbstand = Abstand(Start,Zieltabelle)
print("Startabstand",minabst)

# Breitensuche
bekannt = set([cStart])
for d in range(999):
    # bearbeite Stellungen mit Abstand d
    Stellungen.append([]) # erzeuge Stellungen[d+1]
    if d>=1: bekannt = set(Stellungen[d-1])
    if d>=1: Stellungen[d-1] = []
    for st in Stellungen[d]:
        for stneu in alleZüge(st):
            code_stneu = code(stneu)
            if code_stneu not in bekannt:
                Stellungen[d+1].append(code_stneu)
                bekannt.add(code_stneu)

                abst = Abstand(stneu,Zieltabelle)
                if abst<minabst:
                    minabst = abst
                    print("neuer Abstand", abst)
                    if abst==0:
                        print(d+1,"Züge")
                        exit()

    Anzahl = len(Stellungen[d+1])
    print(f"Distanz {d+1}: {Anzahl} Stellungen, insgesamt", len(bekannt),flush=True)
print("fertig")