Skip to content

Instantly share code, notes, and snippets.

@obelisk68

obelisk68/sokoban_solver.rb

Last active January 24, 2021 14:29
Show Gist options
  • Save obelisk68/5d71f84dcd5cafe8688321f9497a247b to your computer and use it in GitHub Desktop.
Save obelisk68/5d71f84dcd5cafe8688321f9497a247b to your computer and use it in GitHub Desktop.
Download ZIP
倉庫番ソルバー（Brute Force）
Raw
sokoban_solver.rb
module Sokoban
Pos = Struct.new(:x, :y) do
def dirs
[Pos.new(x + 1, y), Pos.new(x, y - 1),
Pos.new(x - 1, y), Pos.new(x, y + 1)]
end
def inspect = "<#{x},#{y}>"
def over_there(e) = Pos.new(2 * e.x - x, 2 * e.y - y)
def <=>(a) = [x, y] <=> [a.x, a.y]
end
module Disp
def self.show(raw)
puts raw
sleep(1)
end
end
class Field
class Node
def initialize(pos, parent=nil)
@pos = pos
@parent = parent
end
attr_reader :pos, :parent
def x = @pos.x
def y = @pos.y
def dirs = @pos.dirs.map { Node.new(_1, self) }
end #----Node
def initialize(data)
@raw = data
width = data[0].length
d = data.join
i = d.index("@")
xy = ->(idx) { Pos.new(idx % width, idx / width) }
@man = xy.(i)
@raw[@man.y][@man.x] = " "
@goals =
d.each_char.with_index.filter_map { |c, i| c == "." ? xy.(i) : nil }
@boxes =
d.each_char.with_index.filter_map { |c, i| c == "=" ? xy.(i) : nil }
@goals.sort!
@boxes.sort!
@raw.map! { _1.tr(".", " ") }
end
attr_reader :boxes, :man, :raw
attr_writer :goals
def reachable?(from, to, flag = true)
return [from] if from == to
f = @raw.map(&:dup)
queue = [Node.new(from)]
try = ->{
while (now = queue.shift)
now.dirs.each do |nxt|
next unless f[nxt.y][nxt.x] == " " || f[nxt.y][nxt.x] == "."
if to == nxt.pos
if flag
path = []
a = nxt
while a
path.unshift(a.pos)
a = a.parent
end
return path
else
return true
end
else
queue << nxt
f[nxt.y][nxt.x] = "$"
end
end
end
false
}
try.()
end
def walk
@boxes.each do |b|
b.dirs.select { |b1| @raw[b1.y][b1.x] == " " }.each do |man|
ov = man.over_there(b)
next unless @raw[ov.y][ov.x] == " "
next unless (path = reachable?(@man, man))
yield(man, b, path)
end
end
end
def push(man, box)
raw = @raw.map(&:dup)
raw[box.y][box.x] = "@"
raw[man.y][man.x] = " "
boxes = @boxes.reject { _1 == box } + [man.over_there(box)]
boxes.sort!
boxes.each { |b| raw[b.y][b.x] = "=" }
f = Field.new(raw)
f.goals = @goals
f
end
def to_s
raw = @raw.map(&:dup)
@goals.each { |g| raw[g.y][g.x] = "." }
@boxes.each { |b| raw[b.y][b.x] = "=" }
raw[@man.y][@man.x] = "@"
raw
end
def show(path)
raw = to_s
a = path[0]
raw[a.y][a.x] = " "
path[1..-1].each do |b|
raw[b.y][b.x] = "@"
Disp.show(raw)
raw[b.y][b.x] = " "
end
end
def goal? = @goals == @boxes
end #----Field
class History
@@all_history = {}
def initialize(*arg)
case arg
in [Field => field]
@@all_history[field.boxes] = field.man
@progress = [[field, []]]
in [history, field, path]
@progress = history.progress + [[field, path]]
end
end
attr_reader :progress
def add(next_field, path)
man = next_field.man
boxes = next_field.boxes
found = @@all_history[boxes]
if found
case found
in Array => men
f = men.any? { |man0| next_field.reachable?(man0, man, false) }
return nil if f
@@all_history[boxes] << man
in Pos => man0
g = next_field.reachable?(man0, man, false)
return nil if g
@@all_history[boxes] = [man0, man]
end
else
@@all_history[boxes] = man
end
History.new(self, next_field, path)
end
def finish
e = @progress.to_enum
field, _ = e.next
Disp.show(field.to_s)
loop do
f, path = e.next
field.show(path)
field = f
Disp.show(field.to_s)
end
end
end #----History
module_function
def solve(data)
field = Field.new(data)
try(field, History.new(field))
end
def try(field, history)
if field.goal?
history.finish
true
else
field.walk do |man, box, path|
next_field = field.push(man, box)
new_history = history.add(next_field, path)
next unless new_history
f = try(next_field, new_history)
return f if f
end
false
end
end
end
Sokoban.solve(DATA.readlines(chomp: true))
__END__
#######
# ###
# = ##
# =@= #
# == #
#.....#
#######
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment