Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 13:42

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Ответить
Имя пользователя:
Заголовок:
Текст сообщения:
Введите текст вашего сообщения. Длина сообщения в символах не более: 60000

Размер шрифта:
Цвет шрифта
Настройки:
BBCode ВКЛЮЧЕН
[img] ВЫКЛЮЧЕН
[flash] ВЫКЛЮЧЕН
[url] ВКЛЮЧЕН
Смайлики ВЫКЛЮЧЕНЫ
Отключить в этом сообщении BBCode
Не преобразовывать адреса URL в ссылки
Вопрос
Теперь гостю придется вводить здесь пароль. Не от своей учетной записи, а ПАРОЛЬ ДЛЯ ГОСТЯ, получить который можно после регистрации на форуме через ЛС.:
Этот вопрос предназначен для выявления и предотвращения автоматических регистраций.
   

Обзор темы - шесть коней
Автор Сообщение
  Заголовок сообщения:  Re: шесть коней  Ответить с цитатой
Поправка:
Можно лишь утверждать, что самый длинный путь не больше 667 ходов белыми и соответственно 667 ходов черными.
Сообщение Добавлено: Пт мар 25, 2011 11:33
  Заголовок сообщения:  Re: шесть коней  Ответить с цитатой
Ethereal писал(а):
Все решения никому не нужны. Интересует одно, но самое длинное.

Формального доказательства существования гамильтонова пути в графе не существует.
Можно лишь утверждать, что такой путь не больше 667 ходов белыми и соответственно 667 ходов черными.
Сообщение Добавлено: Пт мар 25, 2011 10:02
  Заголовок сообщения:  Re: шесть коней  Ответить с цитатой
Ethereal писал(а):
Все решения никому не нужны. Интересует одно, но самое длинное.

Должно быть еще условие невозврата к пройденным позициям, иначе можно любое решение удлинить до бесконечности, делая бесконечно ходы туда-сюда.
Сообщение Добавлено: Сб мар 19, 2011 15:26
  Заголовок сообщения:  Re: шесть коней  Ответить с цитатой
Все решения никому не нужны. Интересует одно, но самое длинное.
Сообщение Добавлено: Сб мар 19, 2011 13:16
  Заголовок сообщения:  Re: шесть коней  Ответить с цитатой
Гость писал(а):
Нужно "положить" граф в память, каждая вершина которого одна из возможных позиций

Число всех позиций с помощью немного упрощенного генератора от garbler'a

Код:
: pos? ( a u -- tf ) u! a!  0 tf!  \ 1 - есть позиция 0 - нет позиции
  a u 1- + a DO I C@ I 1+ C@ + '1' '2' + = IF 1 is tf LEAVE THEN LOOP
  f( a + C@ SWAP a + C@ + '1' '2' + = )
  0 5 f  3 8 f OR  6 11 f OR  tf OR 0= ;

0 VALUE cntpos \ счетчик позиций

: (cswap) ( a1 a2 --> )  2DUP 2>R C@ SWAP C@ R> C! R> C! ;

: (cnotfind) ( c s2 s1 --> t/f )  1 -ROT ?DO OVER I C@ = IF 0 AND LEAVE THEN LOOP NIP ;

: (variants) ( s2 s1 str len --> s2 s1' str len )
  2>R 2DUP - 1 < IF 2R> 2DUP pos? IF cntpos 1+ TO cntpos THEN EXIT THEN
  DUP >R BEGIN 2DUP > WHILE DUP C@ OVER R@ (cnotfind)
               IF DUP R@ (cswap) R> 1+ SWAP 2R> ROT >R RECURSE
                  R> -ROT 2>R SWAP 1- >R DUP R@ (cswap)
               THEN  1+
         REPEAT DROP R> 2R>  ;

: variants ( asc # --> n )  2DUP 2>R OVER + SWAP 2R> (variants) 2DROP 2DROP cntpos . CR ;


S" 111000000222" variants  ( 1334 = 667 + 667 )


ps.
Отсюда и получается оценка длины максимального решения.
число траекторий получается грубо в интервале 2^1334.
Даже если на 3 порядка быстрее вычислять одну траекторию чем у существующих решений (при более 'умном' переборе)
все равно не получить все решения в приемлемое время.
Сообщение Добавлено: Пт мар 18, 2011 13:49
  Заголовок сообщения:  Re: шесть коней  Ответить с цитатой
Как видишь, число решений растет взрывообразно, а значит длинных решений -
астрономическое количество, перебор которых займет нереальное время.
Поэтому просто ползать по графам можно будет до скончания века.
Сообщение Добавлено: Пт мар 18, 2011 01:09
  Заголовок сообщения:  Re: шесть коней  Ответить с цитатой
Так просто, из чистого любопытства
За пару суток долбления с макс.глубиной 30 моя программа нашла решений :
Код:
Ходов : Решений
11+11 : 8    = 2 * (2 * 2)
13+13 : 234  = 2 * (3 * 3 * 13)
15+15 : 3348 = 2 * (2 * 3 * 3 * 3 * 31)
Сообщение Добавлено: Пт мар 18, 2011 01:04
  Заголовок сообщения:  Re: шесть коней  Ответить с цитатой
Все эти теор. исследования ни к чему.
Нужно "положить" граф в память, каждая вершина которого одна из возможных позиций и начать проводить траектории по его ребрам из начальной
позиции в конечную, пока эти траектории не закончатся. Здесь будет перебор, но не тупой перебор. Информацию о пройденных траекториях нужно
оставлять в "графской" памяти.
Сообщение Добавлено: Чт мар 17, 2011 09:37
  Заголовок сообщения:  Re: шесть коней  Ответить с цитатой
Самое длинное решение с неповторяющимися позициями можно, конечно, вывести из вообще, общего числе возможных позиций, которое ограничено невозможностью нападения и может быть очерёдностью ходов, потом, сокращая позиции, которые нельзя получить одна из другой..
Сообщение Добавлено: Ср мар 16, 2011 22:28
  Заголовок сообщения:  Re: шесть коней  Ответить с цитатой
Я тут подумал, что эту задачу можно поисследовать математически.

1.) Докажем, что черные должны сделать столько же ходов, что и белые
При каждом ходе конь меняет свой цвет.
Дадим коню на черном поле вес ноль, а на белом - вес 1.
Тогда вес всех коней в исходной позиции 3 и в конечной 3, т.е.
и в исходной позиции он нечетный и в конечной нечетный.
Ясно, что любой ход будет менять четность веса всех коней,
поскольку вес ходящего коня будет или увеличиваться на 1
или уменьшаться на 1. Значит после хода белых вес всех
коней стане четным, после хода черных - нечетным и так по кругу.
В конечной позиции он нечетный, а значит конечная позиция будет
достигнута после хода черными, а значит черные сделают столько-же
ходов, что и белые. ЧТД

2.) Докажем, что белые (а значит равно и черные) должны сделать нечетное число ходов.
При каждом ходе конь меняет свой цвет.
Дадим коню на черном поле вес ноль, а на белом - вес 1.
В исходной позиции вес белых коней 1, т.е. нечетный.
В конечной позиции вес белых коней 2, т.е. четный.
На каждом ходу белых четность веса белых коней будеть меняться,
поскольку вес белых коней будет увеличиваться на 1 или уменьшаться на 1.
А значит, чтобы прийти в конечную позицию, белые (а значит равно и
черные) должны сделать нечетное число ходов. ЧТД.

Короче говоря все решения задачи имеют длину (2*n+1)+(2*n+1), где n-целое.
Значит после решений в 11+11 и 13+13 ходов следует ожидать решений
в 15+15 ходов.

3.)Докажем без перебора, что решений менее чем в 9+9 ходов не может быть
Снимем черных коней с доски.
Введем понятие расстояния до нижней строчки доски :
232
111
232
000
Видно, что белым коням, чтобы кратчайшим путем попасть на нижнюю
строчку нужно минимум сделать 2+3+2 = 7 ходов. Значит решений, более
коротких чем 7+7 нет. Но оба белых коня, находящиеся в верхней строчке
в выделенных жирным позициях не могут оба проти путь 2->1->0, поскольку
тогда они должны будут оба попасть в одну и ту-же выделенную жирным
позицию на нижней строчке. Один из белых коней не может пройти
кратчайшим путем, значит он должен сделать минимум на ход больше. Значит
белые должны сделать больше 7 ходов. Значит решения 7+7 не существует,
а тогда решений, более коротких, чем 9+9 нет. ЧТД

Вот как доказать без перебора, что решений в 9+9 тоже нет - не знаю.

4.) Докажем, что всегда возможна зеркальная партия
В начальной позиции верхние 6 и нижние 6 клеток являются зеркальными
отображениями друг друга с инверсией цвета. Аналогично и в конечной позиции.
Докажем, что если белые сделали ход, то черные всегда могут сделать
зеркальный ход. Начальная позиция - зеркальная. Если черные будут
делать ход, зеркальный ходу белых, то любая последующая позиция тоже
будет зеркальная. Пусть i-я позиция зеркальная и ход белых.
Белые сделали ход в клетку К. Поскольку до хода белых позиция была
зеркальная то, до хода белых клетка, зеркальная клетке К, была пустой
и для черных коней не под боем. Эта клетка не могла быть занята
в результате хода белых, поскольку никакая клетка не зеркальна себе.
Эта клетка не могла оказаться под боем для черных в результате хода
белых, потому-что ни в какой клетке конь не бьет клетку зеркальную себе.
А значит черные могут сделать зеркальный ход. И это для любой позиции.
Значит возможна зеркальная партия. ЧТД.

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

Код:
222 220 200 000 200 201 201 001 000 001 011 111
000 010 110 112 102 002 100 102 122 022 020 000
000 020 220 221 201 001 200 201 211 011 010 000
111 110 100 000 100 102 102 002 000 002 022 222
Вообще говоря, я искал закономерности, позволяющие резко оптимизировать
алгоритм по скорости и подобраться к обратной задаче - найти САМОЕ ДЛИННОЕ
решение с неповторяющимися позициями. Но пока без результата.
Зеркальные партии позволяют ходить только белыми, а ход черных идет
автоматом. Но как доказать, что среди решений любой длины найдется
зеркальное - не соображу. А обязательная нечетность ходов белыми в
в решении может быть поможет перебирать сразу двойные ходы белыми


P.S. Поскольку исходная (да и конечная) позиции симметричны относительно
вертикальной прямой, проходящей через центр доски, то зеркальные партии
должны существовать парами
. Пара появится как только мы тронем белого
коня в углу доски. Парная партия будет симметричной с ходом белым конем
в другом углу доски. Собственно говоря, приведенные выше два решения 11+11
- это и есть такая симметричная пара.
Сообщение Добавлено: Ср мар 16, 2011 22:18
  Заголовок сообщения:  Re: шесть коней  Ответить с цитатой
Короче говоря, задача сформулирована была неправильно !
Тут уже отмечали, что надо наложить требование, чтобы позиции в
решении не повторялись, иначе количество решений просто бесконечно.
Но дело даже не в этом. У этой задаче не 8 решений вообще,
а 8 кратчайших решений. Их задача и должна была предлагать найти.
А найти все решения - вообще малореальная задача.
Возможно вообще нерешаемая в приемлемое время.
У меня вот программа нашла решение в 210 ходов.
И из соображений симметрии должно быть минимум еще одно той-же длины.

Вот я в своей программе положил ограничение - искать решения не длиннее чем в 22 хода :
Код:
CREATE BOARD   \ Доска
2 C, 2 C, 2 C, \ 2 - белые
0 C, 0 C, 0 C, \ 0 - пусто
0 C, 0 C, 0 C,
1 C, 1 C, 1 C, \ 1 - черные

DECIMAL 22 ( макс.число ходов в решении ) 1+ 1+ CONSTANT MAX-DEPTH

HEX
: WB DEPTH 1 AND 1+ ; ( -- x ) \ Вовращает: 2 - ход белых, 1 - ход черных
: HORSE? ( i j -- flag ) \ Возвращает TRUE если ход i->j есть ход конем
  OVER 3 MOD OVER 3 MOD - ABS ROT 3 / ROT 3 / - ABS * 2 =
;
: PACK ( -- x ) \ Упаковка позиции с доски
  0 C 0 DO 2* 2* BOARD I + C@ 3 AND + LOOP
;
: UNPACK ( x -- ) \ Распаковка позиции на доску
  0 B DO DUP 3 AND BOARD I + C! 2/ 2/ TRUE +LOOP DROP
  WB 3 XOR C 0 DO \ Цикл заполняет 4-ками пустые позиции под боем на данном ходу
    DUP BOARD I + C@ =
    IF
      C 0 DO
        BOARD I + C@ 0= IF J I HORSE? IF 4 BOARD I + C! THEN THEN
      LOOP
    THEN
  LOOP DROP
;

: TURN ( -- ) \ Найден новый ход - THROW ,не найден и нужен откат - EXIT
  WB C 0 DO
    DUP BOARD I + C@ =
    IF
      C 0 DO
        BOARD I + C@ 0=
        IF
          J I HORSE?
          IF
            0 BOARD J + C! DUP BOARD I + C!
            PACK J 1C LSHIFT + I 18 LSHIFT + SWAP >R 2DUP U<
            IF
              NIP PACK 54002A =
              IF
                ." Solution in " DEPTH 2 - DECIMAL . ." turns :" CR CR 4 BASE !
                0 DEPTH 3 - DO
                  I PICK 0 <# # # # A HOLD D HOLD # # # A HOLD
                  D HOLD # # # A HOLD D HOLD # # # #> TYPE CR CR
                TRUE +LOOP
              ELSE
                2 BEGIN
                  1+ 2DUP PICK DUP 0= THROW XOR FFFFFF AND 0=
                UNTIL DROP
              THEN
            ELSE DROP
            THEN
            OVER UNPACK R>
          THEN
        THEN
      LOOP
    THEN
  LOOP DROP
;

: MAIN
  BEGIN
    OVER
  WHILE
    OVER UNPACK
    ['] TURN CATCH IF DEPTH MAX-DEPTH < IF 0 ( глубже ) THEN ELSE DROP ( откат ) THEN
  REPEAT
\ 2DROP DECIMAL \ Вернем контекст к исходному виду, если нужно
;

0 PACK 0 MAIN BYE
И она за три минуты находит 8 решений в 22 хода и что более коротких нет.
Короче говоря, у меня получилось, что задача имеет 8 кратчайших
решений в 22 хода (11 ходов белыми и 11 черными).
Вот пример такого решения :
Код:
Solution in 22 turns :

222
000
000
111

022 022 002 002 000 000 002 002 002 102 102
000 010 010 011 211 211 211 201 201 200 000
020 020 022 022 022 122 102 102 100 100 102
111 011 011 001 001 000 000 001 201 201 201

102 100 100 100 000 000 100 100 110 110 111
001 201 201 221 221 221 220 020 020 000 000
002 002 102 102 112 110 110 110 010 010 000
201 201 200 000 000 200 200 220 220 222 222
P.S. Если в программе положить максимальную длину решений в 26 ходов,
то за пару часов она найдет 8 решений длиной 22 (11+11) хода и 234 решения
длиной 26 (13+13) ходов и никаких других решений. Похоже, чем длиннее
решения, тем больше у них вариантов, причем с ростом длины количество
вариантов растет взрывообразно. А поскольку известно решение и в 210 ходов,
то возможно, что число ВСЕХ решений - астрономическое.
Сообщение Добавлено: Пн мар 14, 2011 20:55
  Заголовок сообщения:  Re: шесть коней  Ответить с цитатой
В следующий раз так и сделаю. А пока - что вышло, то вышло.
Так вот, у меня такое подозрение, что решений у этой задачи не восемь, а больше.
Может быть коротких решений восемь.
Просто я что-то не вижу ошибок в длинных решениях.
Сообщение Добавлено: Пн мар 14, 2011 19:58
  Заголовок сообщения:  Re: шесть коней  Ответить с цитатой
Ethereal писал(а):
Опять форум забыл, что я был залогинен.


Можно скопировать свой гостевой пост в следующий (залогиенный) и отредактировать как надо, а гостевой потом удалить (модератора попросить, чтобы удалил).
Сообщение Добавлено: Пн мар 14, 2011 18:22
  Заголовок сообщения:  Re: шесть коней  Ответить с цитатой
А все таки любопытно, почему у всех решения получились разные.
Сообщение Добавлено: Пн мар 14, 2011 08:04
  Заголовок сообщения:  Re: шесть коней  Ответить с цитатой
Опять форум забыл, что я был залогинен. Пост выше получился от Гостя.
Не отредактировать. А то из-за педантичности я обязательно бы вставил
туда упоминание, что написано под 32-х разрядный форт.
Пояснил бы, что индексы I,J в самых старших 8-и битах закодированной позиции
означают, что данная позиция была получена ходом коня с I-й клетки на J-ю,
причем I находится в более значащих 4-х разрядах, чем J.
А поскольку объемлющий цикл поиска ходов перебирает I-е клетки с которых ходим,
а вложенный перебирает J-e клетки на которые ходим, то свернутые в ячейку
позиции на стеке в процессе перебора монотонно беззнаково возрастают. На этом
и основано отсечение уже рассмотренных вариантов безо всяких графов и деревьев.
Заменил бы "00 - пустая, 01 - черные, 02 - белые" на "00 - пустая, 01 - черные, 10 - белые".
Заменил бы фразу
"А на самой вершине стека - позиция, в которую ведет ход, который мы уже рассмотрели"
на
"А на самой вершине стека - позиция, в которую ведет ход, который мы рассматриваем или уже рассмотрели".
Заменил бы фразу
"Происходит откат на ход и проверяются еще нерассмотренные варианты на данном ходу."
на
"Происходит откат на ход и проверяются еще нерассмотренные варианты на предыдущем ходу."

P.S. Хотя конечно идеология в моем решении - тупая. Банальный полный
перебор вариантов. Весь вопрос как он был сделан.
Сообщение Добавлено: Пн мар 14, 2011 08:04

Часовой пояс: UTC + 3 часа [ Летнее время ]


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB