Задача "Шашки", питон

Вам нужно написать код или вы не знаете какой алгоритм применить? Если второе, то мне кажется, это можно решить динамическим программированием. Динамикой будет число путей в конкретную клетку. Если мы рассчитаем кол-во путей для всех клеток, то ответом будет сумма путей для клеток верхней горизонтали.
Будем считать, что нижняя горизонталь - 1я строка матрицы 8х8. Все элементы матрицы равны 0. Когда мы получили координаты шашки, присваиваем соответствующему элементу матрицы 1. Затем обходим матрицу построчно начиная с 2ой строки. Каждой клетке присваиваем сумму нижних диагональных клеток (откуда мы можем дойти к текущей клетке). В конце работы алгоритма в 8ой строке будут клетки с количеством путей, которыми можно до них дойти. Нам нужно их просуммировать и это будет ответом.

Ну, считай. Примерно так (для черной):
__X__ (шашка)
_1_1_ (2 клетки по одному способу)
1_2_1 (3 клетки по 2 способа)
и т. д.
2 в центре - сумма единичек сверху по диагоналям от нее.
Тебе нужна сумма последней строки.

>> Сколькими способами она может пройти в дамки?
Одним. После прохода в дамки шашкой она уже не станет, поэтому пройти снова в дамки не сможет.

k,s = list(map(int, input().split()))
w=[[0]*10 for i in range(10)]
w[s][k]=1
for i in range(s+1,9):
for j in range(1,9):
w[i][j]=w[i-1][j-1]+w[i-1][j+1]
print(sum(w[8]))

Заведём матрицу размерами 10*10 и обнулим значения во всех ячейках.
Пусть наша доска располагается в прямоугольнике с индексами диагональных вершин A[1][1] и A[8][8]
(индексация ведётся с 0).
Позиции вида A[8][j], где 0 < j < 9 являются тупиковыми, поэтому ответом для таких ячеек является 1.
Чтобы заполнить остальные ячейки массива будем последовательно спускаться на одну строку вниз
(i: от 7 до 1) и для каждой ячейки этой строки (j: от 1 до 8) A[i][j] = A[i-1][j-1] + A[i-1][j+1].
Ответ хранится в ячейке с координатами, подающимися на вход.

Отметим, что использование массива 10*10 вместо 8*8 освобождает нас от обязанности смотреть: является
ли текущая ячейка граничной.