VPF::Обход ферзем - Форум программистов

Михаил1

Дата 7.4.2009, 23:01 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 7.4.2009

Репутация: 1
Всего: 1

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

.
Вот такой вариант обхода могу предложить http://golovolomka.hobby.ru/books/gik/04.shtml
Заранее спасибо

Это сообщение отредактировал(а) Михаил1 - 8.4.2009, 20:26

Михаил1

Дата 12.4.2009, 20:21 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 7.4.2009

Репутация: 1
Всего: 1

Вот консольное решение задачи в VIP7.2. Использовано две эвристики:
1) Обход доски только противосолонь.
2) На каждом отрезке ломаной необходимо проходить не менее трёх новых клеток.
Время решения ~0 сек.

Код


domains
yn = y();n().
cell = c(integer,integer,yn).
cells = cell*.
class facts
i : unsigned:=0.
class predicates
gen_desk : (integer,integer) -> cells Desk determ(i,i).
direction : (integer*) -> integer procedure(i).
isEnd : (cells) determ (i).
nCoord : (integer,integer,integer,integer,integer) determ (i,i,o,o,i).
broken : (integer,integer,integer*,integer*,cells) nondeterm (i,i,o,i,i).
line : (integer,integer,integer,integer,integer,cells,cells,integer) multi (i,i,o,o,i,i,o,o).
mark : (integer,integer,cells,cells,integer) determ (i,i,i,o,o).

clauses
gen_desk(_,0)=[]:-!.
gen_desk(0,J)=gen_desk(8,J-1):-J>0,!.
gen_desk(I,J)=[c(I,J,n)|gen_desk(I-1,J)]:-I>0.

direction([])=1:-!.
direction([1])=3:-!.
direction([I|_])=(I+3) mod 8.

isEnd([]):-!.
isEnd([c(_,_,y)|Desk]):-isEnd(Desk).

nCoord(X,Y,X+1,Y-1, 0):-X<8,Y>1,!.
nCoord(X,Y,X+1,Y,1):-X<8,!.
nCoord(X,Y,X+1,Y+1,2):-X<8,Y<8,!.
nCoord(X,Y,X,Y+1,3):-Y<8,!.
nCoord(X,Y,X-1, Y+1,4):-X>1,Y<8,!.
nCoord(X,Y,X-1, Y,5):-X>1,!.
nCoord(X,Y,X-1, Y-1, 6):-X>1,Y>1,!.
nCoord(X,Y,X,Y-1, 7):-Y>1,!.

broken(1,1,[],_,Desk):-isEnd(Desk).
broken(X,Y,[X1,Y1|Broken],Dir,Desk):-NDir=direction(Dir),line(X,Y,X1,Y1,NDir,Desk,Desk1,L),L>2,i:=i+1,  
                                     broken(X1,Y1,Broken,[NDir|Dir],Desk1).

line(X,Y,X0,Y0,Dir,Desk,Desk0,I+J):-nCoord(X,Y,X1,Y1,Dir),mark(X1,Y1,Desk,Desk1,J),
                                    line(X1,Y1,X0,Y0,Dir,Desk1,Desk0,I).
line(X,Y,X,Y,_,Desk,Desk,0).

mark(X,Y,[c(X,Y,n())|Desk],[c(X,Y,y())|Desk],1):-!.
mark(X,Y,[c(X,Y,y())|Desk],[c(X,Y,y())|Desk],0):-!.
mark(X,Y,[Cell|Desk],[Cell|Desk1],I):-mark(X,Y,Desk,Desk1,I).

run():-init(),
       Desk=gen_desk(8,8),
       broken(1,1,Broken,[],Desk),
       write("\nСчётчик=",i,"\nПуть: ",[1,1|Broken]),
       fail();
       _=stdio::readChar().

При наложенных ограничениях найдено два решения. Для нахождения первого решения понадобилось всего 64 шага, для второго - аж 745 шагов:
Счётчик=64
Путь: [1,1,8,1,8,8,2,2,8,2,2,8,2,4,6,8,3,8,7,4,7,8,2,3,6,3,1,8,1,1]
Счётчик=745
Путь: [1,1,8,1,8,8,3,3,7,3,2,8,2,4,6,8,3,8,7,4,7,8,1,2,7,2,1,8,1,1]

А можете подсказать, как ее переделать под SWI-Prolog?

Михаил1

Дата 22.4.2009, 22:41 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 7.4.2009

Репутация: 1
Всего: 1

SWI вариант:

Код


gen_desk(_,0,[]):-!.
gen_desk(0,J,D):- J>0, J1 is J - 1, gen_desk(8, J1, D),!.
gen_desk(I,J,[c(I,J,n) | D]) :- I>0, I1 is I-1, gen_desk(I1, J, D). 


direction([],1):-!.
direction([1],3):-!.
direction([I|_],I1):- I1 is (I+3) mod 8.

isEnd([]):-!.
isEnd([c(_,_,y)|Desk]):-isEnd(Desk).

nCoord(X,Y,X1,Y1, 0):-X<8,Y>1,X1 is X+1, Y1 is Y - 1,!.
nCoord(X,Y,X1,Y,1):-X<8,X1 is X+1,!.
nCoord(X,Y,X1,Y1,2):-X<8,Y<8,X1 is X+1, Y1 is Y+1,!.
nCoord(X,Y,X,Y1,3):-Y<8,Y1 is Y+1,!.
nCoord(X,Y,X1, Y1,4):-X>1,Y<8,X1 is X-1, Y1 is Y+1,!.
nCoord(X,Y,X1, Y,5):-X>1,X1 is X-1,!.
nCoord(X,Y,X1, Y1, 6):-X>1,Y>1,X1 is X-1, Y1 is Y-1,!.
nCoord(X,Y,X,Y1, 7):-Y>1,Y1 is Y-1,!.


broken(1,1,[],_,Desk):-isEnd(Desk).
broken(X,Y,[X1,Y1|Broken],Dir,Desk):-
    direction(Dir,NDir),
    line(X,Y,X1,Y1,NDir,Desk,Desk1,L),
    L>2,
    broken(X1,Y1,Broken,[NDir|Dir],Desk1).

line(X,Y,X0,Y0,Dir,Desk,Desk0,IJ):-
    nCoord(X,Y,X1,Y1,Dir),
    mark(X1,Y1,Desk,Desk1,J),
    line(X1,Y1,X0,Y0,Dir,Desk1,Desk0,I),
    IJ is I + J.

line(X,Y,X,Y,_,Desk,Desk,0).


mark(X,Y,[c(X,Y,n)|Desk],[c(X,Y,y)|Desk],1):-!.
mark(X,Y,[c(X,Y,y)|Desk],[c(X,Y,y)|Desk],0):-!.
mark(X,Y,[Cell|Desk],[Cell|Desk1],I):-mark(X,Y,Desk,Desk1,I).

run :-
       gen_desk(8,8,Desk),
       broken(1,1,Broken,[],Desk),
       format('Путь: ~w~n', [[1,1|Broken]]),
       fail;
       write('Готово.').

Код


?- run.
Путь: [1, 1, 8, 1, 8, 8, 2, 2, 8, 2, 2, 8, 2, 4, 6, 8, 3, 8, 7, 4, 7, 8, 2, 3, 6, 3, 1, 8, 1, 1]
Путь: [1, 1, 8, 1, 8, 8, 3, 3, 7, 3, 2, 8, 2, 4, 6, 8, 3, 8, 7, 4, 7, 8, 1, 2, 7, 2, 1, 8, 1, 1]
Готово.
true.

В общем, во всем разобрался сам, всем ОГРОМНОЕ спасибо за активнейшую помощь)))

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Prolog \| Следующая тема »