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,

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

Damir_85Ура! Седня проверил алгоритм быстро работает даже на доске 80 на 80)
правда если размерность 90 на 90 в проге уже возникает ошибка Stack Overflow но это уже не важно ) меня устраивает и размерность 80 на 80 завтра вот проверю еще диапазон от 80 до 90 посмотрю какая максимальная размерность поддерживается алгоритмом
небольшой вопрос: я хочу проверить алгоритм на прямоугольной доске N*M седня пару тестов запустил на доске 80 на 60 решения не нашел
Есть у вас какие нибудь тесты с найденными решениями на прямоугольных досках дайте пожалуйста размерность досок и номера полей с которых запускали а то я че то перебирал поля пока положительный тест не обнаружил ну т.е чтобы решение было
и второй вопрос например при обходе доски ферзем правило Варнсдорфа также даст сокращение перебора или здесь уже без разницы прямой перебор или с Варнсдорфом?

Stack Overflow - ты че-то глубоко забрался )
Во-первых, рекурсия не нужна тут.
Во-вторых, подумай о других оптимизациях, маленькие хитрости могут существенно экономить время.
Решение Вансдорфом (без склеек) для доски 1000х1000 находится примерно за секунду.
А насчет ферзя ты, конечно, пошутил, да?

> Кстати что это за склейки?

Про разрезание доски (т.е. решение при помощи склеивания решений для мелких досок) см. выше.


> алгоритм который у меня просто ищет поле откуда можно сделать минимальное кол-во ходов

У Варнсдорфа есть тонкость - какое из полей с одинаковым весом выбрать. Тут простор для твоих подправил.


> дайте какие ниибудть тесты которые дают решение

Да просто бери любую доску, например, квадрат или прямоугольник со стороной 5 или больше. Там всегда есть решение.
Более того, если произведение сторон четное - есть замкнутый путь. Его проще искать, если начинать из центра.


> а насчет ферзя

Просто змейкой ходи - вот и все правило.