#C5.txt: Feb. 7, 2013, One-person games (aka SOlitaire,
#puzzles

Help:=proc() : print(`Children(L,n), Qnk(n,k)`): 
print(`RandDi(n,k) , Sphere(G,i,k) `):
end:

#Children(L,n): inputs a legal placement of
#queens on a nops(L) by n board and finds
#all the legal extensions
#For example,
#Children([2,5,1],6);
#should give
#{[2,5,1,4],[2,5,1,6]}
Children:=proc(L,n) local i,S,s,k:
k:=nops(L):

S:={}:

 for s from 1 to n do
   if not s in L and
  {false,
    seq(evalb(abs(L[i]-s)=abs(k+1-i)), i=1..k)}={false} then
    S:=S union {[ op(L), s] }:
   fi:
 od:
S:
end:









#Qnk(n,k): the set of ways of placing k-non-attacking
#queens on a k by n chess-board, represented as
#[a1,a2,,,,, a_k] where a1 is the column of the
#queen at the first row etc.
Qnk:=proc(n,k) local S,L:
option remember:

if k=0 then
  RETURN({[]}):
fi:

S:=Qnk(n,k-1):

{seq(op(Children(L,n)), L in S)}:



end:


#RandDi(n,k): a random directed graph with n
#vertices and (usually) outdegree k 
RandDi:=proc(n,k) local ra,i,j:
ra:=rand(1..n):

[seq({seq(ra(),i=1..k)} minus {j} ,j=1..n)]:

end:


#Sphere(G,i,k): inputs a directed graph G
#(represented as a list of sets where G[i]
#is the set of outgoing neighbors of vertex i)
#and a vertex i (an integer between 1 and nops(G))
#and a non-neg. integer k, outputs the
#set of all vertices for which you can walk
#from i to it with k steps but no less
Sphere:=proc(G,i,k) local S,s,k1:
option remember:

if k=0 then
 RETURN({i}):
fi:

S:=Sphere(G,i,k-1):

 
{seq(op(G[s]),s in S)}
minus
{ seq(op(Sphere(G,i,k1)),k1=0..k-1)}:

end:

#Spheres(G,i): inputs a directed graph
#and a vertex i (from 1 to nops(G))
#and outputs the list of all concentric spheres
#until it is empty
Spheres:=proc(G,i) local tim,k:

for k from 1 while Sphere(G,i,k)<>{} do od:

[ seq( Sphere(G,i,tim), tim=1..k) ]:

end:


#a missionaries and a cannibals, right now
#you have P=[i,j,b] 
#i missionaries and j cannibals
#on the left bank of the river ,and hence
#a-i and a-j resp. on the other bank
#b=0 if the boat is on the left bank
#and b=1 if the boat is on the right bank
MMChildren:=proc(a,P)local i,j,b:

i:=P[1]: j:=P[2]: b:=P[3]:

#if i>0 then j<=i
#if i<a then i<=j
if b=0 then
fi:

#To be  continued as homework

end: