An answer of http://nabetani.sakura.ne.jp/hena/orde05dokitruck/

yhpg.rb

START_POS = %w(a b c)

MAP = [ 
  [ 'ab', 'ac', 'ac', 'a', 'a', 'ab', 'a', '', 'a' ],
  [ 'bc', 'b', 'ab', 'ab', 'bc', 'b', '', 'b', 'b' ],
  [ 'c', 'bc', 'c', 'bc', 'ac', 'ac', 'c', 'c', '' ],
]

def can_goal(str, path)
  return !str.empty? if (path.empty?) or (str.empty?)
  next_str = str.gsub(/./) { |chr| MAP[chr.ord - START_POS[0].ord][path[0].to_i - 1] }
  can_goal(next_str, path[1..-1])
end

def solve(path)
  ans = START_POS.select { |chr| can_goal(chr, path) }
  ans.empty? ? '-' : ans.join
end

def test(src, expected)
  actual = solve(src)
  puts (actual == expected ? 'ok' : "***NG***: #{actual} does not match #{expected}")
end

[
  [ '172839', 'bc' ],
  [ '789', '-' ],
  [ '274', 'ac' ],
  [ '185', 'abc' ],
  [ '396', 'ab' ],
  [ '1278', 'abc' ],
  [ '7659832', 'a' ],
  [ '178', 'bc' ],
  [ '189', 'ab' ],
  [ '197', 'a' ],
  [ '278', 'ac' ],
  [ '289', 'bc' ],
  [ '297', 'a' ],
  [ '378', 'ac' ],
  [ '389', 'b' ],
  [ '397', 'ab' ],
  [ '478', 'c' ],
  [ '489', 'bc' ],
  [ '497', 'ab' ],
  [ '578', 'bc' ],
  [ '589', 'b' ],
  [ '597', 'ac' ],
  [ '678', 'c' ],
  [ '689', 'ab' ],
  [ '697', 'ac' ],
  [ '899', 'b' ],
  [ '7172', 'ac' ],
  [ '54787', 'bc' ],
  [ '83713', 'bc' ],
  [ '149978', '-' ],
  [ '159735', 'abc' ],
  [ '1449467', 'abc' ],
  [ '9862916', 'b' ],
  [ '96112873', 'ab' ],
  [ '311536789', '-' ],
  [ '281787212994', 'abc' ],
  [ '697535114542', 'ac'],
].each do |src, expected|
  test(src, expected)
end