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

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ Сообщений: 58 ]  На страницу Пред.  1, 2, 3, 4
Автор Сообщение
 Заголовок сообщения: Re: шесть коней
СообщениеДобавлено: Пн мар 14, 2011 18:22 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
Ethereal писал(а):
Опять форум забыл, что я был залогинен.


Можно скопировать свой гостевой пост в следующий (залогиенный) и отредактировать как надо, а гостевой потом удалить (модератора попросить, чтобы удалил).

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: шесть коней
СообщениеДобавлено: Пн мар 14, 2011 19:58 
В следующий раз так и сделаю. А пока - что вышло, то вышло.
Так вот, у меня такое подозрение, что решений у этой задачи не восемь, а больше.
Может быть коротких решений восемь.
Просто я что-то не вижу ошибок в длинных решениях.


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения: Re: шесть коней
СообщениеДобавлено: Пн мар 14, 2011 20:55 
Не в сети
Аватара пользователя

Зарегистрирован: Ср фев 23, 2011 20:42
Сообщения: 600
Откуда: Карелия
Благодарил (а): 3 раз.
Поблагодарили: 24 раз.
Короче говоря, задача сформулирована была неправильно !
Тут уже отмечали, что надо наложить требование, чтобы позиции в
решении не повторялись, иначе количество решений просто бесконечно.
Но дело даже не в этом. У этой задаче не 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 ходов,
то возможно, что число ВСЕХ решений - астрономическое.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: шесть коней
СообщениеДобавлено: Ср мар 16, 2011 22:18 
Не в сети
Аватара пользователя

Зарегистрирован: Ср фев 23, 2011 20:42
Сообщения: 600
Откуда: Карелия
Благодарил (а): 3 раз.
Поблагодарили: 24 раз.
Я тут подумал, что эту задачу можно поисследовать математически.

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
- это и есть такая симметричная пара.


Последний раз редактировалось Ethereal Чт мар 17, 2011 03:27, всего редактировалось 4 раз(а).

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: шесть коней
СообщениеДобавлено: Ср мар 16, 2011 22:28 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Самое длинное решение с неповторяющимися позициями можно, конечно, вывести из вообще, общего числе возможных позиций, которое ограничено невозможностью нападения и может быть очерёдностью ходов, потом, сокращая позиции, которые нельзя получить одна из другой..


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: шесть коней
СообщениеДобавлено: Чт мар 17, 2011 09:37 
Все эти теор. исследования ни к чему.
Нужно "положить" граф в память, каждая вершина которого одна из возможных позиций и начать проводить траектории по его ребрам из начальной
позиции в конечную, пока эти траектории не закончатся. Здесь будет перебор, но не тупой перебор. Информацию о пройденных траекториях нужно
оставлять в "графской" памяти.


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения: Re: шесть коней
СообщениеДобавлено: Пт мар 18, 2011 01:04 
Так просто, из чистого любопытства
За пару суток долбления с макс.глубиной 30 моя программа нашла решений :
Код:
Ходов : Решений
11+11 : 8    = 2 * (2 * 2)
13+13 : 234  = 2 * (3 * 3 * 13)
15+15 : 3348 = 2 * (2 * 3 * 3 * 3 * 31)


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения: Re: шесть коней
СообщениеДобавлено: Пт мар 18, 2011 01:09 
Не в сети
Аватара пользователя

Зарегистрирован: Ср фев 23, 2011 20:42
Сообщения: 600
Откуда: Карелия
Благодарил (а): 3 раз.
Поблагодарили: 24 раз.
Как видишь, число решений растет взрывообразно, а значит длинных решений -
астрономическое количество, перебор которых займет нереальное время.
Поэтому просто ползать по графам можно будет до скончания века.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: шесть коней
СообщениеДобавлено: Пт мар 18, 2011 13:49 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Гость писал(а):
Нужно "положить" граф в память, каждая вершина которого одна из возможных позиций

Число всех позиций с помощью немного упрощенного генератора от 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 порядка быстрее вычислять одну траекторию чем у существующих решений (при более 'умном' переборе)
все равно не получить все решения в приемлемое время.

_________________
С уважением, chess


Последний раз редактировалось chess Пт мар 25, 2011 09:56, всего редактировалось 1 раз.

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: шесть коней
СообщениеДобавлено: Сб мар 19, 2011 13:16 
Не в сети
Аватара пользователя

Зарегистрирован: Ср фев 23, 2011 20:42
Сообщения: 600
Откуда: Карелия
Благодарил (а): 3 раз.
Поблагодарили: 24 раз.
Все решения никому не нужны. Интересует одно, но самое длинное.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: шесть коней
СообщениеДобавлено: Сб мар 19, 2011 15:26 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
Ethereal писал(а):
Все решения никому не нужны. Интересует одно, но самое длинное.

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

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: шесть коней
СообщениеДобавлено: Пт мар 25, 2011 10:02 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Ethereal писал(а):
Все решения никому не нужны. Интересует одно, но самое длинное.

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

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: шесть коней
СообщениеДобавлено: Пт мар 25, 2011 11:33 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Поправка:
Можно лишь утверждать, что самый длинный путь не больше 667 ходов белыми и соответственно 667 ходов черными.

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 58 ]  На страницу Пред.  1, 2, 3, 4

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


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 11


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

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