Forth http://fforum.winglion.ru/ |
|
шесть коней http://fforum.winglion.ru/viewtopic.php?f=19&t=740 |
Страница 3 из 4 |
Автор: | mrack [ Ср май 30, 2007 12:37 ] |
Заголовок сообщения: | |
из позиции 12 в 14, если сначала белый потом черный то все корректно, |
Автор: | chess [ Ср май 30, 2007 12:58 ] |
Заголовок сообщения: | |
rvm писал(а): chess, a является ли решением следующее?
ygrek уже ответил. Кстати, ygrek единственный полностью решил эту задачу. Если бы он еще ввел понятие расстояния групп коней до конечной их позиции, то решение получалось бы быстро(без полного перебора). |
Автор: | rvm [ Ср май 30, 2007 13:11 ] |
Заголовок сообщения: | |
Белые ходят первыми. 13-ый ход, белые идут на чистое поле, 14-ый ход, черные тоже идут на чистое поле. mrack тоже подтверждает, что все верно Код: Если бы он еще ввел понятие расстояния групп коней до конечной их позиции, то решение получалось бы быстро(без полного перебора). А как при этом убедиться, что никакой вариант не пропущен?
|
Автор: | ygrek [ Ср май 30, 2007 13:27 ] |
Заголовок сообщения: | |
rvm, mrack, верно, если белые ходят первыми, то всё корректно. Ошибся. Странно что у меня такой вариант не находится - надо разбираться... rvm писал(а): А как при этом убедиться, что никакой вариант не пропущен?
Просто в каждой точке сортировать варианты хода по этому критерию. Т.е. будут рассмотрены все варианты но в другом порядке. |
Автор: | rvm [ Ср май 30, 2007 13:39 ] |
Заголовок сообщения: | |
Если все варианты будут рассмотрены (или, число рассматриваемых вариантов тоже самое), то и время на это потребуется примерно тоже самое, не зависимо от порядка. |
Автор: | ygrek [ Ср май 30, 2007 14:22 ] |
Заголовок сообщения: | |
Логично. Т.е. для решения этой конкретной задачи такой финт ушами не поможет. А если бы условие было найти любое решение, то это пригодится. Кстати разобрался почему моя прога не находит этот 13-ходовый вариант - я запрещаю каждому коню ходить в уже посещённую позицию. А правильно (с точки зрения нахождения _всех_ вариантов) конечно запрещать повторение позиций. Так что моё решение неполное У profit'а находится только 5 вариантов. Реализация by mrack пишет много букв и не понятно находит ли ответ rvm, ваша реализация ругается Код: Exception #2 at: D:\WORK\FORTH\spf4\devel\~pinka/spf/compiler/control-stack.f:33:57:
S" ~pinka/samples/2006/model/zstack.immutable.f INCLUDED ^ -2003 WORD OR FILE NOT FOUND Итого, задачка всё ещё не решена, не так ли? Хотя конечно если не наложить ограничение (в условии, sic!) на отсутствие повторяющихся позиций на доске, то существует бесконечное число решений |
Автор: | mrack [ Ср май 30, 2007 14:36 ] |
Заголовок сообщения: | |
фиг знает, нет времени разбираться дальше алгоритм дубовый, обход последовательный, должен работать, находит три решения (находит решения в 134 138 и 170 ходов ) , по нахождении решения история ходов являются описанием решения, потом уходит в дебри вариантов и хз вывод на экран можно и порубить, |
Автор: | rvm [ Ср май 30, 2007 14:43 ] |
Заголовок сообщения: | |
О, спасибо! Обновил в репозитории. Вобчем, требуется текущий образ из cvs, включая сборку SPF на текущих исходника (пофиксены некоторые баги). |
Автор: | chess [ Ср май 30, 2007 15:01 ] |
Заголовок сообщения: | |
Закодировал черных - 1,белых -2, пустое поле - 0 Решение rvm выглядит так. Код: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 111 111 011 011 001 001 000 000 001 201 201 201 201 201 000 020 020 022 022 022 122 102 102 100 100 102 002 002 000 000 010 010 011 211 211 211 201 201 200 000 001 201 222 022 022 002 002 000 000 002 002 002 102 102 102 100 14 15 16 17 18 19 20 21 22 23 24 25 26 201 201 201 221 221 221 220 020 020 220 220 222 222 012 010 010 010 000 002 102 102 112 112 010 010 000 201 201 200 000 000 000 000 020 020 000 020 000 000 000 020 120 120 121 101 101 101 001 001 011 011 111 если каждую позицию решения представить числом, то Код: 111000000222 0
111020000022 1 011020010022 2 011022010002 3 001022011002 4 001022211000 5 000122211000 6 000102211002 7 001102201002 8 201100201002 9 201100200102 10 201102000102 11 201002001102 12 201002201100 13 201012201000 14 201010201020 15 201010200120 16 221010000120 17 221000000121 18 221002000101 19 220102000101 20 020102020101 21 020112020001 22 220112000001 23 220010020011 24 222010000011 25 222000000111 26 Ни одного одинакового числа нет - значит это решение правильное. Можно посчитать сколько всего таких троичных чисел может быть(с учетом ограничений на соседство 1 и 2 в связанных позициях). Это будет общее число разных позиций, из каждой позиции есть выход в несколько других. Отсюда получаем задачу о мостах Эйлера. А исходная задача - да, получается не решена. Ygrek нашел все самые короткие решения. |
Автор: | ygrek [ Ср май 30, 2007 15:12 ] |
Заголовок сообщения: | |
Задача о мостах тут совершенно ни при чём. |
Автор: | chess [ Ср май 30, 2007 15:34 ] |
Заголовок сообщения: | |
ygrek писал(а): Задача о мостах тут совершенно ни при чём.
Согласен, не совсем то. Скажем модифицированная задача о мостах. Нужно найти все возможные проходы от начального моста (начальной позиции) до конечного моста(конечной позиции), не разу не пройдя дважды по одному и тому же мосту(не попав дважды в одинаковую позицию. На языке теории графов - найти все пути от одной вершины заданного графа до другой без возвратов в уже пройденные вершины. |
Автор: | profiT [ Ср май 30, 2007 20:51 ] |
Заголовок сообщения: | |
ygrek писал(а): У profit'а находится только 5 вариантов.
Надо увеличить глубину перебора: Код: 50 CONSTANT MAX-MOVES \ максимальное кол-во ходов в переборе
Тогда находит 8 решений. |
Автор: | Гость [ Пн мар 14, 2011 07:56 ] |
Заголовок сообщения: | Re: шесть коней |
Ни тебе списков, ни тебе бакфортов. Вообще даже переменных никаких нет ! Ни одной ! Все шахматные позиции хранятся на стеке, упакованные в ячейку. Одна ячейка - одна позиция. Содержимое стека - история игры ! На самом дне стека лежит ноль. Стек хранит промежуточные позиции в игре. А на верху стека важны два элемента. Второй сверху - это позиция в которой мы играем. А на самой вершине стека - позиция, в которую ведет ход, который мы уже рассмотрели. Позиция кодируется так. Под одну клетку доски отводится два бита. 00 - пустая, 01 - черные, 02 - белые. Итого 24 бита. Самые старшие 8 бит ячейки это индексы циклов I,J при которых мы эту позицию рассматривали (по 4 бита на индекс). Поэтому все еще нерассмотренные позиции по отношению к данной будут, как число, беззнаково больше, чем рассмотренные. В результате простым беззнаковым сравнением можно отделить все рассмотренные позиции на данном ходу от нерассмотренных. Чтобы не повторить позицию, встречавшуюся уже на предыдущих ходах просматривается стек на всю глубину с помощью PICK пока не встретится ноль, который помечает дно стека. Если найден ход, то на стек просто кладется ноль (новая позиция становаится текущей и такой, в которой еще ни один ход не разобран). Если все ходы в текущей позиции разобраны, возможных ходов больше нет или все они ведут к тем позициям, что уже были раньше, то со стека отбрасывается верхний элемент. Происходит откат на ход и проверяются еще нерассмотренные варианты на данном ходу. Короче говоря, программа работает и даже мгновенно находит три решения (в 94, 98 и 210 ходов), а потом погрязает в долгих вычислениях и мне таки было лень дожидаться конца рассчетов. Но досчитает, ни куда не денется. Программа написана только CORE-овыми словами. Никаких либ не требует. Выводит решения в наглядном виде - в виде шахматных досок со сменяющимися позициями. Алгоритмы в ней - сплошной вынос мозга ;-) Код: 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 - черные 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 0 ELSE DROP THEN REPEAT \ 2DROP DECIMAL \ Вернем контекст к исходному виду, если нужно ; 0 PACK 0 MAIN BYE |
Автор: | Ethereal [ Пн мар 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. Хотя конечно идеология в моем решении - тупая. Банальный полный перебор вариантов. Весь вопрос как он был сделан. |
Автор: | Ethereal [ Пн мар 14, 2011 08:04 ] |
Заголовок сообщения: | Re: шесть коней |
А все таки любопытно, почему у всех решения получились разные. |
Страница 3 из 4 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |