Теоретический материал

Задача о расстановке коней

На этот раз на шахматной доске n×n нужно подсчитать количество способов расставить k коней так, чтобы они не били друг друга.

Мы уже привыкли, что профиль -- битовая карта столбца левее bi. Но здесь этой информации мало, так как кони могут прыгать сразу через два столбца. Поэтому профиль должен описывать два соседних столбца.

Для двух профилей pr1 = $ \langle$p1, p2$ \rangle$ (p1 -- битовая карта первого столбца, p2 -- второго) и pr2 = $ \langle$p'1, p'2$ \rangle$ положим d[pr1, pr2] = 1 если и только если

a)
p2 = p'1;
б)
кони не бьют друг друга.

В противном случае d[pr1, pr2] = 0.

Таким образом, переходов на порядок меньше, чем количество профилей. Всего профилей 4n, а из каждого профиля получается менее 2n новых за счет совпадения p2 и p1'. Другими словами, матрица D сильно разрежена (имееет много нулевых элементов).

Поэтому в задаче о расстановки коней можно добиться значительного ускорения (по сравнению с шаблонным алгоритмом), если хранить D в виде "списков смежности": D'[pr1] -- список всех таких pr2, из которых можно получить pr1, то есть d[pr2][pr1] = 1. В этом случае формула (2) будет выглядеть так:

a[i, p] = $\displaystyle \sum_{t \in D'[p]}^{}$a[i - 1, t] d[t, p].

Суммарное время вычисления a[i] равно количеству всевозможных переходов, то есть количество ненулевых элементов в D. В нашем случае (задаче о конях) их не более 4n×2n = 8n, то есть время работы алгоритма с такой оптимизацией будет O(8nm) -- это в 2n раз меньше, чем время стандартного алгоритма.