model 'nim' ! nim.mos : Computes move to safe position (if available) in game of Nim ! Written by : Martin J. Chlond ! Date written : 26 December 2001 uses 'mmxprs' parameters heap = 5 ! number of heaps col = 4 ! columns for binary representation of position after move k = 1 ! maximum number of heaps to change (if k>1 then Moore's game) ! number of squares per side end-parameters declarations nmax=2^col-1 ! maximum number allowed in any heap n: array(1..heap) of real !variables x: array(1..heap,1..col) of mpvar ! binary values of position after move d: array(1..heap) of mpvar ! 1 if heap changed, 0 otherwise s: array(1..heap) of mpvar ! number taken from heap m: array(1..heap) of mpvar ! number in each heap after move w: array(1..col) of mpvar ! dummy variables for winning position test end-declarations n:=[5,4,3,2,1] ! number in each heap before move ! number of heaps changed heapch:= sum(i in 1..heap) d(i) ! convert heap numbers (after move) to binary forall(i in 1..heap) conb(i):= sum(j in 1..col) 2^(j-1)*x(i,j) = m(i) ! ensures safe position after move forall(j in 1..col) winp(j):= sum(i in 1..heap) x(i,j) = (k+1)*w(j) ! positions before and after are consistent with move forall(i in 1..heap) cons(i):= n(i)-s(i) = m(i) ! dummy set to 1 if heap changed forall(i in 1..heap) dset(i):= s(i)-nmax*d(i) <= 0 forall(i in 1..heap,j in 1..col) x(i,j) is_binary forall (i in 1..heap) do d(i) is_binary s(i) is_integer m(i) is_integer end-do forall(j in 1..col) w(j) is_integer ! minimise number of heaps changed - if solution is zero then current position already safe minimise( heapch ) ! output solution forall(i in 1..heap) do write(getsol(s(i)),' ',getsol(m(i))) writeln end-do end-model