Enigmatic Code

Programming Enigma Puzzles

Enigma 1571: Just ladders

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.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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

%d bloggers like this: