#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