Ход конем

Задача о ходе коня — задача о нахождении маршрута шахматного коня, проходящего через все поля доски по одному разу.

Эта задача известна по крайней мере с XVIII века. Леонард Эйлер посвятил ей большую работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию» (датируется 26 апреля 1757 года). В письме к Гольдбаху он сообщал: «…Воспоминание о предложенной когда-то мне задаче послужило для меня недавно поводом к некоторым тонким изысканиям, в которых обыкновенный анализ, как кажется, не имеет никакого применения… Я нашел, наконец, ясный способ находить сколько угодно решений (число их, однако, не бесконечно), не делая проб.» Помимо рассмотрения задачи для коня, Эйлер разобрал аналогичные задачи и для других фигур.

В терминах теории графов каждый маршрут коня, проходящий через все поля шахматной доски, соответствует гамильтонову пути (или циклу, если маршрут замкнутый) в графе, вершинами которого являются поля доски, и два поля соединены ребром, если с одного можно попасть на другое за один ход коня. Задача отыскания гамильтонова пути в графах является известной NP-полной задачей.

Количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно 13 267 364 410 532 [1] (количество замкнутых маршрутов с учётом направления в два раза больше). В то же время задача подсчёта всех возможных незамкнутых маршрутов значительно сложнее и не решена до сих пор. Известно, [2] что количество незамкнутых маршрутов не превышает числа сочетаний 1,2*10^47
Материал из Вики
Ну и флешка, почти на эту тему