задачка об обходе шахматной доски конем.

← →
Bless © (2007-08-01 11:37) [0]

Если применить алгоритм без оптимизаций
(типа переборного решения с http://algolist.manual.ru/maths/combinat/knight.php), то сколько в самом худшем случае может потребоваться времени на обход на доске 8х8?

А то у меня программа (не та, что по ссылке, а самописная, но алгоритм по сути тот же), сволочь, на доске 5х5, 6х6, 7х7 отрабатывает за пару секунд максимум, а на 8х8 после получаса ожидания я задолбался ждать и вырубил ее. Оставил на работе на ночь, ограничив ее 40 000 000 000 ходов.
Не решила. Надо искать ошибку или теоретически такое возможно?
Можно ли определить теоретически минимальное число шагов, за которое задача гарантированно решится?

← →
TStas © (2007-08-01 11:43) [1]

Для 10х10 это игрушка известная получится. Её 100 раньше звали. Решений у нее дохрена. Пробовал решить в общем случае - не вышло.

← →
Bless © (2007-08-01 12:02) [2]

Че-то быстро вниз ушло. Подниму разок.

← →
Vlad Oshin © (2007-08-01 12:24) [3]

решал :)
суть - это задача Варнсдорфа, наскоко память неизменяет
достаточное(правда не доказанное) условие ставить коня так, чтоб он мог сделать как можно меньше(МЕНЬШЕ!, но не =0) ходов в следующий раз.

решал матрицей полей из 0-1
где был/небыл конь соответственно

исходник утерян, да и код все равно поругают мастера :), но смысл такой.

← →
TUser © (2007-08-01 12:26) [4]

> TStas © (01.08.07 11:43) [1]

Задача комивояжжера NP-полная. Эффективных алгоритмов в общем случае нет.

← →
Vlad Oshin © (2007-08-01 12:49) [5]

кстати по этому правилу конь обходил все доски размером выше 5х5
из любой начальной позиции

← →
Bless © (2007-08-01 12:53) [6]

> Vlad Oshin © (01.08.07 12:24) [3]
>
> решал :)
> суть - это задача Варнсдорфа, наскоко память неизменяет
>

Применение правила Варнсдорфа - это уже улучшение алгоритма, не подходит.
Меня интересует не готовое решение задачи и не улучшение его, а именно ответ на вопрос, за сколько ходов задача гарантированно решится при применение самого простого алгоритма с перебором всех возможных вариантов.
Т.е. это вопрос наверное больше к математикам, чем к программистам.
Единственная оценка сверху, что приходит на ум - это 8^63 ходов, что даже и оценкой-то не назовешь в силу ее огромности.

← →
Vlad Oshin © (2007-08-01 13:09) [7]

а что значит гарантированность? и кому она нужна?

вчера видел и математика и программиста - ужасно симпатичные человеки..
жаль времени не было познакомится.

← →
MBo © (2007-08-01 13:09) [8]

13 267 364 410 532 - количество замкнутых маршрутов коня на доске 8х8
http://mathworld.wolfram.com/KnightsTour.html

← →
Bless © (2007-08-01 13:15) [9]

> MBo © (01.08.07 13:09) [8]

О, спасибо, интересная ссылка!

← →
Думкин © (2007-08-01 14:18) [10]

У меня для поля 8*8 нашлось через 3 242 091 ход решение.

← →
Zeqfreed © (2007-08-01 15:41) [11]

Не знаю, та ли это задача, я писал программу для поиска максимального количества самонепересекающихся ходов коня по доске 8х8. Она находит решение в 20 ходов за 3 секунды при ограничении перебора 120000 конечных позиций. Т.к. работает без оптимизации абсолютно, то проверить на больших вариантах перебора у меня не получается, т.к. она занимает всю доступную память, хотя я и стараюсь ее освобождать при первой возможности :)

← →
Vlad Oshin © (2007-08-01 15:44) [12]

ну, чем мог, словом..
а напиши смысл (не код) твоей программы

← →
Bless © (2007-08-01 16:02) [13]

> Vlad Oshin © (01.08.07 15:44) [12]
>
> ну, чем мог, словом..
> а напиши смысл (не код) твоей программы

да смысл тот же, что и в переборном решении из ссылки, приведенной в [0]. Только у меня без рекурсии. И доска - не массив значений "занято/свободно", а массив пар значений "занято/свободно" и "сколько вариантов ходов из этой клетки сделано".

Кстати, если взять алгоритм, предложенный в [0] и поменять начальные координаты стартовой точки с (0,0) на (1,1), то тоже задумывается на минуты (окончания я не дождался).

← →
Думкин © (2007-08-01 19:18) [14]

> Bless © (01.08.07 16:02) [13]

А у тебя точно 8*8? Я взял код из ссылки по 0, и на Дельфи. У меня считается для 6,7,8. Для 5 решения нет. Для 9 начинает усиленно думать. Я тут прикидывал как можно снизить оценку для самых плохихи случаев. Для 5 вышло довольно близко, сейчас пробую прикинуть для 9, если там нет решения.
Поменял координаты с 0 на 1 - результат прежний.

← →
Sha © (2007-08-02 00:10) [15]

Для 8х8 решение быстро находится. Секунды в худшем случае, уж никак не вся ночь.

Было дело - пробовал решить эту задачу в общем случае. Могу подкинуть пару идей:
1. Удалось немного подкрутить Вансдорфа для досок большего размера.
2. Разрезанием доски задача легко решается (в смысле поиск одного решения)
для досок произвольного размера. Причем количество "базовых" досок
получается не таким уж большим.

← →
Petr V. Abramov © (2007-08-02 00:25) [16]

> 7х7 отрабатывает за пару секунд максимум, а на 8х8 после получаса ожидания я задолбался
как факториал чего растет кол-во вычислений???

← →
Sha © (2007-08-02 00:34) [17]

> Bless © (01.08.07 12:53) [6]
> ... за сколько ходов задача гарантированно решится при применение самого
> простого алгоритма с перебором всех возможных вариантов.

Совсем без оптимизамизации не пробовал.

← →
Sha © (2007-08-02 00:42) [18]

Petr V. Abramov © (02.08.07 00:25) [16]

Понятно, что время растет из-за увеличения количества и длины цепочек ходов, которые приходится откатывать. Вопрос в том как их оценить.

← →
Petr V. Abramov © (2007-08-02 01:10) [19]

> Sha © (02.08.07 00:42) [18]
да оно понятно.
смущает больно быстрый переход от 7 к 8. что ж должно факториалиться?

← →
Sha © (2007-08-02 01:19) [20]

> Petr V. Abramov © (02.08.07 01:10) [19]
> смущает больно быстрый переход от 7 к 8. что ж должно факториалиться?

Это ты о Вансдорфе или о переборе без оптимизации?
Если о Вансдорфе, то это стечение обстоятельств )

← →
Думкин © (2007-08-02 06:15) [21]

> Petr V. Abramov © (02.08.07 01:10) [19]

Да вы глухие нафиг. Я использовал тот самый ни разу НЕОПТИМИЗИРОВАННЫЙ алгоритм. Для 8 считается за секунду, для 7 кстати, чуток дольше при тех же начальных. Примерно в 4 раза.

Проблемы начинаются с 9*9, для этого алгоритма. Чего непонятно?

← →
Думкин © (2007-08-02 06:47) [22]

Да, про 5*5 - тоже находит, это ступил. Для 4*4 делает 17784 попытки двинуть коня - за пределы доски тоже считается, 6526 - за пределы доски не считается, но считается попытка двинуть на занятое, 2222 - только результативные ходы.
Считаются все попытки - и за пределы, и на занятое. Решение находится за:

5*5 - 280
6*6 - 43283
7*7 - 90178634
8*8 - 25936500

← →
Bless © (2007-08-02 09:53) [23]

> Думкин © (01.08.07 19:18) [14]
>
> > Bless © (01.08.07 16:02) [13]
>
> А у тебя точно 8*8? Я взял код из ссылки по 0, и на Дельфи.
> У меня считается для 6,7,8. Для 5 решения нет. Для 9 начинает
> усиленно думать... Поменял координаты с 0 на 1 - результат прежний.

Гм... А можно взглянуть исходник?
Изначально я компилировал пример из [0] на Borland C++ 3.2 (досовский).
После твоего поста перевел в делфи. Замена начальной точки с (0,0) на (1,1) уже в делфийском варианте точно так же, как и раньше "задумала" программу на 3 мин (дальше ждать не стал).

← →
Думкин © (2007-08-02 10:14) [24]

> Bless © (02.08.07 09:53) [23]

Скажи куда - пришлю.

← →
Bless © (2007-08-02 10:19) [25]

> Думкин © (02.08.07 10:14) [24]
>
> Скажи куда - пришлю.

bless [ав-ав] zeos . net

← →
Sha © (2007-08-02 10:32) [26]

> Думкин © (02.08.07 06:15) [21]
> Я использовал тот самый ни разу НЕОПТИМИЗИРОВАННЫЙ алгоритм.

Со случайным выбором очередного хода?

Иначе, если выбор очередного хода не случаен,
т.е. порядок просмотра возможных ходов коня фиксирован,
то алгоритм уже как-то оптимизирован.

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

ушло.

> Sha © (02.08.07 10:32) [26]

Я про по ссылке. Там порядок осмотра возможных ходов всегда одинаков и вписан в 2 массива.

Ничего случайного там нет. Он полностью детерминирован.

Кстати, можно посмотреть на торроидальные доски. Как там ситуация.

> Думкин © (02.08.07 10:39) [28]
> Я про по ссылке.
> Там порядок осмотра возможных ходов всегда одинаков и вписан в 2

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

> Думкин © (02.08.07 10:41) [29]
> Кстати, можно посмотреть на торроидальные доски. Как там ситуация.

Смотрел, ничего интересного )
Гораздо увлекательнее оказалось разобраться с разрезанием.

> Думкин © (02.08.07 10:38) [27]
> ушло.

Получил.
Ничего не меняя, получил те же что и в [22] результат для доски 8*8 - 25936500.
Поменял координаты на (1,1) (i:=1; j:=1 в обработчике bbClick).
Запустил, несколько минут подождал, после того, как количество ходов на экране ушло в минуса (переполнение), отрубил :)

> Bless © (02.08.07 11:12) [32]
> Запустил, несколько минут подождал, после того,
> как количество ходов на экране ушло в минуса (переполнение), отрубил :)

Так и должно быть, если в самом начале работы алгоритма
(ходу так примерно на 10м) образуются несвязные области,
обычно угловые поля.

Чтобы к ним потом вернуться, придется отменинить почти всю
проделанную работу, а это полный перебор всех решений
для 54х клеток - вечность.

> Sha © (02.08.07 10:48) [30]

Кучу решений - безусловно. Но разве речь шла о нахождении всех решений?
Насколько я понял, речь шла о нахождении хотя бы одного решения. А если решений нет, то из данной начальной позиции будут обойдены ВСЕ возможные пути. Если решение есть, то обход закончится в общем случае раньше.

> Bless © (02.08.07 11:12) [32]

Ну да, для 1 изменилось поведение, но я там чуток с утра изменил код. :)

> Sha © (02.08.07 10:52) [31]

Ты хочешь, чтобы для каждого возможног набора прыжков из позиции случайным образом формировался список прыжков, и при откате переходили к следующему в этом списке? Это можно.

> Думкин © (02.08.07 11:37) [34]
> Но разве речь шла о нахождении всех решений?

Нет, конечно.
Все дело в том как искать.

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

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

> Думкин © (02.08.07 11:41) [35]

Что-то типа этого.
Только ведь ясно, что это даже не стоит пытаться делать.
Время работы будет громадным.

Как выше для 4*4, если решения нет(выходим из угловой) число попыток
4*4 17784 6526 2222
5*5 13880632 6192754 1735078
6*6 ? > 6000000000

Как говорится, почувствуйте разницу. :)

>Время работы будет громадным.

То есть для 5 еще приемлемо. Для 6 возможно. Для 7 я уже не подпишусь.

задачка об обходе шахматной доски конем. Найти похожие ветки