🎓 Снова шахматная задачка. Задача о ходе коня — задача о нахождении маршрута шахматного коня, проходящего через все поля доски по одному разу. Довольно известная и довольно сложная задача для общего случая!
#announcement #task_206
#announcement #task_206
Telegraph
Анонс #206. Обход доски конем
Задача: Постройте маршрут коня на доске размером 9×9, проходящий через каждую клетку доски ровно один раз. В этой задаче ровно один тест, входных данных нет никаких. Программа должна вывести 81 строку, в каждой строке должна быть указана координата одной…
👨🏻💻 В терминах теории графов каждый маршрут коня, проходящий через все поля шахматной доски, соответствует гамильтонову пути (или циклу, если маршрут замкнутый) в графе, вершинами которого являются поля доски, и два поля соединены ребром, если с одного можно попасть на другое за один ход коня.
Для доски 8 × 8 количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно 13 267 364 410 532.
#task_206 #cpp
Для доски 8 × 8 количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно 13 267 364 410 532.
#task_206 #cpp
Medium
UniLecs #Task. Chess Knight Tour
Задача: Постройте маршрут коня на доске размером 9×9, проходящий через каждую клетку доски ровно один раз.