Schachbrett-Torus Züge

Question

Ein Schachbrett nxn ist als Torus geformt.
Das Springer-Minimum s(x, y) ist die minimale Anzahl an Zügen, die ein Springer benötigt, um vom einen Feld aufs andere zu kommen.
Bei einem 8 × 8-Torus wäre s(b3, h4) = 1.
Das Springer-Maximum S(n) eines Feldes ist nun das Maximum von s(x, y) über alle beliebigen Felder x, y des Feldes. Man kommt also in höchsten S(n)
Zügen von jedem Feld auf jedes beliebige andere.

Aufgaben:
1. Berechne S(4) und S(8).
2. Für alle k, l ∈ N mit k ≤ l gilt S(k) ≤ S(l)
Beweise oder widerlege mit Beispiel

Danke

Answer 1

Da du nicht beschreibst, wie du das Problem gelöst haben möchtest, hier ein (sehr naiver) algorithmischer Ansatz in Python:

def removeDuplicates(l):
    result = []
    for x in l:
        if x not in result:
            result.append(x)
    return result

def generateKnightsGraph(size):
    graph = dict()
    for i in range(size):
        for j in range(size):
            legalMoves = [ ((i+2)%size, (j+1)%size), 
                           ((i+2)%size, (j-1)%size), 
                           ((i+1)%size, (j-2)%size), 
                           ((i-1)%size, (j-2)%size), 
                           ((i-2)%size, (j-1)%size), 
                           ((i-2)%size, (j+1)%size), 
                           ((i-1)%size, (j+2)%size), 
                           ((i+1)%size, (j+2)%size) ]
            graph[(i,j)] = removeDuplicates(legalMoves)
    return graph

def s(start, dest, knightsgraph):
    queue = []
    visited = dict.fromkeys(knightsgraph, False)

    queue.append( [start, 0] )
    visited[start] = True

    while len(queue) != 0:
        node, depth = queue.pop(0)
        visited[node] = True
        
        if node == dest:
            return depth
        else:
            for move in knightsgraph[node]:
                if not visited[move]:
                    queue.append( [move, depth + 1] )

    return -1

def S(size):
    kg = generateKnightsGraph(size)
    maximum = -1
    for i in range(size):
        for j in range(size):
            for k in range(size):
                for l in range(size):
                    maximum = max(maximum, s((i,j), (k,l), kg))
    return maximum

if __name__ == '__main__':
    print(S(8))

Für die Funktion s(k,l) wird Breitensuche verwendet.

Das Programm liefert:

a) S(4) = 4, S(8) = 4

b) S(4) > S(5) = 2 aber 4 < 5

Comments

Danke, der Lösungsweg is letztendlich komplett egal.

---

Bist du dir sicher dass es bei s(8) 4 sind?

---

Ja, siehe Bild:

---

Vielen vielen Dank.

Nur noch eine Frage, da ich mich Null, also absolut gar nicht mit Python auskenne. Wie lasse ich mir das ausspucken? ^^

---

Z.B. hier:

https: //repl.it/languages/python3

den code oben einfügen. Bei " print(S(8)) " ggf die 8 durch die gewünschte Feldgröße ersetzen. Anschließend auf "run" klicken.

Falls dir die Antwort geholfen hat, würde ich mich über eine "beste Antwort" freuen (kannst du in der Antwort oben rechts auswählen) :)

---

Klar, hatte ich vergessen. Vielen Vielen Vielen Dank.

---

Womit hast du das Bild gemacht?

---

mit LibreOffice Calc (vgl. Excel). Der Code

size = 8

kg = generateKnightsGraph(size)
depthdict = dict.fromkeys(kg,-1)

queue = [ [(0,0), 0] ]
while len(queue) != 0:
    node, depth = queue.pop(0)
    depthdict[node] = depth

    for move in kg[node]:
        if depthdict[move] == -1:
            queue.append( [move,depth + 1] )

file = open("out.csv","w+")

for i in range(size-1,-1,-1):
    file.write( str(depthdict[(i,0)]) )
    for j in range(1,size):
        file.write( ", " + str(depthdict[(i,j)]) )
    file.write( "\n" )

file.close()

spruckt dir eine .csv Datei aus, die du mit obiger Software öffnen kannst. Die Einfärbung kann dann über bedingte Formatierungen erfolgen:

STRG + A -> Format -> Bedingte Formatierung -> Bedingung.

Dann z.B. "Zellenwert ist", "gleich", "1". -> Neue Vorlage -> Hintergrund -> Farbe wählen -> ok

Dann auf "Hinzufügen" -> gleiches Spiel wieder "Zellenwert ist gleich 2" -> ...