Пролог. Обход конем шахматной доски

[Gambler]

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

P.S. в поиск не посылайте. Был уже. Ничего толкового не нашел.

[Gambler]

Мда, я разочарован в этом форуме, хоть и могу считать себя старожилом. Ну что ж, тогда я прошу отписаться участников с репутацией больше 100 о том, что они не в силах мне помочь. А то вдруг пропустили темку....

[Utkin]

Я не в силах тебе помочь . Потому что не шарю в Прологе (хоть и пытался въехать). Насчет логического программирования есть неформившаяся идея. Все эти клетки куда наступит конь в определенной последовательности есть по сути константа. То есть для другого поля тебе нужно сделать пересчет определенным образом. Как-то так. Далее, ковырясь в Прологе я нашел ряд примеров, которые хоть и описаны как логическое программирование, но по сути те же я**а только в профиль.
Насчет форума, то ничего страшного здесь нет. Форум делает упор на Дельфи и С++, поэтому найти нужного Вам специалиста сложно. Вы же к проктологу зубы дергать не ходите? Так что Ваша обида не обоснована.

[Sparky]

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

[Gambler]

я по большому счету решил. Баги есть, но это вопрос времени. Проблема в том, что я решаю задачу - математически. А надо что бы пролог сам мне ее решил. То есть как то объяснить прологу что я хочу )))

[Z1000000]

Вот твоя задача.
http://www.progz.ru/t36025/

А я ее даже на Turbo Prolog 2 перевел. Решает твою задачу на доске 6х6 за секунды. На больших надолго задумывается!

domains
il = integer*
predicates
stephorse(integer,integer,integer,integer)
outborder(integer)
av(integer,integer)
elem(integer,integer,il)
solve(il,il,integer)

clauses
av(2,1).
av(2,-1).
av(1,2).
av(1,-2).
av(-1,2).
av(-1,-2).
av(-2,1).
av(-2,-1).

outborder(X):-X>0,X<7.

elem(X,Y,[X,Y|List]):-!.
elem(X,Y,[_,_|Tail]):-elem(X,Y,Tail).

stephorse(X,Y,X1,Y1):-
av(Dx,Dy),X1=X+Dx,Y1=Y+Dy,
OutBorder(X1),OutBorder(Y1).

solve(List,List,1):-!.
solve([X,Y|Past],Res,N):-
stephorse(X,Y,X1,Y1),
not(elem(X1,Y1,Past)),
N1=N-1,
solve([X1,Y1,X,Y|Past],Res,N1).
goal
solve([1,1],Res,36),write(Res)

[Gambler]

Спасибо конечно! Но тут грубый перебор. На доске например 30х30 я буду ждать годами. Нужно придерживаться правила, что я написал в первом посте. Тогда обход совершается с первого раза.

[Utkin]

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

[Gambler]

последовательности нет в общем то. Да и смысл теряется, если что то ручками вбивать. Надо рассчитать.

[Gambler]

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

%trace
domains
	list = integer*
	matrix = list*
predicates
	optim(list,integer)
	min(list,integer,integer,integer,integer)
	lenght(matrix,integer)
	rating(matrix,matrix,matrix,list,list)
	allmove(matrix,matrix,integer,integer,matrix,matrix)
	addel(list,list,integer)
	add(matrix,matrix,list)
	write_matrix(matrix)
	write_list(list)
	value(list, integer, integer, integer)
	matrix_value(matrix, integer, integer, integer, integer)
	ismove(matrix,integer,integer)
	genline(list,integer)
	genpole(matrix,integer,integer)
	changevaluelist(list,list,integer,integer,integer)
	changevaluematrix(matrix,matrix,integer,integer,integer,integer)
	start(integer,integer,integer,integer)
	move(matrix,matrix,integer,integer,integer,integer,integer,matrix)
clauses
	rating(_,_,[],X,X).
	rating(Pole,Hodi,[Head|Tail],Tmp,Result):-
		value(Head,1,X,1),
		value(Head,2,Y,1),
		allmove(Pole,Hodi,X,Y,_,Res),
		lenght(Res,K),
		addel(Tmp,Tmp1,K),
		rating(Pole,Hodi,Tail,Tmp1,Result).
	add([],[X],X).
	add([Head|Tail],[Head|NewList],X):-
		add(Tail,NewList,X).
	addel([],[X],X).
	addel([Head|Tail],[Head|NewList],X):-
		addel(Tail,NewList,X).
	min([],_,K,_,K).
	min([Head|Tail],Tmp,_,Counter,Result):-
		Tmp>Head,
		NewCounter = Counter+1,
		min(Tail,Head,Counter,NewCounter,Result).	
	min([_|Tail],Tmp,Index,Counter,Result):-
		NewCounter = Counter+1,
		min(Tail,Tmp,Index,NewCounter,Result).
	optim([],0).
	optim([Head|Tail],Res):-
		min(Tail,Head,1,2,Res).
	lenght([],0).
	lenght([_|Tail],N) :- lenght(Tail, NN),
				N = NN + 1.
		
	write_list([]) :- nl.
 	write_list([X|Tail]):-
 			X<10,
 			write(" ",X," "),
 			write_list(Tail).
        write_list([X|Tail]):-
        		X>=10,
        		write(X," "),               
        		write_list(Tail).
	write_matrix([]):-nl.
	write_matrix([X|Tail]):-write_list(X),
			write_matrix(Tail).
	value([], _, -1, _) :- !.
	value([Elem|_], Index, Elem, Index) :- !.
	value([_|Tail], Index, Value, Counter) :- !,
			NewCounter = Counter + 1,
			value(Tail, Index, Value, NewCounter).
			
	matrix_value([],_,_,-1,_):-!.
	matrix_value([Elem|_],Index,IndexCol,Result,Index):-!,
			value(Elem,IndexCol,Result,1),!.
	matrix_value([_|Tail],Index,IndexCol,Result,Counter) :-!,
			NewCounter = Counter + 1,
			matrix_value(Tail,Index,IndexCol,Result,NewCounter).
	
	ismove(Mtr,X,Y):-!,
		matrix_value(Mtr,X,Y,Res,1),
		Res=0.
	
	allmove(_,[],_,_,Res,Res).
	allmove(Pole,[Head|Tail],X,Y,Tmp,Res):-
		value(Head,1,IncX,1),
		value(Head,2,IncY,1),
		XX = X + IncX,
		YY = Y + IncY,
		ismove(Pole,XX,YY),
		add(Tmp,Tmp1,[XX|[YY|[]]]),
		allmove(Pole,Tail,X,Y,Tmp1,Res).
		
	allmove(Pole,[_|Tail],X,Y,Tmp,Res):-
		allmove(Pole,Tail,X,Y,Tmp,Res).
	
	genline([],0):-!.
 	genline([0|List],Number):-!,
 			Number>0,
                        Next_Number=Number-1,
                        genline(List,Next_Number).
	genpole([],0,_):-!.
	genpole([Head|Tail],Number,Ny):-!,
				Number>0,
				genline(Head,Ny),
				Next_Number=Number-1,
				genpole(Tail,Next_Number,Ny).
	changevaluelist([],[],_,_,_):-!.
	changevaluelist([_|Tail],[Val|List],Index,Val,Index):-!,
				NewNumber = Index+1,
				changevaluelist(Tail,List,Index,Val,NewNumber).
	changevaluelist([Head|Tail],[Head|List],Index,Val,Number):-!,
				NewNumber = Number+1,
				changevaluelist(Tail,List,Index,Val,NewNumber).
	changevaluematrix([],[],_,_,_,_):-!.
	changevaluematrix([Head|Tail],[Res|List],Lin,Col,Val,Lin):-!,
				changevaluelist(Head,Res,Col,Val,1),
				NewNumber = Lin+1,
				changevaluematrix(Tail,List,Lin,Col,Val,NewNumber).
	changevaluematrix([Head|Tail],[Head|List],Lin,Col,Val,Index):-!,
				NewNumber = Index+1,
				changevaluematrix(Tail,List,Lin,Col,Val,NewNumber).
				
	move(Pole,Hodi,X,Y,N,M,Counter,Result):-
		Counter<=N*M,
		changevaluematrix(Pole,NewPole,X,Y,Counter,1),
%		write_matrix(NewPole),
		allmove(NewPole,Hodi,X,Y,_,Mov),
%		lenght(Mov,Len),
%		Len>0,
		rating(NewPole,Hodi,Mov,_,ListRat),
		optim(ListRat,Index),
		matrix_value(Mov,Index,1,XX,1),
		matrix_value(Mov,Index,2,YY,1),
		NewCounter = Counter + 1,
		move(NewPole,Hodi,XX,YY,N,M,NewCounter,Result).
	move(Pole,_,_,_,_,_,_,Pole):-!.
		
		
	start(X,Y,N,M):-
		X<N,Y<M,X>0,Y>0,N<15,M<15,
		Hod = [[-1,2],[-2,1],[1,2],[2,1],[-1,-2],[-2,-1],[1,-2],[2,-1]],
		genpole(Pole,N,M),
		move(Pole,Hod,X,Y,N,M,1,Res),
		write_matrix(Res).
		
goal
	nl,nl,nl,
	write("Hodi konja"),nl,nl,
	start(1,1,5,5).