Trực giác đằng sau bàn cờ bao gồm thuật toán đệ quy là gì và làm thế nào để có được tốt hơn trong việc xây dựng một thuật toán như vậy?

Question

Bạn có thể đã nghe nói về bảng điều khiển cổ điển bao gồm câu đố. Làm thế nào để bạn bao gồm một bàn cờ có một góc vuông bị thiếu, sử dụng gạch hình chữ L?

Có một cách tiếp cận đệ quy cho điều này như được giải thích trong cuốn sách "Thuật toán Python Làm chủ thuật toán cơ bản trong ngôn ngữ Python".

Ý tưởng là chia bảng thành 4 hình vuông nhỏ hơn, sau đó đặt gạch hình chữ L vào giữa bảng lớn hơn, tạo hiệu quả 4 hình vuông nhỏ hơn với một ô bị thiếu và tiếp tục qua đệ quy.

Về mặt khái niệm, thật dễ hiểu, nhưng tôi thấy rất khó để suy nghĩ về triển khai. Dưới đây là một giải pháp thực hiện -

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 

để chạy mã này, bạn sẽ có được sau

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 

Tôi đã mất một thời gian để hiểu được điều này thực hiện. Tôi không chắc liệu tôi có hoàn toàn hiểu nó hay không, đặc biệt là suy nghĩ đằng sau đường lối tắt. Ai đó có thể cố gắng giải thích việc thực hiện một cách ngắn gọn? Làm thế nào để phát triển trực giác để suy nghĩ về một giải pháp cho các vấn đề thuộc loại này? Tôi tìm thấy giải pháp rất thông minh, đặc biệt là thiết lập các đường dây bù đắp như họ đã làm. Nếu ai đó có thể giúp tôi hiểu điều này và có lẽ gợi ý về cách trở nên tốt hơn, tôi sẽ đánh giá cao điều đó.

Cảm ơn!

Answer 1

Làm cách nào để phát triển trực giác suy nghĩ về giải pháp cho các vấn đề thuộc loại này?

Giải pháp này rất thông minh và khá cụ thể cho các vấn đề, nhưng nó cũng là một ví dụ về một chiến lược giải quyết vấn đề tổng quát hơn gọi là phân chia và chinh phục. Thay vì tấn công vấn đề đầy đủ, hãy tạo các phiên bản nhỏ hơn của nó và cố gắng giải quyết chúng, ví dụ như. bằng bút chì và giấy, thử và sai. Xem nếu có điều gì đó để học hỏi từ các giải pháp này.

Trong trường hợp này, phiên bản 2x2 là không đáng kể để giải quyết, nhưng thật thú vị khi lưu ý rằng nó có một giải pháp.

Dưới đây là giải pháp 4x4. Bây giờ, sau khi chỉ đơn giản là nhìn chằm chằm vào nó một lúc, người ta có thể nhận ra kết nối với trường hợp 2x2. Mỗi góc phần tư về cơ bản là là trường hợp 2x2.

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

Tôi tìm thấy giải pháp rất thông minh, đặc biệt là thiết lập đường dây offsets như họ đã làm. Nếu ai đó có thể giúp tôi hiểu được điều này [...]

Nó có lẽ là dễ hiểu nếu bạn unroll các vòng lồng nhau và thay thế các biến vòng lặp với các giá trị của họ khi họ xuất hiện trong offsets. Sau đó, bạn có bốn câu lệnh if thay vì vòng lặp. Mỗi câu lệnh đặt một trong bốn hình vuông trung tâm nếu hình vuông tương ứng ở góc của bảng không được đặt.

#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 

Tác giả thậm chí có thể bắt đầu bằng cách viết như thế này, nhưng nhận thấy rằng mã lặp lại và được tạo vòng lặp thay thế.Biến số offsets biểu thị sự khác biệt giữa các câu lệnh.