Контрольные задания > 18. Доска имеет форму креста, который получается, если из квадратной доски 4x4 выкинуть угловые клетки (см. рис.). Можно ли обойти ее ходом шахматного коня и вернуться на исходное поле, побывав на всех полях ровно по разу? В ответе укажите 1, если это возможно, или 0, если невозможно.
Вопрос:
18. Доска имеет форму креста, который получается, если из квадратной доски 4x4 выкинуть угловые клетки (см. рис.). Можно ли обойти ее ходом шахматного коня и вернуться на исходное поле, побывав на всех полях ровно по разу? В ответе укажите 1, если это возможно, или 0, если невозможно.
В данном случае речь идет о задаче о гамильтоновом цикле. В данной конфигурации доски возможно обойти все клетки конем и вернуться в исходную клетку.
Ответ: 1