Solves the path-of-primes puzzle at http://www.sporcle.com/games/smenks13/path-of-primes.

menke.rb

#!/Users/jsomers/.rvm/rubies/ruby-1.9.2-p290/bin/ruby
require 'prime'

class Menke
  def initialize(numbers)
    @numbers = numbers
    @grid = make_grid
  end
  
  def solve!
    while (squares = @grid.select {|_, s| just_fed?(s)}).any?
      squares.each do |c, square|
        feed_ancestor(square, :top) if c[0] != 0
        feed_ancestor(square, :left) if c[1] != 0
      end
    end
    draw(plausible_paths.detect {|pp| works?(pp)})
  end
  
  private
  
  def make_grid
    @numbers.each_with_index.inject({}) do |grid, (n, i)|
      coordinates = [i / side_length, i % side_length]
      grid[coordinates] = { number: n,
                            factors: prime_factors(n), 
                            down_sets: n.zero? ? [[]] : [],
                            right_sets: n.zero? ? [[]] : [],
                            fed_down: bottom_edge?(coordinates),
                            fed_right: right_edge?(coordinates),
                            coordinates: coordinates }
      grid
    end
  end
  
  def draw(path)
    puts("".tap do |s|
      @grid.each_with_index do |sq, i|
        s << (path.include?(sq[0]) ? "1" : "0")
        s << "\n" if sq[0][1] == side_length - 1
      end
    end)
  end
  
  def works?(path)
    path.inject([]) { |factors, c|
      square = @grid[c]
      factors = execute(factors, square[:factors])
    }.empty?
  end
  
  # Answers the question: [3, 5, 7, 13] => 2, 5 => [?]
  def execute(current_factors, other_factors)
    ((current_factors - other_factors) + (other_factors - current_factors)).sort
  end
  
  def plausible_paths
    paths = [[[0, 0]]]
    while paths.any? {|p| finished?(p)}
      paths.select {|p| finished?(p)}.each do |path|
        case (pos = possibilities(path.last)).length
        when 0
          paths.delete(path)
        when 1
          path << pos.first
        else
          duplicate_path = path.dup
          path << pos.first
          paths << (duplicate_path << pos.last)
        end
      end
    end
    paths
  end
  
  def finished?(path)
    path.last != [side_length - 1, side_length - 1]
  end
  
  def possibilities(coordinates)
    [].tap do |pos|
      square = @grid[coordinates]
      
      if square[:right_sets].any? && can_move?(square, :right)
        pos << [coordinates[0], coordinates[1] + 1]
      end
      if square[:down_sets].any? && can_move?(square, :down)
        pos << [coordinates[0] + 1, coordinates[1]]
      end
    end
  end
  
  def can_move?(square, dir)
    c = square[:coordinates]
    dest = (dir == :right ? @grid[[c[0], c[1] + 1]] : @grid[[c[0] + 1, c[1]]])
    dest && sets(dest).any?
  end
  
  def just_fed?(square)
    fully_fed?(square) && ancestors(square).any? {|a| !fully_fed?(a)}
  end
  
  def fully_fed?(square)
    square[:fed_down] && square[:fed_right]
  end
  
  def shouldnt?(candidate_set, ancestor)
    impossible?(candidate_set, ancestor) || sets(ancestor).include?(candidate_set)
  end
  
  def impossible?(set, square)
    (set - ancestry(square).map {|coord, sq| sq[:factors]}.flatten).any?
  end
  
  def ancestry(square)
    @grid.select do |c, s| 
      s != square && 
        c[0] <= square[:coordinates][0] && 
        c[1] <= square[:coordinates][1]
    end
  end
  
  # Answers the question: [?] => 2, 5 => [2, 3, 7, 13]
  def set_needed_to_get_to_desired(set, factors)
    ((factors - set) + (set - factors)).sort
  end
  
  def sets(square)
    square[:down_sets] | square[:right_sets]
  end
  
  def ancestors(square)
    [ancestor(square, :left), ancestor(square, :top)].compact
  end
  
  def feed_ancestor(square, dir)
    feeder = (dir == :left ? :right : :down)
    ancestor = ancestor(square, dir)
    sets(square).each do |set|
      candidate_set = set_needed_to_get_to_desired(set, ancestor[:factors])
      ancestor[:"#{feeder}_sets"] << candidate_set unless shouldnt?(candidate_set, ancestor)
    end
    ancestor[:"fed_#{feeder}"] = true
  end
  
  def ancestor(square, dir)
    c = square[:coordinates]
    dir == :left ? @grid[[c[0], c[1] - 1]] : @grid[[c[0] - 1, c[1]]]
  end
  
  def right_edge?(coordinates)
    coordinates[1] == side_length - 1
  end
  
  def bottom_edge?(coordinates)
    coordinates[0] == side_length - 1
  end
  
  def side_length
    Math::sqrt(@numbers.length).to_i
  end
  
  def prime_factors(n)
    n.zero? ? [] : n.prime_division.map {|divisor, power| divisor}
  end
end

menke = Menke.new([0, 12, 25, 16, 56, 
                   4, 36, 20, 40, 32, 
                   28, 5, 24, 65, 27, 
                   10, 3, 14, 21, 42, 
                   15, 18, 9, 26, 0])
menke.solve!