Problem 8 kraljic

Primer razvoja deklerativnega programa na primeru programiranja rešitve problema 8 kraljic. To je le kratek povzetek problema in rešitev, ki se večkrat pojavijo na različnih mestih v knjigi Ivan Bratko: Prolog - Programming for Artificial Intelligence, 3rd ed in bi se naj uporabljal skupaj s knjigo. Namen je le na enem mestu združiti nekaj informacij, ki so sicer razdrobljene po knjigi in pregledati različne možnosti izboljšav.

Problem

Kako razporediti 8 kraljic na šahovnico, tako da ne napadajo ena druge?

1. rešitev

Zgradi pravilno postavitev za n kraljic tako, da prvo zgradi postavitev za n − 1 kraljic in potem postavi n-to kraljico tako, da ne napada drugih kraljic in ni napadena od drugih kraljic.

% Figure 4.7   Program 1 for the eight queens problem.
% solution( BoardPosition) if
%   BoardPosition is a list of non-attacking queens

solution( [] ).
solution( [X/Y | Others] )  :-      % First queen at X/Y, other queens at Others
  solution( Others),
  member( Y, [1,2,3,4,5,6,7,8] ),
  noattack( X/Y, Others).           % First queen does not attack others

noattack( _, [] ).                  % Nothing to attack
noattack( X/Y, [X1/Y1 | Others] )  :-
  Y =\= Y1,                         % Different Y-coordinates
  Y1-Y =\= X1-X,                    % Different diagonals
  Y1-Y =\= X-X1,
  noattack( X/Y, Others).

member( Item, [Item | Rest] ).
member( Item, [First | Rest] )  :-
  member( Item, Rest).

% A solution template

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

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

2. rešitev

Poskuša vse permutacije postavitev kraljic na šahovnici in preverja, če se pri postavitvi ne napadajo.

% Figure 4.9   Program 2 for the eight queens problem.
% solution( Queens) if 
%   Queens is a list of Y-coordinates of eight non-attacking queens

solution( Queens)  :-
  permutation( [1,2,3,4,5,6,7,8], Queens),
  safe( Queens).

permutation( [], [] ).
permutation( [Head | Tail], PermList)  :-
  permutation( Tail, PermTail),
  del( Head, PermList, PermTail).   % Insert Head in permuted Tail 

% del( Item, List, NewList): deleting Item from List gives NewList

del( Item, [Item | List], List).
del( Item, [First | List], [First | List1] )  :-
  del( Item, List, List1).

% safe( Queens) if 
%   Queens is a list of Y-coordinates of non-attacking queens

safe( [] ). 
safe( [Queen | Others] )  :-
  safe( Others),
  noattack( Queen, Others, 1). 

noattack( _, [], _). 
noattack( Y, [Y1 | Ylist], Xdist)  :-
  Y1-Y =\= Xdist,
  Y-Y1 =\= Xdist,
  Dist1 is Xdist + 1,
  noattack( Y, Ylist, Dist1).

To je počasna rešitev, saj poskuša vse permutacije postavitev, tudi tiste, za katere ostali dve rešitvi kmalu ugotovita, da niso v redu.

3. rešitev

Vsaka kraljica na šahovnici napada vrstico, stolpec in dve diagonali, tako da nobena druga kraljica ne more biti v isti vrstici, stolpcu ali diagonali. Ta rešitev poišče takšno kombinacijo četvork teh vrednosti, da je vsaka vrednost uporabljena samo enkrat (in to pomeni, da na dani vrstici, stolpcu in diagonalama leži le ena kraljica).

% Figure 4.11   Program 3 for the eight queens problem.
% solution( Ylist) if 
%   Ylist is a list of Y-coordinates of eight non-attacking queens

solution( Ylist)  :-   
  sol( Ylist,                                    % Y-coordinates of queens
       [1,2,3,4,5,6,7,8],                        % Domain for X-coordinates
       [1,2,3,4,5,6,7,8],                        % Domain for Y-coordinates
       [-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7],   % Upward diagonals
       [2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] ). % Downward diagonals 

sol( [], [], Dy, Du, Dv).
sol( [Y | Ylist], [X | Dx1], Dy, Du, Dv)  :-
  del( Y, Dy, Dy1),                 % Choose a Y-coordinate
  U is X-Y,                         % Corresponding upward diagonal
  del( U, Du, Du1),                 % Remove it
  V is X+Y,                         % Corresponding downward diagonal
  del( V, Dv, Dv1),                 % Remove it
  sol( Ylist, Dx1, Dy1, Du1, Dv1).  % Use remaining values 

del( Item, [Item | List], List).
del( Item, [First | List], [First | List1] )  :-
  del( Item, List, List1).

Uporaba negacije kot neuspeha

Z uporabo negacije kot neuspeha se lahko 1. rešitev zapiše tudi tako:

solution( [] ).
solution( [X/Y | Others] )  :-
  solution( Others),
  member( Y, [1,2,3,4,5,6,7,8] ),   % Usual member predicate
  not attacks( X/Y, Others).

attacks( X/Y, Others)  :-
  member( X1/X2, Others),
  ( Y1 = Y;
    Y1 is Y + X1 - X;
    Y1 is Y - X1 + X ).

Posplošitev problema

Problem se lahko posploši iz 8 kraljic na n kraljic. Rešitev takšnega problema je podobna 1. rešitvi, saj se s takšno posplošitvijo kar ponuja rešitev z rekurzijo, pri kateri je n = 0 trivialna rešitev, n > 0 se pa reši tako, da se prvo najde rešitev za n − 1 kraljic in se doda n-to kraljico tako, da se kraljice ne napadajo. Tako je potem:

eightqueens( Pos)  :-  nqueens( Pos, 8).

Lahko pa se posploši tudi velikost šahovnice, za katero je zanimiva 3. rešitev, saj je potrebno le razširiti sezname (domene) možnih vrstic, stolpcev in diagonal. Za to je potrebno zgraditi metodo, ki bo sama zgradila te sezname:

solution( N, S)  :-
  gen( 1, N, Dxy),
  Nu1 is 1 - N, Nu2 is N - 1,       % Dxy - domain for X and Y
  gen( Nu1, Nu2, Du),
  Nv2 is N + N,
  gen( 2, Nv2, Dv),
  sol( S, Dxy, Dxy, Du, Dv).

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

Tako se rešitev za 12 kraljic na 12x12 veliki šahovnici dobi s:

?-  solution( 12, S).

Problem lahko rešujemo tudi tako, da uporabimo splošno iskanje rešitve z iskanjem v globino, kjer v prostoru stanj iščemo pot do rešitve s koraki v globino, dokler ne pridemo do cilja ali pa se vrnemo nazaj po poti in nadaljujemo po prvi še neprehojeni poti.

solve( N, [N] )  :-
  goal(N).
solve( N, [ N | Sol1] )  :-
  s( N, N1),
  solve( N1, Sol1).

In splošen korak ter cilj zapišemo kot:

s( Queens, [Queen | Queens] )  :-
  member( Queen, [1,2,3,4,5,6,7,8] ),     % Place Queen into any row
  noattack( Queen, Queens).

goal( [_,_,_,_,_,_,_,_] ).                % Position with 8 queens

Začetno stanje je []:

?-  solve( [], Solution).

Pospešitev rešitev

Če pogledamo, kako se izbirajo kraljice pri 1. rešitvi:

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

vidimo, da se izbirajo po vrsti, kar očitno ni najboljši vrstni red, saj morajo biti sosednje kraljice po stolpcih najmanj 2 vrstici narazen, da se ne napadajo. Izboljšava je:

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

kar povzroči 3 do 4 kratno pohitritev programa.

3. rešitev pa lahko pohitrimo tako, da namesto da brišemo "porabljene" diagonale iz seznamov le-teh, raje uporabimo simulacijo polj, v katerih samo označimo že uporabljene s kraljičino X koordinato (in tako se X koordinata kakšne druge kraljice ne ujame s celico polja diagonale).

sol( Ylist)  :-
  functor(Du, u, 15),               % Set of upward diagonals
  functor(Dv, v, 15),               % Set of downward diagonals
  sol( Ylist,
     [1,2,3,4,5,6,7,8],             % Set of X-coordinates
     [1,2,3,4,5,6,7,8],             % Set of Y-coordinates
     Du, Dv).

sol( [], [], [], _, _).
sol( [Y | Ys], [X | XL], YL0, Du, Dv)  :-
  del( Y, YL0, YL),                 % Choose a Y coordinate
  U is X+Y-1,
  arg( U, Du, X),                   % Upward diagonal free
  V is X-Y+8,
  arg( V, Dv, X),                   % Downward diagonal free
  sol( Ys, XL, YL, Du, Dv).

del( X, [X | L], L).
del( X, [Y | L0], [Y | L]) :-
  del( X, L0, L).