A program for solving Sam Lloyd's "Back from the Klondike" puzzle.

grid.txt

__________xxx__________
_______xxx477xxx_______
_____xx544833463xx_____
____x1451114517135x____
___x494967555876685x___
__x37298356739187585x__
__x14784292711822763x__
_x7218553113133428613x_
_x4267252422543281773x_
_x4165111914344319827x_
x435232232425351135537x
x271511315332423775427x
x252261244634121265188x
_x4375193445294195748x_
_x4167834341312323624x_
_x7326153923215758954x_
__x16734811121228941x__
__x25478756135787293x__
___x656467252263474x___
____x2312333213211x____
_____xx744573447xx_____
_______xxx334xxx_______
__________xxx__________

klondike.rb

# A class that solves puzzles in the style of Sam Lloyd's
# "Back From the Klondike" puzzle.
#
# (see https://en.wikipedia.org/wiki/Back_from_the_Klondike)
#
# This solver works in two steps:
#
# 1. Convert the puzzle into a graph.
# 2. Apply Dijkstra's algorithm to the graph to find the
#    shortest solution.

class Node
  attr_reader :row, :col
  attr_accessor :distance
  attr_accessor :previous_dir
  attr_accessor :previous_node

  def initialize(row, col)
    @neighbors = {}
    @row, @col = row, col
    @goal = false
    @distance = 1_000_000_000
  end

  def [](direction)
    @neighbors[direction]
  end

  def []=(direction, neighbor)
    @neighbors[direction] = neighbor
  end

  def goal?
    @goal
  end

  def goal!
    @goal = true
  end
end

class Graph
  def self.from_field(field)
    graph = new

    field.each do |value, row, col|
      next unless value
      node = Node.new(row, col)
      graph.add_node(node)
    end

    graph.each do |node|
      row, col = node.row, node.col

      if field[row, col] == :goal
        node.goal!
      else
        distance = field[row, col]

        if field.valid_span?(row, col, row-distance, col)
          node[:n] = graph[row-distance, col]
        end

        if field.valid_span?(row, col, row-distance, col-distance)
          node[:nw] = graph[row-distance, col-distance]
        end

        if field.valid_span?(row, col, row-distance, col+distance)
          node[:ne] = graph[row-distance, col+distance]
        end

        if field.valid_span?(row, col, row+distance, col)
          node[:s] = graph[row+distance, col]
        end

        if field.valid_span?(row, col, row+distance, col-distance)
          node[:sw] = graph[row+distance, col-distance]
        end

        if field.valid_span?(row, col, row+distance, col+distance)
          node[:se] = graph[row+distance, col+distance]
        end

        if field.valid_span?(row, col, row, col-distance)
          node[:w] = graph[row, col-distance]
        end

        if field.valid_span?(row, col, row, col+distance)
          node[:e] = graph[row, col+distance]
        end
      end
    end

    graph
  end

  def initialize
    @nodes = {}
  end

  def add_node(node)
    @nodes[node.row] ||= {}
    @nodes[node.row][node.col] = node
  end

  def [](row, col)
    @nodes[row][col]
  end

  def each
    @nodes.each do |row, rows|
      rows.each do |col, node|
        yield node
      end
    end

    self
  end
end

class Field
  def self.from_file(filename)
    lines = File.readlines(filename)
    lines.map! { |line| line.chomp }
    lengths = lines.map { |l| l.length }.uniq

    rows = lines.length
    cols = lengths.first

    new(rows, cols).tap do |field|
      lines.each_with_index do |line, row|
        line.each_char.with_index do |character, col|
          # Assign each location in the field, based on
          # the corresponding character in the file.
          field[row, col] = case character
            when "_" then nil
            when "x" then :goal
            when /[1-9]/ then character.to_i
            else raise "invalid (#{character.inspect})"
            end
        end
      end
    end
  end

  attr_reader :rows, :columns

  def initialize(rows, columns)
    @rows, @columns = rows, columns
    @field = Array.new(rows) { Array.new(columns) }
  end

  def [](row, col)
    @field[row][col]
  end

  def []=(row, col, value)
    @field[row][col] = value
  end

  def each
    @field.each_with_index do |row, row_idx|
      row.each_with_index do |col, col_idx|
        yield col, row_idx, col_idx
      end
    end

    self
  end

  def valid_span?(row, col, to_row, to_col)
    drow = _delta(to_row - row)
    dcol = _delta(to_col - col)

    while row != to_row || col != to_col
      return false if row < 0 || row >= rows
      return false if col < 0 || col >= columns
      return false if self[row, col].nil?
      return false if self[row, col] == :goal
      row += drow
      col += dcol
    end

    row >= 0 && row < rows &&
      col >= 0 && col <= columns &&
      self[row, col]
  end

  def _delta(value)
    return 0 if value.zero?
    (value < 0) ? -1 : 1
  end
end

class Solution
  attr_reader :graph
  attr_reader :goal
  attr_reader :root

  def initialize(field, start_row, start_column)
    @graph = Graph.from_field(field)
    @root = @graph[start_row, start_column]

    _compute_solution
  end

  def path
    path = []
    node = @goal

    while node != root
      path.unshift node.previous_dir
      node = node.previous_node
    end

    path
  end

  def _compute_solution
    root.distance = 0
    frontier = [ root ]

    while frontier.any?
      new_frontier = []

      frontier.each do |node|
        %i(n s e w nw ne sw se).each do |dir|
          next unless node[dir]

          if node[dir].distance > node.distance+1
            node[dir].distance = node.distance + 1
            node[dir].previous_dir = dir
            node[dir].previous_node = node

            if node[dir].goal?
              if @goal.nil? || @goal.distance > node[dir].distance
                @goal = node[dir]
              end
            else
              new_frontier << node[dir]
            end
          end
        end
      end

      frontier = new_frontier
    end
  end
end

field = Field.from_file(ARGV.first || "grid.txt")
solution = Solution.new(field, field.rows/2, field.columns/2)

solution.path.each do |step|
  puts " - #{step}"
end