What is the intuition behind the trellis lattice, the recursive algorithm, and how best to cope with the formulation of such an algorithm?

Question

You may have heard of a classic puzzle covering a chessboard. How do you cover a missing square chessboard using L-shaped tiles?

There is a recursive approach to this, as explained in the book Python Algorithms Mastering Basic Python Algorithms.

The idea is to split the board into 4 smaller squares, and then place the L-shaped tile in the center of the larger board, effectively creating 4 smaller squares with one tile and continuing the recursion.

Conceptually, this is easy to understand, but it’s very difficult for me to think about implementation. Here is one solution -

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 

To run the code, you will get the following

  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 

It took me a while to understand this implementation. I’m not sure how much I understand this, especially the thought of a line of displacement. Can someone try to explain the implementation briefly? How do you develop intuition to think about solving problems of this type? I found the solution very smart, especially adjusting the offset line the same way they did. If someone could help me figure this out and maybe suggestions on how to get better, I would really appreciate it.

Thanks!

Answer 1

How do you develop intuition to think about solving problems of this type?

The solution is very smart and very specific to the problem, but it is also an example of a more general problem-solving strategy called division and conquest. Instead of completely attacking the problem, create smaller versions and try to solve them, for example. with pencil and paper, as well as trial and error. See if there is anything that can be learned from these solutions.

In this case, the 2x2 version is trivial for the solution, but it is nevertheless interesting to note that it has a solution.

Below is a 4x4 solution. Now, just by looking at it for a while, you can learn about the connection to the 2x2 case. Each quadrant is basically a 2x2 case.

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

I found the solution very smart, especially adjusting the offset line the same way they did. If someone can help me figure this out [...]

It might be easier to understand if you are expanding nested loops and replacing loop variables with their values ​​as they appear in offsets . Then you have four if statements instead of a loop. Each operator sets one of the four central squares, if the corresponding square in the corner of the board is not installed.

 #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 

Perhaps the author even began to write this way, but noticed that the code repeated itself, and instead created a loop. The offsets variable represents the differences between statements.