03
Май
2020

Применение рекурсии в задаче создания полей для битья в шашках

Не так давно решил создать шашки на python. В какой-то момент возникла необходимость просчитать все возможные поля взятий для какой - либо конкретной шашки. Для этой задачи я решил использовать рекурсию: выясняем, есть ли возможность побить в четырех направлениях, если такая возможность есть, то добавляем эту позицию в массив, после чего рекурсивно вызываем эту же функцию для новой позиции, ведь, как известно, шашки могут бить сразу несколько других. Все позиции я просчитывал с помощью массива 8 х 8:

# создаем массив 8 * 8. Каждый элемент "-1"
# будет обозначать вражескую шашку, а элемент
# 1 - наши шашки.
virtual_board = [ [0] * 8 for x in range(8) ]

# поставим нашу шашку в левый верхний угол и попробуем
# вычислить позиции для битья двух других, вражеских шашек
virtual_board[0][0] = 1
virtual_board[1][1] = -1
virtual_board[1][3] = -1 

class Example():
    def __init__(self, virtual_board):
        self.virtual_board = virtual_board
        self.positions = list()

    def check_taking_steps_for_player(self, x, y):
        # существует ли данная позиция?
        if (x >= 0 and x < 8) and (y >= 0 and y < 8):   
            # если шашка находится слишком близко к 
            # низу или правому краю, то взятие в данном направлении невозможно
            if y < 6 and x < 6:
                # проверка нижнего правого угла

                # сначала выясняем, находится ли в нужном направлении
                # вражеская шашка. Затем проверяем клетку 'за ней'.
                # Если такая клетка свободна, то взятие возможно.
                if self.virtual_board[y + 1][x + 1] < 0 and \
                self.virtual_board[y + 2][x + 2] == 0:
                    self.positions.append((x+2, y+2))  
                    self.check_taking_steps_for_player(x+2, y+2)

            if y >= 2 and x < 6:
                # верхнего правого угла
                if self.virtual_board[y - 1][x + 1] < 0 and \
                self.virtual_board[y - 2][x + 2] == 0:
                    self.positions.append((x+2, y-2))
                    self.check_taking_steps_for_player(x+2, y-2)


            if y >= 2 and x >= 2:
                # верхнего левого угла
                if self.virtual_board[y - 1][x - 1] < 0 and \
                self.virtual_board[y - 2][x - 2] == 0:
                    self.positions.append((x-2, y-2))
                    self.check_taking_steps_for_player(x-2, y-2)

            if y < 6 and x >= 2:
                # нижнего левого угла
                if self.virtual_board[y + 1][x - 1] < 0 and \
                self.virtual_board[y + 2][x - 2] == 0:
                    self.positions.append((x-2, y+2))
                    self.check_taking_steps_for_player(x-2, y+2)

ex = Example(virtual_board)
#ex.check_taking_steps_for_player(0, 0)

Моя проблема в том, что программа просто-напросто зависает (она не справляется даже с этим примером, где вычислить нужно всего две позиции.) И это странно, ведь такая рекурсивная функция не предполагает слишком сильного углубления. В чем беда?

Источник: https://ru.stackoverflow.com/questions/1119712/%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5-%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B8-%D0%B2-%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B5-%D1%81%D0%BE%D0%B7%D0%B4%D0%B0%D0%BD%D0%B8%D1%8F-%D0%BF%D0%BE%D0%BB%D0%B5%D0%B9-%D0%B4%D0%BB%D1%8F-%D0%B1%D0%B8%D1%82%D1%8C%D1%8F-%D0%B2-%D1%88%D0%B0%D1%88%D0%BA%D0%B0%D1%85

Тебе может это понравится...

Добавить комментарий