Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.225.11.98] |
|
Страницы: (2) 1 [2] все ( Перейти к последнему сообщению ) |
Сообщ.
#16
,
|
|||||
|
итак. ето дело, конечно же, основано на поиске в глубину. но при полном переборе всех вариантов не удаётся за разумное время получить даже одно решение квадрата 9х9. но мы можем заметить, что: 1. если при ходе образуются клетки, из которых нельзя походить, и мы ещё не дошли до предпоследней клетки, то такой ход бесперспективен, ибо мы никогда не попадём в такую клетку, или напротив, сходим в неё и застрянем. ежели мы дошли до предпоследней клетки, то, понятное дело, такая клетка непременно образуется, и она будет последней. можно расширить сей критерий и сказать, что мы не будем рассматривать те ходы, при которых невозможно обойти конём все свободные клетки. такой критерий используется в horse7.exe, и, как показывает практика, не приносит особых дивидендов, к тому же считается медленно. 2. свободных клеток, из которых существует только один вариант хода, может быть не больше одной, или же вторая должна быть следующей на пути коня. например
понятно, что конь сходит в клетку, которая под ним, и обойдёт все четыре оставшихся клетки. а сейчас
конь остановится на распутье, и куда бы он ни пошёл, ему не суждено обойти все клетки.
понятное дело, она не ищет на каждом ходе все варианты путей из каждой клетки. существует специальный массив zakr[0..32, 0..32], в котором записывается число клеток, в которые конь не может походить из данной клетки (хотя было бы логичнее записывать число клеток, в которые он может походить). стало быть, на каждом шаге сей параметр изменяется только у восьми соседних с конём клеток, и на вышеописанные критерии надо проверять только их. |
Сообщ.
#17
,
|
|||||
|
бедный wormball я написал не в ту тему, повторюсь:
для 9х9 решения нет. |
Сообщ.
#18
,
|
|||||
|
ето если с приходом в ту же точку, а так есь:
можешь проверить на досуге
|
Сообщ.
#19
,
|
|
|
что "_так_есь_" я знаю
|
Сообщ.
#20
,
|
|||||||
|
Так последовательность ходов вроде получается циклической? Тогда переносим клетку с 1 в любую другую и последовательность снова останется циклической. Т.е. я хочу сказать, что если для начальной клетки (1, 1) удалось найти цикл по всем клеткам, то и для любой клетки (x, y) таковая тоже есть. PS: масло маслянное... |
Сообщ.
#21
,
|
|
|
А циклической в случай нечетного числа клеток она никогда не будет wormball же сказал, что конь ходит на клетку противоположного цвета (если брать цветА из шахмат), а на доске с нечетным числом клеток нельзя сделать так, чтобы конь вернулся.
А если цикл все же есть, как например на 8х8 тогда да. |
Сообщ.
#22
,
|
|
|
Я имел в виду классический случай 8 на 8.
Да, вот еще возник вопросик: а сколько всего способов обхода для поля NxN? Может, получиться найти математическую формулу, или тут тоько полный перебор? |