Enigmatic Code

Programming Enigma Puzzles

From New Scientist #2734, 14th November 2009 [link]

I have designed a snakes and ladders board. It is a 10-by-10 grid numbered 1 to 10 from left to right in the bottom row, then 11 to 20 from right to left in the next row, 21 to 30 from left to right in the next and so on, ending at 100 in the top left-hand corner.

Each ladder is a thin straight line from the centre of one square up to the centre of another square. None goes up vertically and no two of the ladders touch or cross each other. If a ladder started, say, in the second row up and went to the seventh row up then it would completely jump over four rows. In fact, my seven ladders all jump over at least one row and they all jump different numbers of rows from each other.

The numbers at the bottom of the ladders are all perfect squares larger than 1, and the numbers at the top of the ladders are all prime numbers. List the starts and finishes of all the ladders (in the form 4-a, 9-b, etc).

[enigma1571]

2 responses to “Enigma 1571: Just ladders”

1. jimrandell 15 February 2012 at 6:36 pm

The following Python program runs in 105ms (using `floats` instead of `Fractions` gets this down to 40ms).

```from fractions import Fraction
from enigma import irange, is_prime, printf

squares = [x * x for x in irange(2, 8)]
primes = [x for x in irange(21, 100) if is_prime(x)]

# find the x,y co-ordinates of the squares and primes
(X, Y) = ({}, {})
for n in squares + primes:
(y, x) = divmod(n - 1, 10)
(X[n], Y[n]) = ((9 - x if y % 2 else x), y)

def solve(i, lines, rows):
# are we done? i.e. we have a line for each square
if i < 0:
for s in sorted(lines.keys()):
p = lines[s]
printf("{s}-{p} [{y}]", y=Y[p]-Y[s]-1)
return
s = squares[i]
# find a prime that isn't used yet
for p in primes:
if p in lines.values(): continue
if X[p] == X[s]: continue # not in the same column
r = Y[p] - Y[s]
if r < 2: continue # prime must be at least 2 rows higher
if r in rows: continue # and the row count must be unique
if intersect(s, p, lines): continue # can't intersect with existing lines
# try the solution with this line
lines[s] = p
if solve(i-1, lines, rows + [r]): return
# otherwise remove the line
del lines[s]

def intersect(s, p, lines):
"intersect(s, p, lines): check line s->p doesn't intersect with any existing lines"
# line parameters (y = mx + c)
m = Fraction(Y[s] - Y[p], X[s] - X[p])
c = Y[s] - m * X[s]
for (sl, pl) in lines.items():
ml = Fraction(Y[sl] - Y[pl], X[sl] - X[pl])
cl = Y[sl] - ml * X[sl]
# if the lines are parallel they don't interset
if m == ml: continue
# else find out where they do intersect
x = (c - cl) / (ml - m)
# is it inside the line?
if min(X[s], X[p]) <= x <= max(X[s], X[p]) and min(X[sl], X[pl]) <= x <= max(X[sl], X[pl]):
return True
return False

solve(len(squares)-1, {}, [])
```

Solution: The ladders are at 4-79, 9-53, 16-97, 25-89, 36-73, 49-71 and 64-83.

This site uses Akismet to reduce spam. Learn how your comment data is processed.