Графовый алгоритм с участием шахмат: возможные пути за k ходов

Я пытаюсь решить проблему алгоритма, связанную с шахматами.

Предположим, у меня есть король на A8, и я хочу переместить его на H1 (только с разрешенными ходами). Как я могу узнать, сколько возможностей (путей) есть для любых заданных k ходов? (например, сколько есть путей/возможностей, если я хочу переместить короля с A8 на H1 за 15 ходов?)

Одно тривиальное решение состоит в том, чтобы рассматривать это как задачу с графом и использовать любой стандартный алгоритм поиска пути, считая каждый ход стоимостью 1. Итак, допустим, я хочу переместить своего короля с A8 на H1 за 10 ходов. Я бы просто искал все пути, сумма которых равна 10.

Мой вопрос в том, есть ли другие более умные и эффективные способы сделать это? Мне также было интересно, может ли быть что-то более «математическое» и простое, чтобы найти это число, а не такое «алгоритмическое» и «подобное грубой силе»?


algorithm graph-algorithm chess
person Proghero    schedule 04.06.2012    source источник
comment
Здесь нужно быть очень осторожным с целочисленным переполнением. 15 ходов переполнят 32 бита, а 25 ходов переполнят 64 бита.   -  person n. 1.8e9-where's-my-share m.    schedule 04.06.2012

Ответы (3)


arrow_upward
3
arrow_downward

Это простая задача динамического программирования O(N^3).

Просто назначьте 3D-массив следующим образом:

Пусть Z[x][y][k] будет количеством ходов из k шагов, чтобы добраться до места назначения из позиции (x,y) на доске.

Базовые случаи:

foreach x in 0 to 7,
   foreach y in 0 to 7,
       Z[x][y][0] = 0 // forall x,y: 0 ways to reach H1 from
                      // anywhere else with 0 steps

Z[7][7][0] = 1 // 1 way to reach H1 from H1 with 0 steps

Рекурсивный случай:

foreach k in 1 to K,
   foreach x in 0 to 7,
      foreach y in 0 to 7,
          Z[x][y][k+1] = Z[x-1][y][k]
              + Z[x+1][y][k]
              + Z[x][y-1][k]
              + Z[x][y+1][k]
              + ...; // only include positions in
                     // the summation that are on the board
                     // and that a king can make

Тогда ваш ответ:

return Z[0][0][K]; // number of ways to reach H1(7,7) from A8(0,0) with K moves

(Есть более быстрый способ сделать это за O (n ^ 2), разложив ходы на два набора горизонтальных и вертикальных перемещений, а затем объединив их и умножив на количество чередований.)

См. этот связанный вопрос и ответ: Нет способов ходить M шагов в сетке

person Andrew Tomazos    schedule 04.06.2012
comment
Незначительное: мне кажется, что самая внешняя итерация должна быть foreach k in 0 to K-1. - person kavinyao; 18.10.2014

arrow_upward
3
arrow_downward

Вы можете использовать матрицу смежности. Если такую ​​матрицу умножить на себя, то получится количество путей от точки к точке. Пример:

График: полный график K3: A‹->B‹->C‹->A

Матрица:

[0 ; 1 ; 1]
[1 ; 0 ; 1]
[1 ; 1 ; 0]

Пути для длины 2: M * M

[2 ; 1 ; 1]
[1 ; 2 ; 1]
[1 ; 1 ; 2]

Тогда длина 3 будет M * M * M

[2 ; 3 ; 3]
[3 ; 2 ; 3]
[3 ; 3 ; 2]
person Slomo    schedule 04.06.2012
comment
Одна из возможных проблем с этим методом (который, я думаю, я видел в учебниках) заключается в том, что для больших графов требуемая память станет O((rows*columns)^2), и, таким образом, также время для каждого итерация. Однако, если у вас есть хорошо написанная библиотека разреженных матриц (может быть, numpy?), то, вероятно, она должна хорошо обобщаться. - person ninjagecko; 04.06.2012
comment
Ты прав. Он также вычисляет гораздо больше, чем просто пути от A до B. Он вычисляет все возможности от каждой начальной точки до каждой конечной точки за N ходов. Однако в случае обычного шахматного поля 8x8 это не должно быть серьезной проблемой. Кроме того, это может быть хорошо распараллелено. - person Slomo; 04.06.2012
comment
Я не думаю, что есть способ вычислить все возможности от начальной до каждой конечной точки за N ходов. (Если вы говорите о проблеме насыщения, это кажется довольно незначительным.) Я просто имел в виду проблему, заключающуюся в том, что шахматная доска не является полным графом, и поэтому существует чрезвычайно большое количество нулевых элементов. - person ninjagecko; 04.06.2012

arrow_upward
0
arrow_downward 

.......E <-end
........
........
........
........
........
........
S....... <-start

К сожалению, вы не можете использовать «любой стандартный алгоритм поиска пути», потому что ваши пути могут не быть кратчайшими путями. Вам нужно будет специально использовать наивный поиск, который учитывает все пути (например, в глубину или в ширину).

Однако, поскольку вам все равно, как вы попали на плитку, вы можете использовать технику, называемую динамическим программированием. Для каждого местоположения (i,j) количество способов добраться туда за n изменяется (назовем его waysi,j(n)) это:

способыi,j(n) = способыi-1,j(n-1) + способыi+1,j (n-1) + способыi,j-1(n-1) + способыi,j+1(n-1) + способыi+ 1,j+1(n-1) + способыi-1,j+1(n-1) + способыi+1,j-1(n-1) + способыi-1,j-1(n-1)

То есть король может сходить с любой из соседних клеток за 1 ход:

путиi,j(n) = суммаneighbours(i,j)(waysneighbor(n-1))

Таким образом, вы бы сделали, например, в python:

SIZE = 8

cache = {}
def ways(pos, n):
    r,c = pos  # row,column
    if not (0<=r<SIZE and 0<=c<SIZE):
        # off edge of board: no ways to get here
        return 0
    elif n==0:
        # starting position: only one way to get here
        return 1 if (r,c)==(0,0) else 0
    else:
        args = (pos,n)
        if not args in cache:
            cache[args] = ways((r-1,c), n-1) + ways((r+1,c), n-1) + ways((r,c-1), n-1) + ways((r,c+1), n-1) + ways((r-1,c-1), n-1) + ways((r+1,c-1), n-1) + ways((r+1,c-1), n-1) + ways((r+1,c+1), n-1)
        return cache[args]

Демо:

>>> ways((7,7), 15)
1074445298

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

>>> cache
{}
>>> ways((1,0), 1)
1
>>> cache
{((1, 0), 1): 1}
>>> ways((1,1), 2)
2
>>> cache
{((0, 1), 1): 1, ((1, 2), 1): 0, ((1, 0), 1): 1, ((0, 0), 1): 0, ((2, 0), 1): 0, ((2, 1), 1): 0, ((1, 1), 2): 2, ((2, 2), 1): 0}
>>> ways((2,1), 3)
5
>>> cache
{((1, 2), 1): 0, ((2, 3), 1): 0, ((2, 0), 2): 1, ((1, 1), 1): 1, ((3, 1), 1): 0, ((4, 0), 1): 0, ((1, 0), 1): 1, ((3, 0), 1): 0, ((0, 0), 1): 0, ((2, 0), 1): 0, ((2, 1), 1): 0, ((4, 1), 1): 0, ((2, 2), 2): 1, ((3, 3), 1): 0, ((0, 1), 1): 1, ((3, 0), 2): 0, ((3, 2), 2): 0, ((3, 2), 1): 0, ((1, 0), 2): 1, ((4, 2), 1): 0, ((4, 3), 1): 0, ((3, 1), 2): 0, ((1, 1), 2): 2, ((2, 2), 1): 0, ((2, 1), 3): 5}

(В python также можно использовать декоратор @cached или @memoized, чтобы не писать весь код в последнем блоке else:. В других языках есть другие способы автоматического выполнения мемоизации.)

Вышеупомянутый подход был нисходящим. Иногда он может создавать очень большие стеки (ваш стек будет расти с n). Если вы хотите быть сверхэффективным, чтобы избежать ненужной работы, вы можете использовать восходящий подход, когда вы моделируете все позиции, в которых может быть король, на 1 шаг, 2 шага, 3 шага, ...:

SIZE = 8
def ways(n):
    grid = [[0 for row in range(8)] for col in range(8)]
    grid[0][0] = 1

    def inGrid(r,c):            
        return all(0<=coord<SIZE for coord in (r,c))
    def adjacentSum(pos, grid):
        r,c = pos
        total = 0
        for neighbor in [(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)]:
            delta_r,delta_c = neighbor
            (r2,c2) = (r+delta_r,c+delta_c)
            if inGrid(r2,c2):
                total += grid[r2][c2]
        return total

    for _ in range(n):
        grid = [[adjacentSum((r,c), grid) for r in range(8)] for c in range(8)]
        # careful: grid must be replaced atomically, not element-by-element

    from pprint import pprint
    pprint(grid)
    return grid

Демо:

>>> ways(0)
[[1, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0]]

>>> ways(1)
[[0, 1, 0, 0, 0, 0, 0, 0],
 [1, 1, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0]]

>>> ways(2)
[[3, 2, 2, 0, 0, 0, 0, 0],
 [2, 2, 2, 0, 0, 0, 0, 0],
 [2, 2, 1, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0]]

>>> ways(3)
[[6,  11, 6, 4, 0, 0, 0, 0],
 [11, 16, 9, 5, 0, 0, 0, 0],
 [6,  9,  6, 3, 0, 0, 0, 0],
 [4,  5,  3, 1, 0, 0, 0, 0],
 [0,  0,  0, 0, 0, 0, 0, 0],
 [0,  0,  0, 0, 0, 0, 0, 0],
 [0,  0,  0, 0, 0, 0, 0, 0],
 [0,  0,  0, 0, 0, 0, 0, 0]]

>>> ways(4)
[[38, 48, 45, 20, 9,  0, 0, 0],
 [48, 64, 60, 28, 12, 0, 0, 0],
 [45, 60, 51, 24, 9,  0, 0, 0],
 [20, 28, 24, 12, 4,  0, 0, 0],
 [9,  12, 9,  4,  1,  0, 0, 0],
 [0,  0,  0,  0,  0,  0, 0, 0],
 [0,  0,  0,  0,  0,  0, 0, 0],
 [0,  0,  0,  0,  0,  0, 0, 0]]
person ninjagecko    schedule 04.06.2012
comment
Король ходит не так. - person n. 1.8e9-where's-my-share m.; 04.06.2012
comment
@n.m.: о, упс... исправлено. К счастью, это была домашняя работа, и все же было очевидно, как применить задачу к случаю с королем. - person ninjagecko; 05.06.2012