0

Не так давно решил создать шашки на 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)

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

1 ответ 1

2

Перепрыгнув через вражескую шашку, своя смотрит в обратном направлении, и видит, что можно взять ту же самую - ведь она не убрана. И снова вперёд. И снова назад. Или по квадрату ходит. Вот и зациклились

Нужно удалять взятую шашку.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.