Задача за осемте царици Постановка на задачата



Дата05.06.2017
Размер48.47 Kb.
#22867
ТипЗадача
Задача за осемте царици

1. Постановка на задачата

Да се намери такова разположение на осем царици върху шахматна дъска, че никоя от тях да не се намира на бито поле от останалите.

Нека решението да има вида:
Solution(Pos).
и да приема стойност истина, тогава и само тогава, когато Pos изобразява позиция, при която осемте царици не се бият една друга.
2. Решение на задачата
Вариант 1

Първо трябва да изберем начин за представяне на позициите върху дъската. Един от най-естествените начини е да представяме позициите във вид на списък от осем елемента, всеки един от които съответства на по една царица. Всеки един елемент на списъка ще описва това поле от дъската, на което стои съответната царица. Полетата ще описваме с помощта на двойка кординати (X и Y), като всяка координата е цякло число от 1 до 8. Тази двойка ще записваме в програмата във вида X/Y .

По този начин задачата се сведе до намиране на списък от вида:
[X1/Y1, X2/Y2, X3/Y3, X4/Y4, X5/Y5, X6/Y6, X7/Y7, X8/Y8]
удовлетворяващ условието цариците да не са на бито поле.

Нашата процедура Solution трябва да намери подходящо свързване на променливите X1,Y1,X2,Y2,..., X8,Y8. Ясно е че всички царици трябва да се намират на различни вертикали, ето защо можем да ограничим начина на разполагане, за да облегчим решението. Можем да фиксираме X-координатата, тогава списъкът даващ решението трябва да има вида:


[1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]

Нас ни интересуват дъски с размер 8x8. Нека да разгледаме по-обща задача, която бихме могли лесно да решим и тогава решението на нашата задача ще може да разглеждаме като неин частен случай. Много важен момент е да изберем подходящо обобщение на задачата. В нашия случай подходящо обобщение на задачата е да разрешим броя на цариците да е произволен, включително и нула. Тогава определянето на решението Solution се свежда до два случая:



Случай 1: Списъкът от царици е празен.
Това очевидно е решение, защото в този случай никой не е на бито поле от другите.

Случай 2: Списъкът от царици не е празен.
Тогава той ще има вида:
[ X/Y | Rest ]
където първата царица се намира на поле X/Y, а останалите - на полета описани в списъка Rest. За да бъде това решение е необходимо да са изпълнени следните условия:
(1) Цариците от списъка Rest, трябва да не се бият една друга, т.е. списъкът
Rest да представлява решение.
(2) X и Y трябва да са числа от 1 до 8.
(3) Царицата, която е на поле X /Y не трябва да се бие с нито една от цариците, които са в списъка Rest.

Тогава Solution ще има вида:


solution([X/Y|Rest]):- solution(Rest),
member(Y,[1,2,3,4,5,6,7,8]),
notbeat(X/Y,Rest).

Остава да напишем notbeat:


notbeat(Q,QList).

Неговото описание отново може да се разбие на два случая:

(1) Ако Qlist е празен списък, тогава условието е изпълнено.
(2) Ако QList не е празен списък, то той ще има вида
[Q1| QList]
и трябва да отговаря на следните две условия:
(а) царицата на поле Q не трябва да бие царицата на поле Q1 и
(б) царицата на поле Q не трябва да бие нито една от цариците в
списъка QList.

Условието царица да не е на бито поле от друга царица, означава двете царици да не са на един и същ диагонал, хоризонтал или вертикал, т.е. Y-координатите им да са различни и разстоянията между полетата по X и по Y да са различни.

Тогава програмата, която дава решението ще има вида:
solution([]).

solution([X/Y|Rest]):- solution(Rest),

member(Y,[1,2,3,4,5,6,7,8]),

notbeat(X/Y,Rest).
notbeat(_,[]).

notbeat(X/Y,[X1/Y1|Rest]):- Y =\= Y1,
Y1-Y =\= X-X1, Y1-Y =\= X1-X,


notbeat(X/Y,Rest).
member(X,[X|L]).

member(X,[Y|L]):-member(X,L).
pattern([1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]).
Решението може да се получи от въпроса:

?- pattern(S), solution(S).

Вариант 2

При вариант 1, решенията имаха вида:


[1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]
очевидно е че ако се пропусне X-координатата никаква информация няма да се изгуби. Ето защо може да направим по-икономично представяне на позициите върху дъската, като оставим само Y-координатите на цариците:
[Y1,Y2,Y3,Y4,Y5,Y6,Y7,Y8].

За да няма биене на цариците по хоризонтала е необходимо Y-координатите на цариците да са такива, че да са заети всички хоризонтали от1 до 8. Остава само да се определи в какъв ред ще се приемат тези осем стойности. Всяко решение представлява една пермутация на списъка: [1,2,3,4,5,6,7,8]. Една такава пермутация на списъка S е решение, ако всяка царица не е на бито поле, т.е. S е "безопасен".

Тогава решението ще има вида:
solution(S):-perm([1,2,3,4,5,6,7,8],S),safe(S).

На построяването на пермутация на списък няма да се спираме. Остава да определим safe. Може да разгледаме два случая:

(1) S е празният списък. Тогава той очевидно е безопасен.
(2) S не е празен списък и има вида [Q|Rest]. Тогава той е безопасен, ако списъкът Rest е безопасен и Q не бие нито една царица от списъка Rest.

Тогава safe ще има вида:


safe([]).
safe([Q|Rest]):-safe(Rest),notbeat(Q,Rest,1).

При определянето на notbeat трудността се състои в това, че разположението на цариците се определя само от Y-координатите им, а X-координатите не присъстват в явен вид при представянето. Ето защо ще добавим трети аргумент DistX, който ще ни задава разстоянието по X, между Q и Rest.

Тогава програмата, която дава решението ще има вида:

solution(S):-perm([1,2,3,4,5,6,7,8],S),safe(S).
safe([]).
safe([Q|Rest]):-safe(Rest),notbeat(Q,Rest,1).

notbeat(_,[],_).
notbeat(Y,[Y1|ListY],DistX):- Y1-Y =\= DistX,
Y-Y1 =\= DistX,
Dist1 is DistX+1,
notbeat(Y,ListY,Dist1).

del(A,[A|L],L).

del(A,[B|L],[B|L1]):-del(A,L,L1).
perm([],[]).

perm([X|L],P):-perm(L,L1),del(X,P,L1).
Вариант 3

При този вариант, всяка царица трябва да бъде разположена на някое поле, т.е. на някоя хоризонтала, някоя вертикала и на пресечната точка на кои да са два диагонала. За да се осигури безопасността на цариците е необходимо те да се разполагат в разлияни хоризонтали, вертикали и диагонали (както на спускащи се отгоре-надолу, така и на отиващи отдолу-нагоре). Ще разглеждаме система с четири координати:


x вертикали
y хоризонтали
u диагонали, спускащи се отгоре-надолу
v диагонали, отиващи отдолу-нагоре.
Тези координати не са независими: при дадени x и y, u и v се определят еднозначно:
u = x - y
v = x + y

Областите на изменение на четирите координати са:


Dx = [1,2,3,4,5,6,7,8]
Dy = [1,2,3,4,5,6,7,8]
Du = [-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7]
Dv = [2,3,4,5,6,7,8,9,10,11,12,13,14,15,16].

задачата за осемте царици може да бъде формулирана по следния начин: да се изберат осем четворки (X,Y,U,V), от областите (X от Dx,Y от Dy, U от Du, V от Dv), така че нито един елемент да не се избира два пъти от една и съща област Решението при такава формулировка на задачата накратко може да бъде описано така: от дадените 4 интервала да се избере позицията на първата царица, да се зачеркнат съответните елементи от 4-те интервала, а полсле като се използват останалите стойности от 4-те интервала да се разположат останалите царици.

Тогава програмата, която дава решението ще има вида:

solution(ListY):-solve( ListY,
[1,2,3,4,5,6,7,8],
[1,2,3,4,5,6,7,8],
[-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7],
[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]).

solve([],[],Dy,Du,Dv).
solve([Y|ListY],[X|Dx1],Dy,Du,Dv):- del(Y,Dy,Dy1),
U is X-Y, del(U,Du,Du1),
V is X+Y, del(V,Dv,Dv1),
solve(ListY,Dx1,Dy1,Du1,Dv1).

del(A,[A|L],L).

del(A,[B|L],[B|L1]):-del(A,L,L1).
Това решение е универсално и лесно може да бъде модифицирано за случая на N царици и дъска NxN, като се създаде генератор на множествата Dx,Dy,Du,Dv. Ще дефинираме:
generate(N1,N2,List),
където
List=[N1,N1+1,N1+2,...,N2-2,N2-1,N2]

Обобщеното решение sol(N,S) за дъска NxN ще има вида:


sol(N,S):-generate(1,N,Dxy),

Nu1 is 1-N, Nu2 is N-1, generate(Nu1,Nu2,Du),

Nv2 is N+N, generate(2,Nv2,Dv),

solve(S,Dxy,Dxy,Du,Dv).
generate(N,N,[N]).

generate(N1,N2,[N1|List]):-N1 < N2, M is N1+1, generate(M,N2,List).






Сподели с приятели:




©obuch.info 2024
отнасят до администрацията

    Начална страница