What is the intuition behind the checkerboard covering recursive algorithm and how does one get better at formulating such an algorithm?

Question

You may have heard of the classic checkerboard covering puzzle. How do you cover a checkerboard that has one corner square missing, using L-shaped tiles?

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

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

Conceptually, it's easy to understand, but I find it very difficult to think about an implementation. Here's one implementation 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 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 some time to understand this implementation. I'm not sure if I even completely understand it, especially the thought behind the offsets line. Can someone try to explain the implementation succinctly? How does one develop an intuition to think about a solution to problems of this type? I found the solution very clever, especially setting up the offsets line as they did. If someone could help me understand this and perhaps suggestions on how to become better, I would greatly appreciate it.

Thanks!

My advice to understand recursive code: when you analyze a recursive function, assume that it fulfills its specification, i.e. whatever arguments you pass, it somehow performs the expected effect, like a back box. Then with that hypothesis on internal calls, you better understand how the function works. — , May 23 '15 at 17:01
@ YvesDaoust: thanks for the valuable comment. @ unutbu: true, but the assumption was a 2**n sized board. I would still find it difficult to come up with this recursive approach. — yeehaw, May 23 '15 at 17:51

score 3 · Accepted Answer · answered May 26 '15 at 15:41

How does one develop an intuition to think about a solution to problems of this type?

The solution is very clever and quite specific to the problem, but it is also an example of a more general problem-solving strategy called divide and conquer. Instead of attacking the problem in full, create smaller versions of it and try to solve them, eg. with pencil and paper, and trial and error. See if there is something to learn from these solutions.

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

Below is the 4x4 solution. Now, after simply staring at it for a while, one might recognize the connection to the 2x2 case. Each quadrant basically is the 2x2 case.

I found the solution very clever, especially setting up the offsets line as they did. If someone could help me understand this [...]

It is perhaps easier to understand if you unroll the nested loops and replace the loop variables with their values as they appear in offsets. Then you have four if statements instead of the loop. Each statement sets one the four central squares if the corresponding square at the corner of the board is not set.

#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

The author may have even started by writing it like this, but noticed that the code is repetitive, and crafted the loop instead. The offsets variable represents the differences between the statements.

I've realized that in general I understand the reduction part of a recursive problem, but with some solutions, I can't visualize or grasp the unraveling of the problem or unwinding of the problem after the deep recursive calls to the base case have been made. In simple recursive tree traversal like problems, it's easy to the see the unraveling parts, but cases like the problem above, towers of hanoi, etc, the unraveling seems a little difficult to understand. Does one need to grasp that part of the problem, or as long as you know that it's working, it doesn't matter? — yeehaw, May 27 '15 at 23:19
@yeehaw But in this case the work at each level is done before making the recursive calls, so after reaching the base case it simply backtracks. — Janne Karila, May 28 '15 at 10:32

What is the intuition behind the checkerboard covering recursive algorithm and how does one get better at formulating such an algorithm?

1 Answers1