dungen

#const width=10.
#const height=10.
#const min_solve_length = 33.

dim(1..width).
tile_type(water;floor;gem;tree;player).

1 {at(X,Y,T) : tile_type(T)} 1
  :- dim(X), dim(Y).

start(1,1).
finish(width,height).

% The player has to start at the start tile
:- start(X, Y), not at(X,Y,player).
% There can only be one tile with the player at it
1 {at(X,Y,player) : dim(X), dim(Y)} 1.

step(0,-1; 0,1; 1,0; -1,0).

passable_tile(floor).
passable_tile(gem).
passable_tile(player).
passable(X,Y) :- at(X,Y,T), passable_tile(T).

reachable(X,Y) :- start(X,Y), at(X,Y,T), passable_tile(T).
reachable(NX, NY) :-
  reachable(X,Y),
  step(DX, DY),
  NX = X + DX,
  NY = Y + DY,
  at(NX,NY,floor).

solvable :- finish(X,Y), reachable(X,Y).

:- not solvable.

%% Adding minimum solve length

reachable_in(X, Y, 0) :- start(X,Y), at(X,Y,floor).
reachable_in(NX, NY, T+1) :-
  reachable_in(X, Y, T),
  T < min_solve_length,
  step(DX,DY),
  NX = X + DX,
  NY = Y + DY,
  at(NX, NY, floor).

finish_in(T) :- finish(X,Y), reachable_in(X, Y, T).

speedrun :- finish_in(T), T < min_solve_length.

:- speedrun.

#show at/3.
% #show finish_in/1.

4 {at(X,Y,gem) : dim(X), dim(Y)}.