Here's my solution. It got longer and messier than I wanted, but I tried to be
fairly general. Here's the basic structure:

Button: A struct of a label, an x-coord, and a y-coord

ButtonSequence: An array of Buttons.

Pad: A hash of String labels ('0' thru '9' & '*') to Buttons

metrics: Not a class of their own, just a Proc taking a ButtonSequence and
         returning a numeric score (lower is better)

MetricStack: An array of metrics to be tried in order when there's a tie.

alternator: Not a class, just Procs taking a seconds value and returing an
            Enumerable of alternate, equivalent seconds values to try (used
            for tolerance).

Then there is the main microwave() function that takes a seconds value, a Pad,
an alternator, and a MetricStack [and a list() function to run microwave() on
a bunch of values). These are spread among the 4 files below. Here's some
examples of how it can be used:

# Use default pad, the Exact alternator which returns just [76], and the
# EuclideanMetric for a distance metric.
# to_s is called because a ButtonSequence is returned.
microwave(76).to_s
=> "76*"

# Use a pad with buttons twice as wide.
microwave(76, Pad.stretched_pad(2,1)).to_s
=> "76*"

# Allow a tolerance of up to 5 seconds.
microwave(76, Pad.normal_pad, Tolerance[5]).to_s
=> "80*"

# First, try to minimize Euclidean distance. If there's a tie, try to minimize
# the total number of buttons pressed. If there's still a tie, try to minimize
# the number of unique buttons pressed.
ms = MetricStack.new([EuclideanMetric, LowButtonMetric, MinButtonMetric])
microwave(71, Pad.normal_pad, Exact, ms).to_s
=> "111*"

And now here's the code:

# ----------------------------------------------------------------------------
# pad.rb
# Ruby Quiz 118: Microwave Numbers

Button = Struct.new(:label, :x, :y)

# Holds Buttons. I thought about making this a Comparable, or of making
# subclasses of this for different orderings, but didn't.
class ButtonSequence < Array
  def to_s
    self.map{ |b| b.label }.join
  end
end

# Maps button labels (Strings) to Buttons.
class Pad < Hash
  # Return an Array containing all ways of entering the given number of
  # seconds into the microwave. Each entry will be a pair of minutes &
  # seconds.
  def Pad.entries(seconds)
    ent = []
    minutes = seconds / 60
    (0..minutes).each do |min|
      sec = seconds - 60*min
      ent << [min, sec] if sec < 100
    end
    ent
  end

  # Return a String of keys to press on the microwave to enter the given
  # number of minutes and seconds. sec must be < 100.
  def Pad.what_to_press(min, sec)
    raise 'sec is too large' if sec >= 100
    str = ''
    str << min.to_s if min > 0
    str << '0' if sec < 10 and min > 0
    str << sec.to_s
    str << '*'
    str
  end

  # For the given number of seconds, yield each possible button sequence as an
  # ButtonSequence.
  def each_button_sequence(seconds)
    Pad.entries(seconds).each do |ent|
      press_str = Pad.what_to_press(*ent)
      bs = ButtonSequence.new(press_str.split(//).map { |char| self[char] })
      yield(bs)
    end
  end

  # Generate a pad like this:
  #           x
  #       0   1   2
  #    +---+---+---+
  #  0 | 1 | 2 | 3 |
  #    +---+---+---+
  #  1 | 4 | 5 | 6 |
  # y   +---+---+---+
  #  2 | 7 | 8 | 9 |
  #    +---+---+---+
  #  3   | 0 | * |
  #      +---+---+
  def Pad.normal_pad
    stretched_pad(1, 1)
  end

  # Generate a pad like the normal one, but stretched either horizontally,
  # vertially, or both. x_factor and y_factor must be integers. For example,
  # Pad.stretched_pad(3,1) would produce a pad with buttons 3 times wider
  # than they are tall.
  def Pad.stretched_pad(x_factor, y_factor)
    pad = Pad.new
    (1..9).each do |n|
      pad[n.to_s] = Button.new(n.to_s, x_factor*((n-1) % 3),
                                       y_factor*((n-1) / 3))
    end
    pad.merge!( { '0' => Button.new('0',   x_factor, 3*y_factor),
                  '*' => Button.new('*', 2*x_factor, 3*y_factor) } )
    pad
  end
end

# ----------------------------------------------------------------------------
# metrics.rb
# Ruby Quiz 118: Microwave Numbers

# To decide which button sequences are better than others, a metric is used. I
# didn't bother creating a Metric class, so they're just a Proc that takes a
# ButtonSequence as an argument and returns a numeric score (lower is always
# better). To settle ties, a MetricStack is used, which is an Array of metrics
# that are tried in order until the tie is broken (if its ever broken).

require 'set'

class Array
  # Yield all Arrays containing two adjacent elements.
  def each_adjacent_pair
    (1...self.size).each do |i|
      yield([self[i-1], self[i]])
    end
  end

  # Return the number of unique elements.
  def num_uniq
    Set[*self].size
  end
end

# Create a Proc returns the n-norm of two Buttons.
def create_norm_distancer(n)
  lambda do |b1, b2|
    ((b1.x - b2.x).abs**n + (b1.y - b2.y).abs**n) ** (1.0/n)
  end
end

ManhattanDistance = create_norm_distancer(1)
EuclideanDistance = create_norm_distancer(2)

# Create a distance-measuring metric from the given distance measurer.
def create_distance_metric(dist_measurer)
  lambda do |button_sequence|
    dist = 0
    button_sequence.each_adjacent_pair do |button_pair|
      dist += dist_measurer[button_pair.first, button_pair.last]
    end
    dist
  end
end

ManhattanMetric = create_distance_metric(ManhattanDistance)
EuclideanMetric = create_distance_metric(EuclideanDistance)

# A metric that minimizes the total number of buttons pressed.
MinButtonMetric = lambda do |button_sequence|
  button_sequence.size
end

# A metric that minimizes the number of unique buttons pressed.
LowButtonMetric = lambda do |button_sequence|
  button_sequence.num_uniq
end

# A MetricStack is an Array of metrics that compare ButtonSequences. Earlier
# metrics take precedence over later metrics.
class MetricStack < Array
  # Return true if button_seq_1 is better than button_seq_2.
  def better?(button_seq_1, button_seq_2)
    return true if not button_seq_1.nil? and button_seq_2.nil?
    better = nil
    self.each do |metric|
      s1, s2 = metric[button_seq_1], metric[button_seq_2]
      s1 < s2 ? better = true : s2 < s1 ? better = false : nil
      break if not better.nil?
    end
    better.nil? ? false : better
  end
end

# ----------------------------------------------------------------------------
# alternators.rb
# Ruby Quiz 118: Microwave Numbers

# For "something that produces alternate seconds values" I'm using the word
# "alternator" - it can be any Proc that takes as an argument the number of
# seconds, and returns an Enumerable of "close enough" seconds to try.

require 'set'

Exact = lambda { |seconds| [seconds] }

# Produce an alternator that will return all seconds within the given 
tolerance
# from the target number of seconds (eg, Tolerance[2][10] will return 
(8..12)).
Tolerance = lambda do |tolerance|
  lambda do |seconds|
    ([seconds - tolerance, 0].max..seconds + tolerance)
    # Any way to pass a block to a Proc?
    #([seconds - tolerance, 0].max..seconds + tolerance).each do |sec|
    #  yield(sec)
    #end
  end
end

# Produce a few values close by. This isn't really useful, just an example of
# another alternator.
RandomClose = lambda do |seconds|
  s = Set[seconds]
  (rand(10)+1).times { s << [seconds + rand(21) - 10, 0].max }
  s
end

# ----------------------------------------------------------------------------
# microwave.rb
# Ruby Quiz 118: Microwave Numbers

require 'metrics'
require 'pad'
require 'alternators'

# alternator is a Proc that takes the number of seconds and produces an
# Enumerable of equivalent values.
#
# metrics can be:
#   - a MetricStack
#   - a single metric Proc
#   - an Array of metric Procs
def microwave(seconds, pad = Pad.normal_pad,
              alternator = Exact, metrics = EuclideanMetric)
  case metrics
    when Proc;  metrics = MetricStack.new([metrics])
    when Array; metrics = MetricStack.new(metrics)
  end
  best = nil
  alternator[seconds].each do |sec|
    pad.each_button_sequence(sec) do |bs|
      best = bs if metrics.better?(bs, best)
    end
  end
  best
end

# Print out the best button sequences for all seconds in the given Enumerable.
# Other arguments are passed into microwave(). The thing that sucks about
# this is that if there's a tolerance of > 0, identical sequences will be
# scored more than once. Maybe memo-ize that or something..
def list(enum, pad = Pad.normal_pad,
         alternator = Exact, metrics = EuclideanMetric)
  puts "Seconds   Buttons"
  puts "-------   -------"
  enum.each do |i|
    best = microwave(i, pad, alternator, metrics)
    puts "#{i}         #{best}"
  end
end
# ----------------------------------------------------------------------------

-- 
Jesse Merriman
jessemerriman / warpmail.net
http://www.jessemerriman.com/