Was ist die Intuition hinter dem Schachbrett, das den rekursiven Algorithmus abdeckt und wie wird man bei der Formulierung eines solchen Algorithmus besser?

Question

Sie haben vielleicht schon von dem klassischen Schachbrett Puzzle gehört. Wie bedecken Sie ein Schachbrett, bei dem ein Eckquadrat fehlt, indem Sie L-förmige Fliesen verwenden?

Es gibt einen rekursiven Ansatz dazu, wie in dem Buch "Python-Algorithmen, die grundlegende Algorithmen in der Python-Sprache beherrschen."

Die Idee besteht darin, das Brett in 4 kleinere Quadrate zu teilen, dann das L-förmige Plättchen in die Mitte eines größeren Brettes zu legen und so effektiv 4 kleinere Quadrate mit einem fehlenden Plättchen zu erzeugen.

Konzeptionell ist es leicht zu verstehen, aber ich finde es sehr schwierig, über eine Implementierung nachzudenken. Hier ist eine Implementierung Lösung -

def cover(board, lab=1, top=0, left=0, side=None): 
     if side is None: side = len(board) 

     # Side length 
     s = side // 2 

     # Offsets for outer/inner squares of subboards 
     offsets = ((0, -1), (side-1, 0)) 

     for dy_outer, dy_inner in offsets: 
      for dx_outer, dx_inner in offsets: 
      # If the outer corner is not set... 
       if not board[top+dy_outer][left+dx_outer]: 
       # ... label the inner corner: 
        board[top+s+dy_inner][left+s+dx_inner] = lab 


     # Next label: 
     lab += 1 
     if s > 1: 
      for dy in [0, s]: 
       for dx in [0, s]: 
        # Recursive calls, if s is at least 2: 
        lab = cover(board, lab, top+dy, left+dx, s) 

     # Return the next available label: 
     return lab 

um den Code auszuführen, erhalten Sie die folgende

board = [[0]*8 for i in range(8)] 
    board[7][7] = -1 
    cover(board) 
    for row in board: 
     print((" %2i"*8)%tuple(row)) 

    3 3 4 4 8 8 9 9 
    3 2 2 4 8 7 7 9 
    5 2 6 6 10 10 7 11 
    5 5 6 1 1 10 11 11 
    13 13 14 1 18 18 19 19 
    13 12 14 14 18 17 17 19 
    15 12 12 16 20 17 21 21 
    15 15 16 16 20 20 21 -1 

Es dauerte einige Zeit, diese Umsetzung zu verstehen. Ich bin mir nicht sicher, ob ich es überhaupt verstehe, vor allem die Gedanken hinter der Offsets-Linie. Kann jemand versuchen, die Implementierung kurz zu erklären? Wie entwickelt man eine Intuition, um über eine Lösung solcher Probleme nachzudenken? Ich fand die Lösung sehr clever, insbesondere die Offset-Linie so einzurichten, wie sie es tat. Wenn mir jemand helfen könnte, dies zu verstehen und vielleicht Vorschläge, wie ich besser werden könnte, würde ich das sehr schätzen.

Danke!

Answer 1

Wie entwickelt man eine Intuition, um über eine Lösung für Probleme dieses Typs nachzudenken?

Die Lösung ist sehr clever und ziemlich spezifisch für das Problem, aber sie ist auch ein Beispiel für eine allgemeinere Problemlösungsstrategie namens "Teile und herrsche". Anstatt das Problem vollständig anzugehen, erstellen Sie kleinere Versionen und versuchen Sie, sie zu lösen, z. mit Bleistift und Papier und Versuch und Irrtum. Sehen Sie, ob es von diesen Lösungen etwas zu lernen gibt.

In diesem Fall ist die 2x2-Version trivial zu lösen, aber es ist dennoch interessant zu bemerken, dass es eine Lösung hat.

Unten ist die 4x4-Lösung. Jetzt, nachdem man es eine Weile lang angestarrt hat, könnte man die Verbindung zum 2x2-Fall erkennen. Jeder Quadrant im Grunde ist der 2x2 Fall.

3 3 4 4 
3 2 2 4 
5 2 6 6 
5 5 6 -1 

fand ich die Lösung sehr klug, vor allem die Versätze Linie Einrichtung wie sie es taten. Wenn jemand könnte mir dies helfen zu verstehen, [...]

Es ist vielleicht leichter zu verstehen, wenn Sie die verschachtelten Schleifen entrollen und die Schleife Variablen mit ihren Werten ersetzen, wie sie in offsets erscheinen. Dann haben Sie vier if-Anweisungen anstelle der Schleife. Jede Anweisung setzt eins der vier zentralen Quadrate, wenn das entsprechende Quadrat an der Ecke der Tafel nicht gesetzt ist.

Der Autor hat vielleicht sogar damit begonnen, es so zu schreiben, aber bemerkte, dass der Code sich wiederholend ist, und stattdessen die Schleife erstellte.Die offsets Variable repräsentiert die Unterschiede zwischen den Anweisungen.