путь коня - головоломка

Hа Чессбеисе недавно опубликовали ( http://chessbase.com/newsdetail.asp?newsid=5720 ) интересную головоломку Мехрдада Пахлеванзаде (может и до него было такое, ну это неважно)

Cколько разных путей у коня с c3 на e5 (или с f3 на d5, в общем по диагонали на две клетки)?

Bроде нетрудно, а вот постарайтесь вручную посчитать Hаверное можно для компа написать алгоритм, но как упражнение для счетчиков сгодится. Алгоритм как таковой тоже интересен.

Вперед!

phisey

Скорее нет. Но зависит что вы подразумеваете под "записью" - зарисовки или просто нотацию? А так, думаю что для разных уровней (=разрядов, званий) можно поставить разные ограничения. Гросс по идее должен строго в уме решить. Я например и с доской и бумажкой полчаса мучаюсь

Очевидно бесконечное счетное число
c3-e4-g5-f7-e5
c3-e4-g5-f7-g5-f7-e5
c3-e4-g5-f7-g5-f7-g5-f7-e5
c3-e4-g5-f7-g5-f7-g5-f7-g5-f7-e5
...

Количество, конечно, на порядок меньше, чем 8*8*8*8. Во-первых, как минимум, назад конем вернутсья не вариант, так что уже 8*7*6*5, а еще можно за два (три) хода так далеко упрыгнуть от цели, что до финальной точки не дойти (Это продемонстрировать проще на доске n х m, а на стандартной просто возможных ходов на краю доски меньше. в этом, в общем-то и состоит задача

ре: повышение мастерства

Думаю, что для счетного мастерства может сгодится, а так неважно, просто интересно решить


прав:

Mustitz, хорошая шутка речь, разумеется, строго о 4-х ходовых маршрутах.

Это не шутка. А вот ваше уточнение существенно меняет задачу.

Для пары c3 e5 конь после первого хода могу располагаться так:



Далее, на два года конь может передвигаться разными спобобами. Перечислим их.

Непосредственно по диагонали:

Таких пар восемь, переходов по диагонали два. Итого 16

Через клетку

Таких пар две, переходов два. Итого 4

Ходом жирафа

Таких пар шесть, перехода два, итого 12

По диагонали через две клетки

Вариантов два, переходов две, итого 4

И двойной ход всадника

Вариантов восемь, переход один, итого 8

Суммируем 16 + 4 + 12 + 4 + 8 = 44

У меня другое решение, считал тупо с бумажкой вслепую очень сложно решить, запутаться очень легко. Пока не скажу решение, может кто хочет еще побаловаться.

Так надо как-то систематизировать...

Так Вы практически все сделали: на первой диаграмме перебрать всех белых коней и найти (в лоб) все разные 2-х ходовые пути, оканчивающиеся на полях черных коней .
Да, с учетом симметрии достаточно 4-х над диагональю a1-h8.

Надо начать с более простой задачи - сколько способов перемещения коня в 2 хода между двумя полями одного цвета. Это очень просто: может быть 0, 1 или 2 варианта перемещения, Mustitz перечислил выше все возможности.

С с3 до e5 четыре хода, т.е. 2 плюс 2. Теперь надо перебрать все варианты для промежуточного черного поля.

Например, промежуточное поле b2 дает 2*2=4 варианта (2 варианта перейти с c3 до b2 и 2 варианта с b2 до e5). Для других полей аналогично, все нетрудно перебрать в уме не глядя на доску. Если использовать симметрию, то перебор можно сократить. В итоге:
a3 - 2*1=2 варианта, a7 - 1*1=1 вариант,
b2 - 2*2=4 варианта, b4 - 2*2=4 варианта, b6 - 2*2=4 варианта,
c1 - 2*1=2 варианта, c5 - 2*2=4 варианта,
d2 - 2*2=4 варианта, d4 - 2*2=4 варианта, d6 - 2*2=4 варианта,
e3 - 2*2=4 варианта, e7 - 1*2=2 варианта,
f2 - 2*2=4 варианта, f4 - 2*2=4 варианта, f6 - 2*2=4 варианта,
g1 - 1*1=1 вариант, g5 - 1*2=2 варианта,
Всего 54.