Cvičenia 10 -- SOKOBAN

V DLV-K vyriešte level klasickej hry SOKOBAN.

Vstup je zakódovaný nasledovnými predikátmi:

right(L1,L2) - hovorí, že pozícia L2 je napravo od L1
top(L1,L2) - hovorí, že pozícia L1 je nad L2 (ano, viem, že je to trošiku nekonzistentné ;)
box(L) - na pozícii L je krabica
sokoban(L) - na pozícii L je sokoban
solution(L) - na pozícii L je miesto, kam treba presunúť krabicu

Vyriešte dve verzie:

Riešenie má pozostávať z akcií:
- move(L) - sokoban sa presunie na susediacu pozíciu (tesne nad, pod, vľavo alebo vpravo, ak tam nie je krabica)
- push_right(L1,L2) push_left(L1,L2) push_up(L1,L2) push_down(L1,L2) - sokoban pousine krabicku z L1 na susediacu pozíciu L2 (a musí byť teda na správnej strane L1 a L2 musí byť voľné
Akcia move(L) nemusí presúvať sokobana medzi vedľa seba ležiacimi pozíciami, ale rovno na ľubovoľnú dostupnú ( kam sa vie v tomto momente presunúť).
Potrebujeme vlastne akciu move? :)

Príklad velmi jednoducháho vstupu:

% ######
% #@ $.#
% ######

right(l0,l1).
right(l1,l2).
right(l2,l3).
sokoban(l0).
box(l2).
solution(l3).

Zaujímavejšie vstupy

soko3.dl

% #############
% #           #
% #      @    #
% #  $        #
% #        .  #
% #           #
% #############
% 
top(c7r2,c7r1).
right(c7r1,c8r1).
top(c8r2,c8r1).
top(c8r3,c8r2).
top(c8r4,c8r3).
top(c8r5,c8r4).
right(c8r5,c9r5).
top(c9r5,c9r4).
top(c9r4,c9r3).
top(c9r3,c9r2).
top(c9r2,c9r1).
right(c9r1,c10r1).
top(c10r2,c10r1).
top(c10r3,c10r2).
top(c10r4,c10r3).
top(c10r5,c10r4).
right(c10r5,c11r5).
top(c11r5,c11r4).
top(c11r4,c11r3).
top(c11r3,c11r2).
top(c11r2,c11r1).
right(c10r4,c11r4).
right(c10r3,c11r3).
right(c10r2,c11r2).
right(c10r1,c11r1).
right(c9r2,c10r2).
right(c9r3,c10r3).
right(c9r4,c10r4).
right(c9r5,c10r5).
top(c7r5,c7r4).
top(c7r4,c7r3).
top(c7r3,c7r2).
right(c7r3,c8r3).
top(c6r3,c6r2).
top(c6r2,c6r1).
right(c6r1,c7r1).
top(c5r2,c5r1).
top(c5r3,c5r2).
top(c5r4,c5r3).
top(c5r5,c5r4).
right(c5r5,c6r5).
top(c6r5,c6r4).
top(c6r4,c6r3).
right(c6r4,c7r4).
right(c6r5,c7r5).
top(c4r5,c4r4).
top(c4r4,c4r3).
top(c4r3,c4r2).
top(c4r2,c4r1).
right(c4r1,c5r1).
top(c3r2,c3r1).
top(c3r3,c3r2).
top(c3r4,c3r3).
top(c3r5,c3r4).
right(c3r5,c4r5).
top(c2r5,c2r4).
top(c2r4,c2r3).
top(c2r3,c2r2).
top(c2r2,c2r1).
right(c2r1,c3r1).
top(c1r2,c1r1).
top(c1r3,c1r2).
top(c1r4,c1r3).
top(c1r5,c1r4).
right(c1r5,c2r5).
right(c1r4,c2r4).
right(c1r3,c2r3).
right(c1r2,c2r2).
right(c1r1,c2r1).
right(c2r2,c3r2).
right(c2r3,c3r3).
right(c2r4,c3r4).
right(c2r5,c3r5).
right(c3r4,c4r4).
right(c3r3,c4r3).
right(c3r2,c4r2).
right(c3r1,c4r1).
right(c4r2,c5r2).
right(c4r3,c5r3).
right(c4r4,c5r4).
right(c4r5,c5r5).
right(c5r4,c6r4).
right(c5r3,c6r3).
right(c5r2,c6r2).
right(c5r1,c6r1).
right(c6r2,c7r2).
right(c6r3,c7r3).
right(c7r4,c8r4).
right(c7r5,c8r5).
right(c8r4,c9r4).
right(c8r3,c9r3).
right(c8r2,c9r2).
right(c8r1,c9r1).
right(c7r2,c8r2).
box(c3r3).
solution(c9r4).
sokoban(c7r2).

soko4.dl

% ########
% # .    #
% #  $ $ #
% #.  @  #
% ########    
% 
top(c4r3,c4r2).
top(c4r2,c4r1).
right(c4r1,c5r1).
top(c5r2,c5r1).
top(c5r3,c5r2).
right(c5r3,c6r3).
top(c6r3,c6r2).
top(c6r2,c6r1).
right(c5r2,c6r2).
right(c5r1,c6r1).
top(c3r2,c3r1).
top(c3r3,c3r2).
right(c3r3,c4r3).
top(c2r3,c2r2).
top(c2r2,c2r1).
right(c2r1,c3r1).
top(c1r2,c1r1).
top(c1r3,c1r2).
right(c1r3,c2r3).
right(c1r2,c2r2).
right(c1r1,c2r1).
right(c2r2,c3r2).
right(c2r3,c3r3).
right(c3r2,c4r2).
right(c3r1,c4r1).
right(c4r2,c5r2).
right(c4r3,c5r3).
box(c5r2).
box(c3r2).
solution(c2r1).
solution(c1r3).
sokoban(c4r3).

soko7.dl

% ########
% #.     #
% ## #   #
% #@  $  ####
% #   #  $ .# 
% ###########
% 
top(s1z4,s1z3).
right(s1z4,s2z4).
top(s2z4,s2z3).
top(s2z3,s2z2).
top(s2z2,s2z1).
right(s2z1,s3z1).
right(s3z1,s4z1).
top(s4z2,s4z1).
top(s4z3,s4z2).
right(s4z3,s5z3).
top(s5z3,s5z2).
top(s5z2,s5z1).
right(s5z1,s6z1).
top(s6z2,s6z1).
top(s6z3,s6z2).
top(s6z4,s6z3).
right(s6z4,s7z4).
right(s7z4,s8z4).
right(s8z4,s9z4).
top(s5z4,s5z3).
right(s5z4,s6z4).
right(s5z2,s6z2).
right(s5z3,s6z3).
top(s3z4,s3z3).
right(s3z3,s4z3).
right(s4z2,s5z2).
right(s4z1,s5z1).
right(s1z1,s2z1).
right(s2z3,s3z3).
right(s2z4,s3z4).
right(s1z3,s2z3).
box(s4z3).
box(s7z4).
solution(s1z1).
solution(s9z4).
sokoban(s1z3).

Ďaľšie vstypy možno nájsť medzi príkladmi na stránke DLV-K