Автор |
Сообщение |
|
|
Заголовок сообщения: |
Re: шесть коней |
|
|
Поправка: Можно лишь утверждать, что самый длинный путь не больше 667 ходов белыми и соответственно 667 ходов черными.
Поправка: Можно лишь утверждать, что [b]самый длинный[/b] путь не больше 667 ходов белыми и соответственно 667 ходов черными.
|
|
|
|
Добавлено: Пт мар 25, 2011 11:33 |
|
|
|
|
|
Заголовок сообщения: |
Re: шесть коней |
|
|
Ethereal писал(а): Все решения никому не нужны. Интересует одно, но самое длинное. Формального доказательства существования гамильтонова пути в графе не существует. Можно лишь утверждать, что такой путь не больше 667 ходов белыми и соответственно 667 ходов черными.
[quote="Ethereal"]Все решения никому не нужны. Интересует одно, но самое длинное.[/quote] Формального доказательства существования гамильтонова пути в графе не существует. Можно лишь утверждать, что такой путь не больше 667 ходов белыми и соответственно 667 ходов черными.
|
|
|
|
Добавлено: Пт мар 25, 2011 10:02 |
|
|
|
|
|
Заголовок сообщения: |
Re: шесть коней |
|
|
Ethereal писал(а): Все решения никому не нужны. Интересует одно, но самое длинное. Должно быть еще условие невозврата к пройденным позициям, иначе можно любое решение удлинить до бесконечности, делая бесконечно ходы туда-сюда.
[quote="Ethereal"]Все решения никому не нужны. Интересует одно, но самое длинное.[/quote] Должно быть еще условие невозврата к пройденным позициям, иначе можно любое решение удлинить до бесконечности, делая бесконечно ходы туда-сюда.
|
|
|
|
Добавлено: Сб мар 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 порядка быстрее вычислять одну траекторию чем у существующих решений (при более 'умном' переборе) все равно не получить все решения в приемлемое время.
[quote="Гость"]Нужно "положить" граф в память, каждая вершина которого одна из возможных позиций[/quote] Число всех позиций с помощью немного упрощенного генератора от garbler'a
[code]: 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 )[/code]
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)
[i]Так просто, из чистого любопытства[/i] За пару суток долбления с макс.глубиной 30 моя программа нашла решений : [code] Ходов : Решений 11+11 : 8 = 2 * (2 * 2) 13+13 : 234 = 2 * (3 * 3 * 13) 15+15 : 3348 = 2 * (2 * 3 * 3 * 3 * 31)[/code]
|
|
|
|
Добавлено: Пт мар 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 ходов не может бытьСнимем черных коней с доски. Введем понятие расстояния до нижней строчки доски : 23 2111 232 0 00 Видно, что белым коням, чтобы кратчайшим путем попасть на нижнюю строчку нужно минимум сделать 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 - это и есть такая симметричная пара.
Я тут подумал, что эту задачу можно поисследовать математически.
[b]1.) Докажем, что черные должны сделать столько же ходов, что и белые[/b] При каждом ходе конь меняет свой цвет. Дадим коню на черном поле вес ноль, а на белом - вес 1. Тогда вес всех коней в исходной позиции 3 и в конечной 3, т.е. и в исходной позиции он нечетный и в конечной нечетный. Ясно, что любой ход будет менять четность веса всех коней, поскольку вес ходящего коня будет или увеличиваться на 1 или уменьшаться на 1. Значит после хода белых вес всех коней стане четным, после хода черных - нечетным и так по кругу. В конечной позиции он нечетный, а значит конечная позиция будет достигнута после хода черными, а значит черные сделают столько-же ходов, что и белые. ЧТД
[b]2.) Докажем, что белые (а значит равно и черные) должны сделать нечетное число ходов.[/b] При каждом ходе конь меняет свой цвет. Дадим коню на черном поле вес ноль, а на белом - вес 1. В исходной позиции вес белых коней 1, т.е. нечетный. В конечной позиции вес белых коней 2, т.е. четный. На каждом ходу белых четность веса белых коней будеть меняться, поскольку вес белых коней будет увеличиваться на 1 или уменьшаться на 1. А значит, чтобы прийти в конечную позицию, белые (а значит равно и черные) должны сделать нечетное число ходов. ЧТД.
[b]Короче говоря все решения задачи имеют длину (2*n+1)+(2*n+1), где n-целое.[/b] Значит после решений в 11+11 и 13+13 ходов следует ожидать решений в 15+15 ходов.
[b]3.)Докажем без перебора, что решений менее чем в 9+9 ходов не может быть[/b] Снимем черных коней с доски. Введем понятие расстояния до нижней строчки доски : [b]2[/b]3[b]2[/b] 111 232 0[b]0[/b]0 Видно, что белым коням, чтобы кратчайшим путем попасть на нижнюю строчку нужно минимум сделать 2+3+2 = 7 ходов. Значит решений, более коротких чем 7+7 нет. Но оба белых коня, находящиеся в верхней строчке в выделенных жирным позициях не могут оба проти путь 2->1->0, поскольку тогда они должны будут оба попасть в одну и ту-же выделенную жирным позицию на нижней строчке. Один из белых коней не может пройти кратчайшим путем, значит он должен сделать минимум на ход больше. Значит белые должны сделать больше 7 ходов. Значит решения 7+7 не существует, а тогда решений, более коротких, чем 9+9 нет. ЧТД
[i]Вот как доказать без перебора, что решений в 9+9 тоже нет - не знаю.[/i]
[b]4.) Докажем, что всегда возможна зеркальная партия[/b] В начальной позиции верхние 6 и нижние 6 клеток являются зеркальными отображениями друг друга с инверсией цвета. Аналогично и в конечной позиции. Докажем, что если белые сделали ход, то черные всегда могут сделать зеркальный ход. Начальная позиция - зеркальная. Если черные будут делать ход, зеркальный ходу белых, то любая последующая позиция тоже будет зеркальная. Пусть i-я позиция зеркальная и ход белых. Белые сделали ход в клетку К. Поскольку до хода белых позиция была зеркальная то, до хода белых клетка, зеркальная клетке К, была пустой и для черных коней не под боем. Эта клетка не могла быть занята в результате хода белых, поскольку никакая клетка не зеркальна себе. Эта клетка не могла оказаться под боем для черных в результате хода белых, потому-что ни в какой клетке конь не бьет клетку зеркальную себе. А значит черные могут сделать зеркальный ход. И это для любой позиции. Значит возможна зеркальная партия. ЧТД.
[i]Вот как без перебора доказать, что найдется зеркальная партия, решающая задачу - пока не сообразил. С перебором-то такая партия отыскивается легко. Вот зеркальная партия из решения в 11+11 ходов, показаны только зеркальные позиции после ходов черными :[/i] [code]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[/code][i]Вообще говоря, я искал закономерности, позволяющие резко оптимизировать алгоритм по скорости и подобраться к обратной задаче - найти САМОЕ ДЛИННОЕ решение с неповторяющимися позициями. Но пока без результата. Зеркальные партии позволяют ходить только белыми, а ход черных идет автоматом. Но как доказать, что среди решений любой длины найдется зеркальное - не соображу. А обязательная нечетность ходов белыми в в решении может быть поможет перебирать сразу двойные ходы белыми[/i]
P.S. Поскольку исходная (да и конечная) позиции симметричны относительно вертикальной прямой, проходящей через центр доски, то [b]зеркальные партии должны существовать парами[/b]. Пара появится как только мы тронем белого коня в углу доски. Парная партия будет симметричной с ходом белым конем в другом углу доски. Собственно говоря, приведенные выше два решения 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 ходов, то возможно, что число ВСЕХ решений - астрономическое.
Короче говоря, задача сформулирована была неправильно ! Тут уже отмечали, что надо наложить требование, чтобы позиции в решении не повторялись, иначе количество решений просто бесконечно. Но дело даже не в этом. У этой задаче не 8 решений вообще, а 8 кратчайших решений. Их задача и должна была предлагать найти. А найти все решения - вообще малореальная задача. Возможно вообще нерешаемая в приемлемое время. У меня вот программа нашла решение в 210 ходов. И из соображений симметрии должно быть минимум еще одно той-же длины.
Вот я в своей программе положил ограничение - искать решения не длиннее чем в 22 хода : [code] 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 [/code]И она за три минуты находит 8 решений в 22 хода и что более коротких нет. Короче говоря, у меня получилось, что задача имеет 8 кратчайших решений в 22 хода (11 ходов белыми и 11 черными). Вот пример такого решения : [code]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 [/code]P.S. Если в программе положить максимальную длину решений в 26 ходов, то за пару часов она найдет 8 решений длиной 22 (11+11) хода и 234 решения длиной 26 (13+13) ходов и никаких других решений. Похоже, чем длиннее решения, тем больше у них вариантов, причем с ростом длины количество вариантов растет взрывообразно. А поскольку известно решение и в 210 ходов, то возможно, что число ВСЕХ решений - астрономическое.
|
|
|
|
Добавлено: Пн мар 14, 2011 20:55 |
|
|
|
|
|
Заголовок сообщения: |
Re: шесть коней |
|
|
В следующий раз так и сделаю. А пока - что вышло, то вышло. Так вот, у меня такое подозрение, что решений у этой задачи не восемь, а больше. Может быть коротких решений восемь. Просто я что-то не вижу ошибок в длинных решениях.
В следующий раз так и сделаю. А пока - что вышло, то вышло. Так вот, у меня такое подозрение, что решений у этой задачи не восемь, а больше. Может быть коротких решений восемь. Просто я что-то не вижу ошибок в длинных решениях.
|
|
|
|
Добавлено: Пн мар 14, 2011 19:58 |
|
|
|
|
|
Заголовок сообщения: |
Re: шесть коней |
|
|
Ethereal писал(а): Опять форум забыл, что я был залогинен. Можно скопировать свой гостевой пост в следующий (залогиенный) и отредактировать как надо, а гостевой потом удалить (модератора попросить, чтобы удалил).
[quote="Ethereal"]Опять форум забыл, что я был залогинен.[/quote]
Можно скопировать свой гостевой пост в следующий (залогиенный) и отредактировать как надо, а гостевой потом удалить (модератора попросить, чтобы удалил).
|
|
|
|
Добавлено: Пн мар 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. Хотя конечно идеология в моем решении - тупая. Банальный полный перебор вариантов. Весь вопрос как он был сделан.
Опять форум забыл, что я был залогинен. Пост выше получился от Гостя. Не отредактировать. А то из-за педантичности я обязательно бы вставил туда упоминание, что написано под 32-х разрядный форт. Пояснил бы, что индексы I,J в самых старших 8-и битах закодированной позиции означают, что данная позиция была получена ходом коня с I-й клетки на J-ю, причем I находится в более значащих 4-х разрядах, чем J. А поскольку объемлющий цикл поиска ходов перебирает I-е клетки с которых ходим, а вложенный перебирает J-e клетки на которые ходим, то свернутые в ячейку позиции на стеке в процессе перебора монотонно беззнаково возрастают. На этом и основано отсечение уже рассмотренных вариантов безо всяких графов и деревьев. Заменил бы "00 - пустая, 01 - черные, 02 - белые" на "00 - пустая, 01 - черные, 10 - белые". Заменил бы фразу "А на самой вершине стека - позиция, в которую ведет ход, который мы уже рассмотрели" на "А на самой вершине стека - позиция, в которую ведет ход, который мы рассматриваем или уже рассмотрели". Заменил бы фразу "Происходит откат на ход и проверяются еще нерассмотренные варианты на данном ходу." на "Происходит откат на ход и проверяются еще нерассмотренные варианты на предыдущем ходу."
P.S. Хотя конечно идеология в моем решении - тупая. Банальный полный перебор вариантов. Весь вопрос как он был сделан.
|
|
|
|
Добавлено: Пн мар 14, 2011 08:04 |
|
|
|
|