What's wrong with my Python code about this algorithm?

Question

There is a game. Each person has a 10 * 10 chequered board. Before the game starts, they need to place three "planes" on their board. The question is: how many possibilities are there for planes placement?

This is a plane.

These are two legal ways to place airplanes. The placement of the plane can not be overlapped, but can be inserted in the gap.

My code is as follows:

class Plane():
    def __init__(self, x, y, direction):
        self.x = x
        self.y = y
        self.direction = direction
    @property
    def body(self):
        x = self.x
        y = self.y
        if self.direction == "up":
            return[(x-2, y-1), (x-1, y-1), (x, y-1),
                   (x+1, y-1), (x+2, y-1), (x, y-2),
                   (x-1, y-3), (x, y-3), (x+1, y-3)]
        elif self.direction == "down":
            return[(x-2, y+1), (x-1, y+1), (x, y+1),
                   (x+1, y+1), (x+2, y+1), (x, y+2),
                   (x-1, y+3), (x, y+3), (x+1, y+3)]
        elif self.direction == "left":
            return[(x+1, y+2), (x+1, y+1), (x+1, y),
                   (x+1, y-1), (x+1, y-2), (x+2, y),
                   (x+3, y+1), (x+3, y), (x+3, y-1)]
        elif self.direction == "right":
            return[(x-1, y+2), (x-1, y+1), (x-1, y),
                   (x-1, y-1), (x-1, y-2), (x-2, y),
                   (x-3, y+1), (x-3, y), (x-3, y-1)]
    @property
    def check(self):
        global chart
        for x in self.body:
            if x[0]<0 or x[0]>9 or x[1]<0 or x[1]>9 or chart[x[0]][x[1]] != 0:
                return False
        return True

def recursion(plane):
    global chart, plane_list
    if plane.check:
        x = plane.x
        y = plane.y
        plane_list.append(plane)
        chart[x][y] = 2
        for j in plane.body:
            chart[j[0]][j[1]] = 1
        if x!= 9:
            find_plane(x+1, y)
        else:
            find_plane(0, y+1)
        plane_list.remove(plane)
        chart[x][y] = 0
        for j in plane.body:
            chart[j[0]][j[1]] = 0

def find_plane(startx, starty):
    global method_list, chart, plane_list
    if len(plane_list) == 3:
        method_list.append(plane_list)
        return
    if startx == 9 and starty == 9:
        return
    for x in range(10):
        for y in range(10):
            if (x > startx or y > starty) and (chart[x][y] == 0):
                recursion(Plane(x, y, "up"))
                recursion(Plane(x, y, "down"))
                recursion(Plane(x, y, "left"))
                recursion(Plane(x, y, "right"))

if __name__ == "__main__":
    method_list = []
    chart = [[0]*10 for i in [0]*10]
    plane_list = []
    find_plane(0, 0)
    print(method_list)

I have problems:

1. This is method_list I got finally:

The screenshot here is not complete. In fact, method_list consists of 174631 []. It puzzled me a lot, because my code logic is that only when the length of plane list is 3, plane_list will be added to method_list. I didn't understand why method_list is made up of a bunch of empty lists.

2. My answer 174631 is wrong. I searched the Internet for this problem and found this article (Chinese). https://blog.csdn.net/GGN_2015/article/details/91295002

Translation: After DFS, we found that there are 8744 placement schemes in 9 * 9 airplane bombing game. If the size of chessboard is 10 × 10, the total number of schemes is 66816.

But my answer is several times of 66816. I've been thinking about the algorithm for a long time and still don't know where I'm wrong. Hope to get an answer.

Answer 1

I spend some time and get 66816. I will try to answer:

1. Whole your method_list is list of references to one list - plane_list. When plane_list is empty, then all elements of method_list are empty... and plane_list is empty, because you removed all elements. You should replace method_list.append(plane_list) with method_list.append(plane_list.copy()).

2. You have really bad logic behind this code:

    if x!= 9:
        find_plane(x+1, y)
    else:
        find_plane(0, y+1)

I understand what are you trying to do here, but you do it wrong. So... don't do it. Don't try to have some kind of order in plane_list. just do that:

find_plane(0, 0)

then you will have duplicates in method_list: planes can be in such orders: (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0). there are 6 copies of the same position. So... you should divide len(method_list) by 6.