Jaka jest intuicja za szachownicą pokrywającą algorytm rekursywny i jak lepiej sobie wyobrazić formułowanie takiego algorytmu?

Question

Być może słyszałeś o klasycznej szachownicy obejmującej puzzle. Jak zasłaniasz szachownicę, której brakuje jednego rogu narożnego, używając płytek w kształcie litery L?

Istnieje podejście rekursywne, jak wyjaśniono w książce "Algorytmy Pythona opanowanie podstawowych algorytmów w języku Python."

Chodzi o to, aby podzielić planszę na 4 mniejsze kwadraty, a następnie umieścić płytkę w kształcie litery L na środku większej planszy, tworząc w efekcie 4 mniejsze kwadraty z jednym brakującym żetonem i kontynuować przez rekursję.

Pojęciowo, jest to łatwe do zrozumienia, ale uważam, że bardzo trudno jest myśleć o implementacji. Oto jedno rozwiązanie realizacja -

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 

aby uruchomić kod, pojawi się następujący

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 

Zajęło mi trochę czasu, aby zrozumieć tę realizację. Nie jestem pewien, czy całkowicie to rozumiem, zwłaszcza myśl stojąca za linią offsetów. Czy ktoś może starać się zwięźle wyjaśnić realizację? Jak rozwinąć intuicję, aby myśleć o rozwiązaniu problemów tego typu? Znalazłem rozwiązanie bardzo sprytne, szczególnie ustawiając linię kompensacji tak jak oni. Jeśli ktoś mógłby mi pomóc zrozumieć to i być może sugestie, jak stać się lepszym, byłbym bardzo wdzięczny.

Dzięki!

Answer 1

Jak rozwinąć intuicję myślenia o rozwiązaniu problemów tego typu?

Rozwiązanie jest bardzo sprytne i dość specyficzne dla problemu, ale jest również przykładem bardziej ogólnej strategii rozwiązywania problemów o nazwie dziel i rządź. Zamiast atakować problem w całości, twórz jego mniejsze wersje i próbuj je rozwiązać, np. z ołówkiem i papierem oraz próbą i błędem. Sprawdź, czy jest coś do nauczenia się z tych rozwiązań.

W tym przypadku wersja 2x2 jest prosta do rozwiązania, ale warto zauważyć, że ma rozwiązanie.

Poniżej znajduje się rozwiązanie 4x4. Teraz, po prostu patrząc na to przez chwilę, można rozpoznać połączenie z przypadkiem 2x2. Każdy kwadrant w zasadzie to w przypadku 2x2.

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

znalazłem rozwiązanie bardzo mądry, zwłaszcza utworzenie linii Przesunięcia punktu jak oni. Jeśli ktoś może mi pomóc zrozumieć ten [...]

Być może łatwiej zrozumieć, jeśli rozwinąć zagnieżdżone pętle i zastąpić zmienne pętlowe z ich wartościami, które pojawiają się w offsets. Następnie masz cztery instrukcje if zamiast pętli. Każde zdanie ustawia jeden z czterech centralnych kwadratów, jeśli odpowiedni kwadrat w rogu planszy nie jest ustawiony.

#top left      
if not board[top][left]: 
    board[top+s-1][left+s-1] = lab 
#top right  
if not board[top][left+side-1]: 
    board[top+s-1][left+s] = lab 
#bottom left  
if not board[top+side-1][left]: 
    board[top+s][left+s-1] = lab 
#bottom right  
if not board[top+side-1][left+side-1]: 
    board[top+s][left+s] = lab 

Autor może nawet rozpoczął pisząc to w ten sposób, ale zauważyłem, że kod jest powtarzalne i wykonane pętlę zamiast.Zmienna offsets reprezentuje różnice między instrukcjami.