A program for solving Sam Lloyd's "Back from the Klondike" puzzle.
__________xxx__________ | |
_______xxx477xxx_______ | |
_____xx544833463xx_____ | |
____x1451114517135x____ | |
___x494967555876685x___ | |
__x37298356739187585x__ | |
__x14784292711822763x__ | |
_x7218553113133428613x_ | |
_x4267252422543281773x_ | |
_x4165111914344319827x_ | |
x435232232425351135537x | |
x271511315332423775427x | |
x252261244634121265188x | |
_x4375193445294195748x_ | |
_x4167834341312323624x_ | |
_x7326153923215758954x_ | |
__x16734811121228941x__ | |
__x25478756135787293x__ | |
___x656467252263474x___ | |
____x2312333213211x____ | |
_____xx744573447xx_____ | |
_______xxx334xxx_______ | |
__________xxx__________ |
# 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment