Damir_85,

1. Есть "правило Варнсдорфа" для досок небольшого размера.
2. Для досок произвольного размера - разрезание на более мелкие.

ZyK_BotaNAleksandr SharahovDamir_85,

2. Для досок произвольного размера - разрезание на более мелкие.

и кешировать результат.

Нет. Все гораздо проще.
1. Выбирается несколько размеров досок (далее - набор),
которыми можно некоторым стандартным образом (далее - способ)
покрыть любую доску, начиная с некоторого размера.
2. Для всех досок меньше этого некоторого размера решение
находится обычным способом (Вансдорф).
3. Для больших досок наш способ характеризуется не только тем,
как мы режем, но тем как выбираем входные-выходные точки
для досок из набора. Для каждой доски из набора (около 20 штук)
заранее находится одно решение с заданными точками.
4. После этого решение любой задачи довольно просто выполняется
за секунды. Для маленьких досок - Вансдорф, для больших - склейка
готовых решений из набора.

AkinaВместо поиска обхода малых поддосок проще использовать предопределённый закнутый путь обхода по доске 4*4 (их и склеивать проще, чем незамкнутые). В результате после разрезки на доски 4*4 останутся фрагменты с размерами сторон в пределах от 4 до 7, на которых Вансдорф емнип гарантированно не сбоит.
На досках средних размеров (до где-то 100) можно также построить произвольный максимальный путь по Вансдорфу, после чего закрыть пропущенные клетки (если таковые будут) методом Эйлера.

Проблема не в том, чтобы обойти малые доски.
Проблема в том, чтобы их правильно обойти,
чтобы можно было склеит один непрерывный путь коня.
И потом доказать, что ты решил эту задачу для доски любого размера.

AkinaAleksandr Sharahovчтобы можно было склеит один непрерывный путь коня.
И потом доказать, что ты решил эту задачу для доски любого размера.
Две выровненные доски 4*4 с кольцевым обходом гарантированно склеиваются в единый путь. Следовательно, любое количество склеивается в один обход. В принципе можно перебрать все прилегания (4*5, 4-6, 4*7) и показать, что они приклеиваются, аналогично можно перебрать все варианты приклеивания последней "угловой" доски. Соответственно не только будет доказано, что любая прямоугольная доска со сторонами не менее 4 без вырезов может быть обойдена, но и будет полностью построен аглгоритм нахождения пути обхода.

Это не доказательство.

У меня получилось, если не изменяет склероз, 18 типоразмеров досок.
Плюс строгое доказательство. Для четной доски строю замкнутый путь.

ZyK_BotaN,

Кеширование подраумевает временное хранение однажды
выданного результата и его последующую выдачу.

В данном случае это больше похоже на таблицу умножения,
которая используется при вычислении очередного результата.

Aleksandr SharahovУ меня получилось, если не изменяет склероз, 18 типоразмеров досок.


Склероз изменил. Сейчас посмотрел старые исходники.
Обход произвольной шахматной доски размерами 5x5 и более
выполняется путем разрезания доски на минидоски не более 4 типов.
Типы досок выбираются из множества 24 досок различных размеров:



Например, доска 11х11 собирается так

mayton,

Кусками 3*n и 4*n трудно оперировать,
они могут не иметь решения.

Damir_85,

начальное положение любое,
на правило это не влияет - оно ведь ничего не гарантирует )