Wie viele Manhattan-Wege sind bei einem 3 x 3 - Block möglich

3 Lösungen

#113

Wie viele Manhattan-Wege sind bei einem 3 x 3 - Block möglich

Fortgeschrittener - Python von hollst - 28.06.2016 um 16:43 Uhr

Gegeben sei ein 3 x 3 - Int-Array, das mit Zahlen im Bereich von 1 ... 9 belegt werden kann, allerdings niemals mit zwei gleichen Zahlen (d. h. alle 1 ... 9 sind irgenwie verteilt und kommen jeweils genau einmal vor). Die Frage lautet: Mit welcher Wahrscheinlichkeit entsteht bei einer zufälligen Belegung des 3 x 3 - Int-Arrays ein Manhatten-Weg? Ein Manhatten-Weg ist folgendes: Beginnend mit dem Feld, das mit 1 belegt ist, muss das mit 2 belegte Feld mit einem einzigen horizontalen oder vertikalen Schritt erreichbar sein (Sprünge sind verboten). Das gilt auch für alle weiteren Schritte 2 -> 3 -> 4-> ... -> 9 bis zum mit 9 belegten Feld, Diagonalschritte sind gleichfalls nicht erlaubt. Im angehängten Bild sind beispielhaft eine Nicht-Manhatten-Weg-Belegung und vier Belegungen mit Manhatten-Weg dargestellt.

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von Kotgreifer (1100 Punkte) - 17.01.2020 um 14:52 Uhr

Python-Code

import random
startIndex=[]

def getArray():
    zahlen= list(range(1,10))
    a = [[1,2,3],[4,5,6],[7,8,9]]

    for i in range(0,3):
        for x in range(0,3):
            rnd=random.choice(zahlen)
            if rnd == 1:
                startIndex.append(i)
                startIndex.append(x)
            a[i][x]=rnd
            zahlen.remove(rnd)
    return a

def printErg(b,e):
    print("Mannhattan-Weg---------------------------Nach: "+str(e)+" Versuchen")
    print(b[0])
    print(b[1])
    print(b[2])
    print("\n")


#Start
for e in range(1,5000):
    b=getArray()
    index=startIndex
    aktZahl=2                                   #Aktuelle Zahl bei der Index Suche
    end=False                                   #Schleifen Ende
    steps=[[0,0],[1,0],[0,1],[-1,0],[0,-1]]     #Mögliche Schritte die mal laufen kann
    reihe=[] 

    while end==False:
        try:
            reihe= [0,b[0].index(aktZahl)]
        except:
            try:
                reihe=[1,b[1].index(aktZahl)]
            except:
                reihe=[2,b[2].index(aktZahl)]

        step=[index[0]-reihe[0],index[1]-reihe[1]]
        if step not in steps:
            end=True
        else:
            if aktZahl==9:
                printErg(b,e)
                end=True
        aktZahl+=1
        index=reihe
    startIndex=[]