Головоломки, подобные этим, насчитывают полтысячелетия. В 1512 году итальянец Гуарини (Guarini di Forli) предложил задачу, которая часто приводится в книгах по занимательной математике: "В углах шахматной доски 3´3 стоят два белых и два черных коня. Необходимо поменять их местами за наименьшее число ходов". Мы предложим вам несколько более трудных задач, используя доски причудливых конфигураций.
Первая скачка
Задача 1: переставить красного коня с поля с1 на поле с3. Черные и белые кони при этом должны вернуться на свои места (18 ходов).
Задача 2: поменять местами белых и черных коней. Красный конь при этом должен вернуться на свое поле (34 хода).
Вторая скачка
Доска имеет более привычную прямо-угольную форму, но поля b2 и d2 (помеченные косой штриховкой) на ней отсутствуют.
Задача: поменять местами белых и черных коней. Красные кони при этом должны вернуться на свои поля (36 ходов). Постройте граф и найдите решение.
Третья скачка
Задача 1: переставить красного коня с поля b2 на поле с3. Черные и белые кони при этом должны вернуться на свои места.
Задача 2: поменять местами белых и черных коней. Красный конь при этом должен вернуться на свое поле.
Постройте граф и найдите решение.