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 hak (980 Punkte) - 10.09.2016 um 00:15 Uhr

Python-Code

import itertools

def manhattan_way_exists(arr, pos, next = 1):
    if next == 9:
        return True
    else:
        if pos % 3 < 2 and arr[pos+1] == next :
            return manhattan_way_exists(arr, pos+1, next+1)
        elif pos % 3 > 0 and arr[pos-1] == next :
            return manhattan_way_exists(arr, pos-1, next+1)
        elif pos < 6 and arr[pos+3] == next :
            return manhattan_way_exists(arr, pos+3, next+1)
        elif pos > 2 and arr[pos-3] == next :
            return manhattan_way_exists(arr, pos-3, next+1)
        else :
            return False
    
def manhattan_way_prob() :
    random_arrays = itertools.permutations(range(9), 9)
    manhattan_way_count = 0
    total_count = 0
    for a in random_arrays:
        total_count += 1
        if manhattan_way_exists(a, a.index(0)):
            manhattan_way_count += 1
    return manhattan_way_count / total_count
    

print(manhattan_way_prob())