Найти все решения для такой chess-задачки(с помощью Форта конечно):

Поменять местами белых коней с черными, путем поочередных ходов сначала одним из белых коней, затем одним из черных коней и т.д., при этом коней нельзя ставить на клетки, которые находятся под ударом коней другого цвета.

фигасе... /me впал в задумчивость

Вручную оно как-то решается быстрее, чем с помощью Форта

ну, тут важен алгоритм

Ну и кто разберёт эту тарабарщину?
<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-коде.
Алгоритм - тупой перебор в лоб - даже без устремления к цели - просто перебор всех ходов удовлетворяющих условиям до тех пор пока текущая позиция не совпадёт с требуемой. Параметры : размер доски, количество коней и их начальное и конечное расположение можно менять (правда ввиду тупости алгоритма результата можно ждать долго...). Находит восемь решений. Реализовано на бакфорте потому что есть удобные средства для перебора, "конкатенации" переборов, возврата.

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

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

Задача стояла решить на форте. По крайней мере я себе поставил такую задачу.
Решить на бумажке эту конкретную задачку конечно проще.
Как её решать указанным методом совершенно непонятно.

Там задача сначала приводится к удобному для восприятия человеком виду. После этого все решения легко находятся вручную.

/me впроцесе поиска решения
P.S. вернее в процессе отладки выбранного пути

Краткое описание метода можно посмотреть здесь: http://stepanov.lk.net/gardner/sec/sec03.html

В этой задаче вместо одного кольца - два кольца с двумя переходами - есть два узла развилки. Вот схема :

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

Это что, теория графов?

Сначала я кстати явно строил этот граф переходов и хранил в памяти. Но что-там не задалось и переписал. Хотя так для бОльших размерностей конечно правильней.

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