Forth :: Просмотр темы - шесть коней

Прежде чем пускать в ход тяжелую артиллерию, неплохо сначала подумать.
Задача элементарно решается методом пуговиц и нитей без всякого компьютера.
См. "Наука и жизнь", № 5, 1977.

Всё таки как решать эту задачку методом ниток и пуговиц?
Там задача и тут задача - принципиально разные.

И есть условие на "битые поля". То есть надо следить чтобы соседние узлы не были заняты вражеским цветом. По-моему вручную даже после такого преобразования решение не очевидно и надо руками двигать и смотреть. Ну а программа просто реализует это двигание.

Автор:	chess [ Пн май 14, 2007 14:52 ]
Заголовок сообщения:	шесть коней
Найти все решения для такой chess-задачки(с помощью Форта конечно): Поменять местами белых коней с черными, путем поочередных ходов сначала одним из белых коней, затем одним из черных коней и т.д., при этом коней нельзя ставить на клетки, которые находятся под ударом коней другого цвета.

Автор:	mrack [ Пн май 14, 2007 21:57 ]
Заголовок сообщения:
фигасе... /me впал в задумчивость

Автор:	WingLion [ Пн май 14, 2007 22:09 ]
Заголовок сообщения:
Вручную оно как-то решается быстрее, чем с помощью Форта

Автор:	вопрос [ Пн май 14, 2007 23:46 ]
Заголовок сообщения:
ну, тут важен алгоритм

Автор:	ygrek [ Вт май 15, 2007 16:55 ]
Заголовок сообщения:
Ну и кто разберёт эту тарабарщину? <pre> STARTLOG REQUIRE write-list ~ygrek/lib/list/all.f \ Размерности 3 VALUE nx 4 VALUE ny \ пакуем две координаты в один CELL : xy ( x y -- p ) 16 LSHIFT OR ; : p ( p -- x y ) DUP 16 RSHIFT SWAP 0xFFFF AND SWAP ; : xy. SWAP . . ; \ Пара - позиция и "история посещений" : xy% %[ xy DUP % %[ % ]% %l ]% %l ; \ начальные позиции %[ 0 0 xy% 1 0 xy% 2 0 xy% ]% VALUE b %[ 0 3 xy% 1 3 xy% 2 3 xy% ]% VALUE w \ конечные позиции %[ 0 0 xy % 1 0 xy % 2 0 xy % ]% VALUE w-fin %[ 0 3 xy % 1 3 xy % 2 3 xy % ]% VALUE b-fin \ ход игры () VALUE bpath () VALUE wpath \ ----------------------------------------------------------------------- : position car ; : position! setcar ; : history cdar ; : history! cdr setcar ; : history-add >R vnode R@ history cons R> history! ; : history-dec >R R@ history cdr R> history! ; : position-member? LAMBDA{ position OVER = } SWAP list-find NIP NIP ; : poswrite LAMBDA{ ." ( " p xy. ." ) " } SWAP mapcar ; : pwrite LAMBDA{ CR DUP position p xy. ." ( " history LAMBDA{ ." [ " p xy. ." ] " } SWAP mapcar ." ) " } SWAP mapcar ; : bwprint CR ." Black : " b pwrite CR ." White : " w pwrite ; : tablewrite { w b -- } ny 0 DO CR nx 0 DO I J xy w member? IF ." W" ELSE I J xy b member? IF ." B" ELSE ." ." THEN THEN LOOP LOOP ; : pathwrite LAMBDA{ CR poswrite } SWAP mapcar ; : pathwrite2 LAMBDA{ car >R car R> CR tablewrite } -ROT map2 ; \ принадлежит игровому полю? : valid? { x y -- ? } y 0 < x 0 < OR IF FALSE EXIT THEN y ny < x nx < AND ; \ сгенерировать два числа +n и -n : +/- ( n <--> +/-n ) PRO CONT NEGATE CONT DROP ; : BOTH+ { a b c d -- a+c b+d } a c + b d + ; \ сгенерировать все варианты прыжка конём : variants=> ( x y --> x1 y1 \ <-- x1 y1 ) PRO START{ > 2 +/- 1 +/- <> 1 +/- 2 +/- <* ( x y dx dy ) 2OVER 2OVER BOTH+ CONT 2DROP }EMERGE 2DROP ; \ отсечь только те что попадают на игровое поле : //valid PRO 2DUP valid? ONTRUE CONT ; \ сохранить все варианты хода в список : variants ( x y -- l ) %[ START{ variants=> //valid 2DUP xy % }EMERGE ]% ; \ Расстояние от хотя бы одной позиции из списка l1 до клетки x y равняется одному ходу конём : beats? ( x y l1 -- ? ) -ROT variants { \| l2 } DUP -> l2 ( l1 l2 ) \ AND lists LAMBDA{ OVER ( a l1 ) LAMBDA{ position OVER = } SWAP list-find NIP NIP } SWAP list-find NIP NIP l2 FREE-LIST ; \ занята ли клетка : free? ( x y -- ? ) xy DUP w position-member? IF DROP FALSE EXIT THEN b position-member? 0= ; \ отсекает все битый позиции : //notbeats ( x y l <--> x y ) PRO >R 2DUP R> beats? 0= IF CONT THEN ; \ отсекает все занятые позиции : //free ( x y <--> x y ) PRO 2DUP free? ONTRUE CONT ; \ ход одним конём : move1 ( enemy knight --> \ <-- ) STATIC z z ! STATIC enemy enemy ! PRO z @ position p BACK xy z @ position! TRACKING 2RESTB variants=> //valid //free enemy @ //notbeats 2DUP xy z @ history member? ONFALSE 2DUP xy z @ position! 2DUP xy z @ history-add z @ enemy @ CONT enemy ! z ! z @ history-dec ; \ ход чёрных - это либо один ход первым конём, либо вторым, либо третьим : bmove PRO b list-> car w SWAP move1 CONT ; : wmove PRO w list-> car b SWAP move1 CONT ; \ совпала ли позиция с заданой? : finish? LAMBDA{ position b-fin member? NOT } b list-find NIP NOT ; \ сохранить позиции всех коней : save-positions ( b\|w -- ) %[ LAMBDA{ position % } SWAP mapcar ]% ; \ не более n решений : solutions=> ( n --> \ <-- ) STATIC n n ! STATIC cnt cnt 0! PRO START{ cnt @ n @ >= IF EXIT THEN \ bwprint \ KEY DROP bmove b save-positions vnode as-list bpath cons TO bpath BACK bpath DUP cdr TO bpath () cons FREE-LIST TRACKING wmove w save-positions vnode as-list wpath cons TO wpath BACK wpath DUP cdr TO wpath () cons FREE-LIST TRACKING \ CR ." Check finish" finish? IF CONT cnt 1+! THEN finish? ONFALSE \ CR ." Recurse" DIVE }EMERGE ; : go 100 +{ solutions=> CR CR bwprint wpath reverse \ eventually все пути в обратном порядке - для удобства - развернём перед выводом bpath reverse 2DUP CR pathwrite2 reverse TO bpath reverse TO wpath 1 }+ CR " Found {n} solutions" STYPE ; go </pre> Работает традиционно только на cvs-коде. Алгоритм - тупой перебор в лоб - даже без устремления к цели - просто перебор всех ходов удовлетворяющих условиям до тех пор пока текущая позиция не совпадёт с требуемой. Параметры : размер доски, количество коней и их начальное и конечное расположение можно менять (правда ввиду тупости алгоритма результата можно ждать долго...). Находит восемь решений. Реализовано на бакфорте потому что есть удобные средства для перебора, "конкатенации" переборов, возврата.

Forth http://fforum.winglion.ru/

шесть коней http://fforum.winglion.ru/viewtopic.php?f=19&t=740	Страница 1 из 4

Автор:	chess [ Ср май 16, 2007 16:58 ]
Заголовок сообщения:
Ygrek совершил подвиг программиста. Браво! Я думал - никто не решит. Была применена тяжелая артиллерия - бакфорт и списки. Правда был использован тупой перебор, из-за чего время решения увеличилось, но зато решение было найдено в общем виде. Управление направлением перебора - использование набора правил выбора из многих вариантов немногих(в идеале - одного), быстрее ведущих к цели - главная проблема ИИ. В данном случае можно было бы ввести понятие расстояния между текущей позицией коней и конечной их позицией (это лежит на поверхности). И если ход уменьшает это расстояние, то его следовало бы предпочесть ходу увеличивающему расстояние, правда, при условии что позиция, которая получится после этого хода отсутствует в списке состоявшихся позиций. Сам я такие задачи могу решать лишь на уровне построения алгоритма, а реализовать на форте нет - в форте я неофит пока

Автор:	yz [ Ср май 16, 2007 20:08 ]
Заголовок сообщения:
Прежде чем пускать в ход тяжелую артиллерию, неплохо сначала подумать. Задача элементарно решается методом пуговиц и нитей без всякого компьютера. См. "Наука и жизнь", № 7, 1977.

Автор:	ygrek [ Ср май 16, 2007 20:16 ]
Заголовок сообщения:
Задача стояла решить на форте. По крайней мере я себе поставил такую задачу. Решить на бумажке эту конкретную задачку конечно проще. Как её решать указанным методом совершенно непонятно.

Автор:	chess [ Ср май 16, 2007 20:47 ]
Заголовок сообщения:
yz писал(а): Прежде чем пускать в ход тяжелую артиллерию, неплохо сначала подумать. Задача элементарно решается методом пуговиц и нитей без всякого компьютера. См. "Наука и жизнь", № 5, 1977. Там задача сначала приводится к удобному для восприятия человеком виду. После этого все решения легко находятся вручную.

Автор:	mrack [ Ср май 16, 2007 21:39 ]
Заголовок сообщения:
/me впроцесе поиска решения P.S. вернее в процессе отладки выбранного пути

Автор:	yz [ Ср май 16, 2007 23:26 ]
Заголовок сообщения:
ygrek писал(а): Всё таки как решать эту задачку методом ниток и пуговиц? Там задача и тут задача - принципиально разные. Краткое описание метода можно посмотреть здесь: http://stepanov.lk.net/gardner/sec/sec03.html

Автор:	ygrek [ Чт май 17, 2007 00:10 ]
Заголовок сообщения:
В этой задаче вместо одного кольца - два кольца с двумя переходами - есть два узла развилки. Вот схема : И есть условие на "битые поля". То есть надо следить чтобы соседние узлы не были заняты вражеским цветом. По-моему вручную даже после такого преобразования решение не очевидно и надо руками двигать и смотреть. Ну а программа просто реализует это двигание.

Автор:	вопрос [ Чт май 17, 2007 00:16 ]
Заголовок сообщения:
Это что, теория графов?

Автор:	ygrek [ Чт май 17, 2007 00:19 ]
Заголовок сообщения:
Сначала я кстати явно строил этот граф переходов и хранил в памяти. Но что-там не задалось и переписал. Хотя так для бОльших размерностей конечно правильней.

Страница 1 из 4	Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/

Автор:	yz [ Чт май 17, 2007 10:14 ]
Заголовок сообщения:
ygrek писал(а): И есть условие на "битые поля". То есть надо следить чтобы соседние узлы не были заняты вражеским цветом. По-моему вручную даже после такого преобразования решение не очевидно и надо руками двигать и смотреть. Ну а программа просто реализует это двигание. Программа проводит полный перебор, то есть при всей технической изощренности реализует самый неоптимальный алгоритм. К сожалению, я никогда не умел решать математических задач, но чувствую, что в этой задаче можно придумать какой-то простой алгоритм. Но тогда не получается задачи программистской.