Доска имеет форму креста, который получается, если из квадратной доски 4x4 выкинуть угловые клетки (см. рис.). Можно ли обойти ее ходом шахматного коня и вернуться на исходное поле, побывав на всех полях ровно по разу? В ответе укажите 1, если это возможно, или 0, если невозможно.
Чтобы найти нужный путь, можно занумеровать клетки доски (см. рис. 1) и построить граф, в котором вершины соответствуют клеткам, а ребра соединяют вершины согласно ходам коня (см. рис. 2). На полученном графе построим такой обход, начав, к примеру, с нижней левой точки, имеющей номер 11. Построив обход на графе, перенесем полученную последовательность ходов обратно на доску. Шаги обхода указаны числами от 1 в нижнем левом углу до 12 приведен на рис. 3.
Ответ: можно.