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