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

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ Сообщений: 58 ]  На страницу Пред.  1, 2, 3, 4  След.
Автор Сообщение
 Заголовок сообщения:
СообщениеДобавлено: Ср май 30, 2007 12:37 
Не в сети
Аватара пользователя

Зарегистрирован: Пт май 05, 2006 06:19
Сообщения: 192
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
из позиции 12 в 14, если сначала белый потом черный то все корректно,

_________________
SPF


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср май 30, 2007 12:58 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2109
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 36 раз.
rvm писал(а):
chess, a является ли решением следующее?

ygrek уже ответил. Кстати, ygrek единственный полностью решил эту задачу. Если бы он еще ввел понятие расстояния групп коней до конечной их позиции, то решение получалось бы быстро(без полного перебора).

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср май 30, 2007 13:11 
Белые ходят первыми. 13-ый ход, белые идут на чистое поле, 14-ый ход, черные тоже идут на чистое поле. mrack тоже подтверждает, что все верно :)

Код:
Если бы он еще ввел понятие расстояния групп коней до конечной их позиции, то решение получалось бы быстро(без полного перебора).
А как при этом убедиться, что никакой вариант не пропущен?


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср май 30, 2007 13:27 
Не в сети

Зарегистрирован: Чт май 04, 2006 18:18
Сообщения: 456
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
rvm, mrack, верно, если белые ходят первыми, то всё корректно. Ошибся.
Странно что у меня такой вариант не находится - надо разбираться...

rvm писал(а):
А как при этом убедиться, что никакой вариант не пропущен?

Просто в каждой точке сортировать варианты хода по этому критерию. Т.е. будут рассмотрены все варианты но в другом порядке.

_________________
http://forth.org.ru/~ygrek


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср май 30, 2007 13:39 
Если все варианты будут рассмотрены (или, число рассматриваемых вариантов тоже самое), то и время на это потребуется примерно тоже самое, не зависимо от порядка.


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср май 30, 2007 14:22 
Не в сети

Зарегистрирован: Чт май 04, 2006 18:18
Сообщения: 456
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
Логично. Т.е. для решения этой конкретной задачи такой финт ушами не поможет.
А если бы условие было найти любое решение, то это пригодится.

Кстати разобрался почему моя прога не находит этот 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!) на отсутствие повторяющихся позиций на доске, то существует бесконечное число решений :)

_________________
http://forth.org.ru/~ygrek


Последний раз редактировалось ygrek Ср май 30, 2007 14:38, всего редактировалось 1 раз.

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср май 30, 2007 14:36 
Не в сети
Аватара пользователя

Зарегистрирован: Пт май 05, 2006 06:19
Сообщения: 192
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
фиг знает, нет времени разбираться дальше
алгоритм дубовый, обход последовательный, должен работать,
находит три решения (находит решения в 134 138 и 170 ходов ) , по нахождении решения история ходов являются описанием решения, потом уходит в дебри вариантов и хз
вывод на экран можно и порубить,

_________________
SPF


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср май 30, 2007 14:43 
О, спасибо! Обновил в репозитории. Вобчем, требуется текущий образ из cvs, включая сборку SPF на текущих исходника (пофиксены некоторые баги).


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср май 30, 2007 15:01 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2109
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 36 раз.
Закодировал черных - 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 нашел все самые короткие решения.

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср май 30, 2007 15:12 
Не в сети

Зарегистрирован: Чт май 04, 2006 18:18
Сообщения: 456
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
Задача о мостах тут совершенно ни при чём.

_________________
http://forth.org.ru/~ygrek


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср май 30, 2007 15:34 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2109
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 36 раз.
ygrek писал(а):
Задача о мостах тут совершенно ни при чём.

Согласен, не совсем то. Скажем модифицированная задача о мостах. :)
Нужно найти все возможные проходы от начального моста (начальной позиции) до конечного моста(конечной позиции), не разу не пройдя дважды по одному и тому же мосту(не попав дважды в одинаковую позицию.
На языке теории графов - найти все пути от одной вершины заданного графа до другой без возвратов в уже пройденные вершины.

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср май 30, 2007 20:51 
ygrek писал(а):
У profit'а находится только 5 вариантов.

Надо увеличить глубину перебора:

Код:
50 CONSTANT MAX-MOVES \ максимальное кол-во ходов в переборе


Тогда находит 8 решений.


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


Ни тебе списков, ни тебе бакфортов.
Вообще даже переменных никаких нет ! Ни одной !
Все шахматные позиции хранятся на стеке, упакованные в ячейку.
Одна ячейка - одна позиция. Содержимое стека - история игры !

На самом дне стека лежит ноль. Стек хранит промежуточные позиции
в игре. А на верху стека важны два элемента. Второй сверху - это
позиция в которой мы играем. А на самой вершине стека - позиция,
в которую ведет ход, который мы уже рассмотрели.

Позиция кодируется так. Под одну клетку доски отводится два бита.
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


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

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

P.S. Хотя конечно идеология в моем решении - тупая. Банальный полный
перебор вариантов. Весь вопрос как он был сделан.


Последний раз редактировалось Ethereal Вт мар 15, 2011 01:01, всего редактировалось 12 раз(а).

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

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


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

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


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

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


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

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