/*
Movement puzzle in Picat.
From StackOverflow
"python recursion: solving movement puzzle"
http://stackoverflow.com/questions/20011395/python-recursion-solving-movement-puzzle
"""
im trying to figure out how to write a recursive python program which takes a list
i.e [1,2,3,4,0] while each number donates [denotes?] the number of steps you can take
left or right. and figure out of a way you to get to the zero cell at the end.
for example [3,6,4,1,3,4,2,5,3,0] , if i start at the leftmost cell(3), i could
take: 3 steps right to the 1 cell -> 1 step back to the 4 cell -> 4 steps right
to the 2 cell- > 2 steps right to the 3 cell -> 3 steps left to the 4 cell -> and
4 steps right to the 0 cell
i can start on any cell on the board.. and also need to figure out when it is
not possible to solve the board.
how do i start to think about this using recursion?
"""
The same problem is described here (also as a recursion homework assignment):
http://see.stanford.edu/materials/icspacs106b/H18-Assign3RecPS.pdf
This model assume that the same cell is used only once (i.e. that it
have just one "direction").
There are three different approaches:
- puzzle/3 CP approach
don't assume that we start at first position, though with Start > 0
it requires the start position.
It also generates random problem instances.
- puzzle2/2 shortest path approach
assumes we start at position 1).
- puzzle3/2 planner approach
assumes we start at position 1.
This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
% import util.
import cp.
import planner.
main => go.
%
% start at position 1 (cited example)
%
go =>
A = [3,6,4,1,3,4,2,5,3,0],
Start = 1,
puzzle(A,Start,X),
print_path2(A,X),
nl.
%
% best possible start (cited example)
%
go1 =>
A = [3,6,4,1,3,4,2,5,3,0],
Start = 0,
puzzle(A,Start,X),
print_path2(A,X),
nl.
%
% Test all start positions
%
go1b =>
A = [3,6,4,1,3,4,2,5,3,0],
println(a=A),
% test all possible start positions
foreach(Start in 1..A.length-1)
puzzle(A,Start,X),
print_path2(A,X),
nl
end,
nl.
% another example
go2 =>
A = [14, 11, 8, 16, 9, 11, 3, 3, 10, 7, 2, 4, 3, 13, 3, 10, 7, 11, 7, 0],
println(a=A),
Start = 0,
puzzle(A,Start,X),
println(x=X),
print_path2(A,X),
nl.
go3 =>
A = [3,6,4,1,3,4,2,5,3,0],
Start = 0,
println(a=A),
time2(All = puzzle_all(A,Start)),
println(All),
println(len=All.length),
nl.
go4 =>
A = [14, 11, 8, 16, 9, 11, 3, 3, 10, 7, 2, 4, 3, 13, 3, 10, 7, 11, 7, 0],
Start = 1,
println(a=A),
time2(All = puzzle_all(A,Start)),
println(All),
println(len=All.length),
nl.
go5 =>
Start = 0,
A = generate_random(10,Start),
Start = 0,
println(a=A),
time2(All = puzzle_all(A,Start)),
println(All),
println(len=All.length),
nl.
% Shortest path approach
go6 =>
% A = [3,6,4,1,3,4,2,5,3,0],
% A = [14, 11, 8, 16, 9, 11, 3, 3, 10, 7, 2, 4, 3, 13, 3, 10, 7, 11, 7, 0],
A = [8, 28, 22, 27, 28, 2, 29, 9, 30, 7, 5, 10, 8, 21, 13, 3, 10, 13, 1, 6, 11, 16, 17, 17, 15, 8, 2, 5, 5, 8, 3, 31, 14, 3, 23, 32, 27, 27, 24, 0],
println(a=A),
puzzle2(A,Path,Cost),
println(path=Path),
println(cost=Cost),
print_path(A,Path),
nl.
%
% Random problem
%
go7 =>
N = 1000,
Found = false,
% Generate until a solvable problem is found.
while (Found == false)
println(generating),
A := generate_random2(N),
(
puzzle2(A,Path,Cost) ->
println(a=A),
println(path=Path),
println(cost=Cost),
print_path(A,Path),
Found := true
;
true
)
end,
nl.
go8 =>
A = [3,6,4,1,3,4,2,5,3,0],
println(a=A),
print_pos(A,1),
puzzle3(A,Path),
foreach([Pos1,Step,Pos2] in Path)
println((pos1=Pos1,step=Step,pos2=Pos2)),
print_pos(A,Pos2)
end,
nl.
%
% puzzle3/2 (planner approach)
%
go9 =>
N = 1000,
Found = false,
% Generate until a solvable problem is found.
while (Found == false)
println(generating),
A := generate_random2(N),
println(finished_generating),
(
puzzle3(A,Path) ->
println(a=A),
println(path=Path),
if N <= 40 then
print_pos(A,1)
end,
foreach([Pos1,Step,Pos2] in Path)
println((pos1=Pos1,step=Step,pos2=Pos2)),
if N <= 40 then
print_pos(A,Pos2)
end
end,
Found := true
;
true
)
end,
nl.
print_pos(A,Pos) =>
foreach(I in 1..A.length)
printf("%d%s ", A[I], cond(I=Pos,"*",""))
end,
nl.
% print a shortest path
print_path(A,Path) =>
foreach((From,To) in Path)
T = To-From,
T2 = abs(T),
Dir = cond(T > 0, "+","-"),
printf("From %3d (%3d) .. %s%3d step(s) .. To %3d (%3d)\n", From, A[From], Dir, T2, To, A[To])
% println([From, A[From], Dir, T2, To, A[To]])
end.
% for CP model solutions (puzzle/3)
print_path2(A,Path) =>
NumSteps = [P : P in Path, P > 0].length,
foreach(Step in 1..NumSteps)
nth(Pos,Path,Step),
printf("Step %2d pos=%2d A[%2d] = %2d\n", Step, Pos, Pos, A[Pos])
end,
nl.
puzzle_all(A,Start) = findall(X,puzzle(A,Start,X)).
%
% CP approach
% Here we don't assume any start position
%
puzzle(A,Start,X) =>
println(a=A),
println(start=Start),
N = A.length,
% decision variables
X = new_list(N),
X :: 0..N,
C #= sum([X[I] #> 0 : I in 1..N]),
% constraints
alldifferent_except_0(X),
% X[N] is the last step of the sequence
X[N] #= max(X),
% X[N] #> 0,
X[N] #> 1, % we cannot start at X[X]
if Start > 0 then
X[Start] #= 1
end,
% The main loop:
% For all entries (x[i] > 0):
% identify position of the previous move in X and the
% length to the next element.
%
foreach(I in 2..N)
(I #<= X[N]) #=>
sum([
X[J] #= I #/\
X[K] #= I-1 #/\
A[K] #= abs(J-K)
: J in 1..N, K in 1..N]) #> 0
end,
%
% connect at the end as well:
% There must be a (proper) last step which is
% connected to X[N].
%
sum([X[J] #= X[N]-1 #/\ A[J] #= N-J : J in 1..N]) #> 0,
solve([ffc,split],X),
% solve($[ffc,split,min(C)],X),
println([x=X,c=C]).
generate_random(N,Start) = A =>
A = new_list(N),
Found = 0,
Mod = cond(N > 4, N - N div 3, N),
while (Found == 0)
A := [1+random2() mod Mod : _I in 1..N-1] ++ [0],
(
puzzle(A,Start,_X) ->
Found := 1
;
true
)
end.
% real random puzzle (perhaps not solvable)
generate_random2(N) = A =>
Mod = cond(N > 4, N - N div 3, N),
A := [1+random2() mod Mod : _I in 1..N-1] ++ [0].
alldifferent_except_0(Xs) =>
foreach(I in 1..Xs.length, J in 1..I-1)
(Xs[I] #!= 0 #/\ Xs[J] #!= 0) #=> (Xs[I] #!= Xs[J])
end.
%
% A graph (shortest path) approach.
%
puzzle2(A, Path,Cost) =>
N = A.length,
% create the graph
Graph = [$edge(I,T,1) : I in 1..N-1, T = I+A[I], T <= N] ++
[$edge(I,T,1) : I in 1..N-1, T = I-A[I], T > 0],
% println(graph=Graph),
cl_facts(Graph,$[edge(+,-,-),edge(-,+,-)]),
shortest_path(1,N,Path,Cost).
%
% General shortest path, requires the fact predicate
% edge(From,To,Weight)
%
table(+,+,-,min)
shortest_path(X,Y,Path,W) ?=>
Path=[(X,Y)],
edge(X,Y,W).
shortest_path(X,Y,Path,W) =>
Path = [(X,Z)|PathR],
edge(X,Z,W1),
shortest_path(Z,Y,PathR,W2),
W = W1+W2.
%
% Planner approach
%
puzzle3(A, Path) =>
best_plan_unbounded([1|A],Path).
% using planner
action([Ix1|L],Ix2L,Move,Cost) ?=>
Cost = 1,
Ix2 = Ix1+L[Ix1],
Ix2 <= L.length,
Ix2L = [Ix2|L],
Move = [Ix1,L[Ix1],Ix2].
action([Ix1|L],Ix2L,Move,Cost) =>
Cost = 1,
Ix2 = Ix1-L[Ix1],
Ix2 > 0,
Ix2L = [Ix2|L],
% pos1,-step,pos2
Move = [Ix1,-L[Ix1],Ix2].
final([Ix|L]) => Ix == L.length.