Teaser 3263: Snakes and ladders
From The Sunday Times, 6th April 2025 [link] [link]
My “Snakes and Ladders” board has numbers from 1 to 100 — you throw a die repeatedly and work your way up. There are three “snakes”, each taking you down from one perfect square to another, and three “ladders”, each taking you up from one prime to another. The twelve ends of the snakes and ladders are different two-digit numbers. You must go down a snake if you land on its top-end, and up a ladder if you land on its bottom-end.
For any number from 1 to 6, if I throw that same number repeatedly then I eventually land on 100. The number of throws of 4 needed (with first stops 4, 8, …) is one more than when throwing 5s, which is more than when throwing 3s.
What are the three ladders (in the form “p to q“)?
[teaser3263]
Frits and 
GeoffR, 
Ruud, and 
S2T2 
Jim Randell 7:47 am on 6 April 2025 Permalink |
Here is my first go at a solution.
It constructs all possible arrangements of snakes and ladders, and then checks to see if valid sequences of moves can be made. This is quite slow, as although there are only a few possible arrangements for the snakes, there are a lots of possible ladder arrangements to consider.
It runs in 22.8s (using PyPy).
from enigma import (irange, primes, subsets, partitions, update, printf) # play the game, constantly throwing <d> # return: <sequence-of-positions> or None def play(d, m, p=0): ps = list() while True: # move d spaces p += d # have we hit a special position? p = m.get(p, p) # have we hit a loop? if p in ps: return ps.append(p) # are we done? if p >= 100: return ps # check map <m> of special positions for a solution def check(m): n = dict() for d in [4, 5, 3, 6, 2, 1]: # each play eventually gets to 100 ps = play(d, m) if ps is None or ps[-1] != 100: return n[d] = ps # check n4 = n5 + 1 if d == 5 and not (len(n[4]) == len(n[5]) + 1): return # check n3 < n5 if d == 3 and not (len(n[3]) < len(n[5])): return # return the moves for each die value return n # collect 2-digit squares and primes sqs = list(i * i for i in irange(4, 9)) prs = list(primes.between(10, 99)) # choose k special positions def special(ss, k, r, m): # choose k positions for xs in subsets(ss, size=k): # pair them up for ps in partitions(xs, 2, distinct=1): # add them to the map yield update(m, (sorted(pair, reverse=r) for pair in ps)) # choose 6 ends for the snakes (squares) and ladders (primes) for m0 in special(sqs, 6, 1, dict()): for m in special(prs, 6, 0, m0): # check for solution n = check(m) if n: # output solution for (x, y) in m.items(): printf("{x} -> {y} {z}", z=("ladder" if x < y else "snake")) printf() for d in sorted(n.keys()): printf("{d} -> {k} throws {v}", k=len(n[d]), v=n[d]) printf()Solution: The ladders are: 19 → 97, 29 → 73, 31 → 43.
And the snakes are: 36 → 25, 49 → 16, 81 → 64.
The number of throws for each die value are as follows:
With a standard board layout it looks like this:
(Snakes in red; Ladders in green).
LikeLike
Jim Randell 2:41 pm on 8 April 2025 Permalink |
Here is a faster approach:
This Python 3 program starts by repeatedly throwing a die value and travelling along the board. When it hits a potential “special” square it either allocates a snake/ladder or does nothing, until it completes a sequence that ends on 100. Once this is achieved it takes the partially completed board and then tries another die value, until all values have achieved valid sequences. The completed board (and sequences) are then returned.
It runs in 115ms. (Internal runtime is 40ms).
from enigma import (irange, primes, update, remove, printf) # collect 2-digit squares and primes sqs = list(i * i for i in irange(4, 9)) prs = list(primes.between(10, 99)) # play the game, repeatedly throwing <d> # m = behaviour of positions (src -> tgt) # p = current position # ps = previous positions # sps = positions for snakes # lps = positions for ladders # ns = remaining snakes # nl = remaining ladders # return updated (m, ps, sps, lps, ns, nl) values def play(d, m, p, ps, sps, lps, ns, nl): # are we done? if p >= 100: yield (m, ps, sps, lps, ns, nl) else: # move <d> spaces p += d x = m.get(p) if x is not None: # behaviour of position is already allocated if x not in ps: yield from play(d, m, x, ps + [x], sps, lps, ns, nl) else: # decide the behaviour of this position, either: # -> p is not a special square if p not in ps: yield from play(d, update(m, [(p, p)]), p, ps + [p], sps, lps, ns, nl) # -> p is the bottom of a ladder if nl > 0 and p in lps: # move to a higher ladder position for x in lps: if not (x > p): continue if x not in ps: yield from play(d, update(m, [(p, x)]), x, ps + [x], sps, remove(lps, p, x), ns, nl - 1) # -> p is the top of a snake if ns > 0 and p in sps: # move to a lower snake position for x in sps: if not (x < p): break if x not in ps: yield from play(d, update(m, [(p, x)]), x, ps + [x], remove(sps, p, x), lps, ns - 1, nl) # solve the puzzle for repeated throws in <ds> # m = behaviour of positions (src -> tgt) # sps = positions for snakes # lps = positions for ladders # ns = remaining snakes # nl = remaining ladders # ss = sequences recorded # return (m, ss) def solve(ds, m, sps, lps, ns, nl, ss=dict()): # are we done? if not ds: yield (m, ss) else: # try the next sequence d = ds[0] for (m_, ps_, sps_, lps_, ns_, nl_) in play(d, m, 0, [], sps, lps, ns, nl): # check the sequence ends on 100 if not (ps_[-1] == 100): continue ss_ = update(ss, [(d, ps_)]) # check n4 = n5 + 1 if d == 4 or d == 5: (ss4, ss5) = (ss_.get(4), ss_.get(5)) if ss4 and ss5 and not (len(ss4) == len(ss5) + 1): continue # check n3 < n5 if d == 3 or d == 5: (ss3, ss5) = (ss_.get(3), ss_.get(5)) if ss3 and ss5 and not (len(ss3) < len(ss5)): continue # solve for the remaining sequences yield from solve(ds[1:], m_, sps_, lps_, ns_, nl_, ss_) # solve for repeated throws 1 - 6, with 3 snakes on squares, 3 ladders on primes for (m, ss) in solve([6, 5, 4, 3, 2, 1], dict(), sqs, prs, 3, 3): # output layout for s in sorted(m.keys()): t = m[s] if s < t: printf("{s} -> {t} ladder") if s > t: printf("{s} -> {t} snake") printf() # output sequences for d in sorted(ss.keys()): ts = ss[d] printf("{d} -> {n} throws {ts}", n=len(ts)) printf()LikeLike
Frits 6:25 pm on 7 April 2025 Permalink |
Similar to Jim’s program.
It runs under 10 seconds (using PyPy).
# -------------------------------- start Jim Randell ------------------------ # play the game starting with list <lst>, constantly throwing <d> # return: <sequence-of-positions> or None def play(d, m, lst): ps = list(lst) p = lst[-1] while True: # move d spaces p += d # have we hit a special position? p = m.get(p, p) # have we hit a loop? if p in ps: return ps.append(p) # are we done? if p >= 100: return ps # check map <m> of special positions for a solution def check_sol(m): n = dict() for d in [4, 5, 3, 6, 2, 1]: # each play eventually gets to 100 ps = play(d, m, f_lst[d]) if ps is None or ps[-1] != 100: return n[d] = ps # check n4 = n5 + 1 if d == 5 and not (len(n[4]) == len(n[5]) + 1): return # check n3 < n5 if d == 3 and not (len(n[3]) < len(n[5])): return # return the moves for each die value return n # -------------------------------- end Jim Randell -------------------------- prms = [x for x in range(11, 100, 2) if all(x % p for p in [3, 5, 7])] sqs = [i * i for i in range(4, 10)] # 2-digit squares spec = prms + sqs # mandatory first numbers f_lst = {n: list(range(n, next(x for x in range(n, 100, n) if x in spec and x not in {sqs[0], prms[-1]}), n)) for n in range(1, 7)} # generate all possible combinations of 3 ladders ladders = [] inds = {x: i for i, x in enumerate(prms)} for P in prms[:-3]: for Q in prms[inds[P] + 1:]: for R in prms[inds[P] + 1:-2]: if R == Q: continue for S in prms[inds[R] + 1:]: if S == Q: continue for T in prms[inds[R] + 1:-1]: if T in {Q, S}: continue for U in prms[inds[T] + 1:]: if U in {Q, S}: continue ladders.append((P, Q, R, S, T, U)) # generate all possible combinations of 3 snakes for a in range(5, 9): A = a * a for b in range(4, a): B = b * b for c in range(a + 1, 9): C = c * c for d in range(4, c): if d in {a, b}: continue D = d * d e = 9 E = e * e f = 39 - a - b - c - d - e if f in {a, b, c, d}: continue F = f * f # create snake dictionary d = {A: B, C: D, E: F} for lddr in ladders: d_ = d.copy() # add ladder data to dictionary d_.update({lddr[i]: lddr[i + 1] for i in range(0, 6, 2)}) # check for solution if (n := check_sol(d_)) is None: continue print("answer:", *[lddr[i:i+2] for i in range(0, 6, 2)])LikeLike
Frits 7:13 pm on 8 April 2025 Permalink |
New approach, again without using analysis.
The main line can probably done with recursion but I didn’t feel like doing that.
It run in approx. 18ms (using Cpython).
prms = [x for x in range(11, 100, 2) if all(x % p for p in [3, 5, 7])] sqs = [i * i for i in range(4, 10)] # 2-digit squares spec = prms + sqs # dictionary of mandatory last numbers dlast = {n: tuple(range(next(x for x in range(100 - n, 0, -n) if x in spec and x not in {sqs[-1], prms[0]}), 100 + n, n)) for n in range(1, 7)} # dictionary of mandatory first numbers dfirst = {n: tuple(range(n, next(x for x in range(n, 100, n) if x in spec and x not in {sqs[0], prms[-1]}), n)) for n in range(1, 7)} # go from number <a> to <b> by adding a maximum of <k> board numbers # between <a> and <b> with standard throws <m> and <kn> = known snakes/ladders def solve(m, a, b, k, ns=0, nl=0, kn=set(), ss=[], new=set()): tst = (11, 83) in kn | new # <k> fields cause <k + 1> moves if k == -1 or a == b: if a == b: yield len(ss) - 1, kn | new, ns, nl else: # new number may not have been seen before if (n := a + m) in ss or n > 100: return # try standard throw if not on a kn snake of ladder if n not in {x for x, y in kn}: yield from solve(m, n, b, k - 1, ns, nl, kn, ss + [n], new) # try to add a snake if n in sqs: for s in sqs: if s == n: break # do checks for new snake if (n, s) not in kn: if ns > 2 or not set(sum(kn | new, ())).isdisjoint({n, s}): continue ns_ = ns + 1 else: ns_ = ns yield from solve(m, s, b, k - 1, ns_, nl, kn, ss + [s], new | {(n, s)}) # try to add a ladder if n in prms: for p in prms[::-1]: if p == n: break # do checks for new ladder if (n, p) not in kn: if nl > 2 or not set(sum(kn | new, ())).isdisjoint({n, p}): continue nl_ = nl + 1 else: nl_ = nl yield from solve(m, p, b, k - 1, ns, nl_, kn, ss + [p], new | {(n, p)}) def six_throws(seq, ln5=0, ns=0, nl=0, kn=set(), ss=[]): if not seq: if len(kn) == 6: yield kn else: m = seq[0] mx = (107 if m not in {3, 4} else ln5 + (2 * m - 7) - len(dfirst[m]) - len(dlast[m])) for ln, kn_, ns_, nl_ in solve(m, dfirst[m][-1], dlast[m][0], mx, ns, nl, kn): if m == 4: # check requirement if len(dfirst[m]) + len(dlast[m]) + ln != ln5 + 1: continue if m == 5: # save number of throws of 5 needed ln5 = len(dfirst[m]) + len(dlast[m]) + ln yield from six_throws(seq[1:], ln5 , ns_, nl_, kn_, ss) # perform 2 passes as some ordr's generate incorrect solutions ordr = (5, 4, 3, 6, 2, 1) # one of the most efficient orders # 1st pass: start with no known snakes and ladders for p1 in six_throws(ordr): # 2nd pass: check again with a full set of snakes and ladders sols = [] for p2 in six_throws(ordr, 0, 3, 3, p1): if p2 not in sols: if p1 != p2: print("ERROR") exit(0) sols.append(p2) for s in sols: print("answer:", *[(x, y) for x, y in sorted(s) if x not in sqs])LikeLike