Here's my solution.  The controls are as follows:

i - move up
j - move left
k - move right
m - move down

Q - quit
R - restart level

S - save game (you can only save one game at a time)
L - load last saved game

U - undo

I built a Sokoban module and two interfaces for it.  One interface is 
for Unix terminals and the other is for those who have Ruby's OpenGL 
interface installed.

# === file:  sokoban.rb ===

#!/usr/bin/env ruby

require "yaml"

class Sokoban
	WALL				= "#"
	OPEN_FLOOR			= " "

	MAN					= "@"
	CRATE				= "o"

	STORAGE				= "."
	MAN_ON_STORAGE		= "+"
	CRATE_ON_STORAGE	= "*"

	MAX_UNDO			= 10
	
	PATH				= File.expand_path(File.dirname(__FILE__))
	
	attr_reader :level, :moves
	
	def self.load( file = File.join(PATH, "sokoban_saved_game.yaml") )
		game = nil

		File.open file do |f|
			game = YAML.load(f)
		end

		game ||= Sokoban.new
		game
	end
	
	def initialize( file = File.join(PATH, "sokoban_levels.txt") )
		@level_file = file

		@board = [ ]
		@level = 0
		@over = false
		
		@undos = [ ]
		@moves = 0
		
		load_level
	end
	
	def can_move_down?( )	can_move? :down		end
	def can_move_left?( )	can_move? :left		end
	def can_move_right?( )	can_move? :right	end
	def can_move_up?( )		can_move? :up		end
	
	def display
		@board.inject("") { |dis, row| dis + row.join + "\n" }
	end
	
	def level_solved?
		@board.each_with_index do |row, y|
			row.each_with_index do |cell, x|
				return false if cell == CRATE
			end
		end
		true
	end
	
	def load_level( level = @level += 1, file = @level_file )
		loaded = false

		File.open file do |f|
			count = 0
			while lvl = f.gets("")
				count += 1
				if count == level
					@board = [ ]
					lvl.chomp!
					lvl.each_line { |e| @board << e.chomp.split("") }
					loaded =  true
					break
				end
			end
		end

		if loaded
			@undos = [ ]
			@moves = 0
		else
			@over = true
		end

		loaded
	end
	
	def move_down( )	move :down		end
	def move_left( )	move :left		end
	def move_right( )	move :right	end
	def move_up( )		move :up		end
	
	def over?
		@over
	end
	
	def restart_level
		load_level @level
	end
	
	def save( file = File.join(PATH, "sokoban_saved_game.yaml") )
		File.open(file, "w") do |f|
			f << YAML.dump(self)
		end
	end
	
	def undo
		if @undos.size > 0
			@board = @undos.pop
			@moves -= 1
		end
	end
	
	private
	
	def can_move?( dir )
		x, y = where_am_i
		case dir
		when :down
			first = @board[y + 1][x]
			second = y < @board.size - 2 ? @board[y + 2][x] : nil
		when :left
			first = @board[y][x - 1]
			second = x >= 2 ? @board[y][x - 2] : nil
		when :right
			first = @board[y][x + 1]
			second = x < @board[y].size - 2 ? @board[y][x + 2] : nil
		when :up
			first = @board[y - 1][x]
			second = y >= 2 ? @board[y - 2][x] : nil
		end

		if first == OPEN_FLOOR or first == STORAGE
			true
		elsif not second.nil? and
			  (first == CRATE or first == CRATE_ON_STORAGE) and
			  (second == OPEN_FLOOR or second == STORAGE)
			true
		else
			false
		end
	end
	
	def move( dir )
		return false unless can_move? dir
		
		@undos << Marshal.load(Marshal.dump(@board))
		@undos.shift if @undos.size > MAX_UNDO
		@moves += 1
		
		x, y = where_am_i
		case dir
		when :down
			if @board[y + 1][x] == CRATE or @board[y + 1][x] == CRATE_ON_STORAGE
				move_crate x, y + 1, x, y + 2
			end
			move_man x, y, x, y + 1
		when :left
			if @board[y][x - 1] == CRATE or @board[y][x - 1] == CRATE_ON_STORAGE
				move_crate x - 1, y, x - 2, y
			end
			move_man x, y, x - 1, y
		when :right
			if @board[y][x + 1] == CRATE or @board[y][x + 1] == CRATE_ON_STORAGE
				move_crate x + 1, y, x + 2, y
			end
			move_man x, y, x + 1, y
		when :up
			if @board[y - 1][x] == CRATE or @board[y - 1][x] == CRATE_ON_STORAGE
				move_crate x, y - 1, x, y - 2
			end
			move_man x, y, x, y - 1
		end
		true
	end
	
	def move_crate( from_x, from_y, to_x, to_y )
		if @board[to_y][to_x] == STORAGE
			@board[to_y][to_x] = CRATE_ON_STORAGE
		else
			@board[to_y][to_x] = CRATE
		end
		if @board[from_y][from_x] == CRATE_ON_STORAGE
			@board[from_y][from_x] = STORAGE
		else
			@board[from_y][from_x] = OPEN_FLOOR
		end
	end
	
	def move_man( from_x, from_y, to_x, to_y )
		if @board[to_y][to_x] == STORAGE
			@board[to_y][to_x] = MAN_ON_STORAGE
		else
			@board[to_y][to_x] = MAN
		end
		if @board[from_y][from_x] == MAN_ON_STORAGE
			@board[from_y][from_x] = STORAGE
		else
			@board[from_y][from_x] = OPEN_FLOOR
		end
	end
	
	def where_am_i
		@board.each_with_index do |row, y|
			row.each_with_index do |cell, x|
				return x, y if cell == MAN or cell == MAN_ON_STORAGE
			end
		end
	end
end

__END__

# === file:  unix_term_sokoban.rb ===

#!/usr/bin/env ruby

require "sokoban"

def draw( g )
	screen = "Level #{g.level} - #{g.moves} moves\n\n" + g.display
	screen.gsub("\n", "\r\n")
end

system "stty raw -echo"

game = Sokoban.new

loop do
	system "clear"
	puts draw(game)
	
	if game.level_solved?
		puts "\r\nLevel solved.  Nice Work!\r\n"
		sleep 3
		game.load_level

		break if game.over?
	end
	
	case STDIN.getc
		when ?Q, ?\C-c
			break
		when ?S
			game.save
		when ?L
			game = Sokoban.load if test ?e, "sokoban_saved_game.yaml"
		when ?R
			game.restart_level
		when ?U
			game.undo
		when ?j, ?j
			game.move_left
		when ?k, ?K
			game.move_right
		when ?m, ?m
			game.move_down
		when ?i, ?I
			game.move_up
	end
end

if game.over?
	system "clear"
	puts "\r\nYou've solved all the levels Puzzle Master!!!\r\n\r\n"
end

END { system "stty -raw echo" }

__END__

# === file:  opengl_sokoban.rb ===

#!/usr/bin/env ruby

require "opengl"
require "glut"

require "sokoban"

PATH = File.expand_path(File.dirname(__FILE__))

def init
	GL.Light GL::LIGHT0, GL::AMBIENT, [0.0, 0.0, 0.0, 1.0]
	GL.Light GL::LIGHT0, GL::DIFFUSE, [1.0, 1.0, 1.0, 1.0]
	GL.Light GL::LIGHT0, GL::POSITION, [0.0, 3.0, 3.0, 0.0]
	GL.LightModel GL::LIGHT_MODEL_AMBIENT, [0.2, 0.2, 0.2, 1.0]
	GL.LightModel GL::LIGHT_MODEL_LOCAL_VIEWER, [0.0]
	
	GL.FrontFace GL::CW
	GL.Enable GL::LIGHTING
	GL.Enable GL::LIGHT0
	GL.Enable GL::AUTO_NORMAL
	GL.Enable GL::NORMALIZE
	GL.Enable GL::DEPTH_TEST
	GL.DepthFunc GL::LESS
end

def render_man
	GL.Material GL::FRONT, GL::AMBIENT, [0.0, 0.0, 0.0, 1.0]
	GL.Material GL::FRONT, GL::DIFFUSE, [0.5, 0.0, 0.0, 1.0]
	GL.Material GL::FRONT, GL::SPECULAR, [0.7, 0.6, 0.6, 1.0]
	GL.Material GL::FRONT, GL::SHININESS, 0.25 * 128.0
	
	GLUT.SolidSphere 0.5, 16, 16
end

def render_crate
	GL.Material GL::FRONT, GL::AMBIENT, [0.19125, 0.0735, 0.0225, 1.0]
	GL.Material GL::FRONT, GL::DIFFUSE, [0.7038, 0.27048, 0.0828, 1.0]
	GL.Material GL::FRONT, GL::SPECULAR, [0.256777, 0.137622, 0.086014, 
1.0]
	GL.Material GL::FRONT, GL::SHININESS, 0.1 * 128.0
	
	GL.PushMatrix
		GL.Scale 0.9, 0.9, 0.9
		GL.Translate 0.0, 0.0, 0.45
		
		GLUT.SolidCube 1.0
	GL.PopMatrix
end

def render_stored_crate
	GL.Material GL::FRONT, GL::AMBIENT, [0.25, 0.20725, 0.20725, 1.0]
	GL.Material GL::FRONT, GL::DIFFUSE, [1.0, 0.829, 0.829, 1.0]
	GL.Material GL::FRONT, GL::SPECULAR, [0.296648, 0.296648, 0.296648, 
1.0]
	GL.Material GL::FRONT, GL::SHININESS, 0.088 * 128.0
	
	GL.PushMatrix
		GL.Scale 0.9, 0.9, 0.9
		GL.Translate 0.0, 0.0, 0.45
		
		GLUT.SolidCube 1.0
	GL.PopMatrix
end

def render_open_floor
	GL.Material GL::FRONT, GL::AMBIENT, [0.05, 0.05, 0.05, 1.0]
	GL.Material GL::FRONT, GL::DIFFUSE, [0.5, 0.5, 0.5, 1.0]
	GL.Material GL::FRONT, GL::SPECULAR, [0.7, 0.7, 0.7, 1.0]
	GL.Material GL::FRONT, GL::SHININESS, 0.078125 * 128.0
	
	GL.PushMatrix
		GL.Scale 0.9, 0.9, 0.1
		GL.Translate 0.0, 0.0, -0.05
		
		GLUT.SolidCube 1.0
	GL.PopMatrix

	GL.Material GL::FRONT, GL::AMBIENT, [0.05375, 0.05, 0.06625, 1.0]
	GL.Material GL::FRONT, GL::DIFFUSE, [0.18275, 0.17, 0.22525, 1.0]
	GL.Material GL::FRONT, GL::SPECULAR, [0.332741, 0.328634, 0.346435, 
1.0]
	GL.Material GL::FRONT, GL::SHININESS, 0.3 * 128.0

	GL.PushMatrix
		GL.Scale 1.0, 1.0, 0.1
		GL.Translate 0.0, 0.0, -0.1
		
		GLUT.SolidCube 1.0
	GL.PopMatrix
end

def render_storage
	GL.Material GL::FRONT, GL::AMBIENT, [0.05, 0.05, 0.0, 1.0]
	GL.Material GL::FRONT, GL::DIFFUSE, [0.5, 0.5, 0.4, 1.0]
	GL.Material GL::FRONT, GL::SPECULAR, [0.7, 0.7, 0.04, 1.0]
	GL.Material GL::FRONT, GL::SHININESS, 0.078125 * 128.0
	
	GL.PushMatrix
		GL.Scale 0.9, 0.9, 0.1
		GL.Translate 0.0, 0.0, -0.05
		
		GLUT.SolidCube 1.0
	GL.PopMatrix

	GL.Material GL::FRONT, GL::AMBIENT, [0.05375, 0.05, 0.06625, 1.0]
	GL.Material GL::FRONT, GL::DIFFUSE, [0.18275, 0.17, 0.22525, 1.0]
	GL.Material GL::FRONT, GL::SPECULAR, [0.332741, 0.328634, 0.346435, 
1.0]
	GL.Material GL::FRONT, GL::SHININESS, 0.3 * 128.0

	GL.PushMatrix
		GL.Scale 1.0, 1.0, 0.1
		GL.Translate 0.0, 0.0, -0.1
		
		GLUT.SolidCube 1.0
	GL.PopMatrix
end

def solid_cylinder(radius, height, slices, stacks)
	GL.PushAttrib GL::POLYGON_BIT
		GL.PolygonMode GL::FRONT_AND_BACK, GL::FILL
		obj = GLU.NewQuadric
		GLU.Cylinder obj, radius, radius, height, slices, stacks
		GL.PushMatrix
			GL.Translate 0.0, 0.0, height
			GLU.Disk obj, 0.0, radius, slices, stacks
		GL.PopMatrix
		GLU.DeleteQuadric obj
	GL.PopAttrib
end

def render_wall
	GL.Material GL::FRONT, GL::AMBIENT, [0.0, 0.0, 0.0, 1.0]
	GL.Material GL::FRONT, GL::DIFFUSE, [0.1, 0.35, 0.1, 1.0]
	GL.Material GL::FRONT, GL::SPECULAR, [0.45, 0.55, 0.45, 1.0]
	GL.Material GL::FRONT, GL::SHININESS, 0.25 * 128.0
	
	GL.PushMatrix
		GL.Translate 0.0, 0.0, 0.5
		
		solid_cylinder 0.45, 1.0, 16, 4
	GL.PopMatrix
end

game = Sokoban.new

display = lambda do
	GL.Clear GL::COLOR_BUFFER_BIT | GL::DEPTH_BUFFER_BIT

	screen = game.display
	screen.each_with_index do |row, y|
		row.chomp!
		first = row =~ /^(\s+)/ ? $1.length : 0
		(first...row.length).each do |x|
			GL.PushMatrix
				GL.Translate 1.0 + x, 17.5 - y, 0.0
				
				if row[x, 1] == "." or row[x, 1] == "*" or row[x, 1] == "+"
					render_storage
				else
					render_open_floor
				end
				if row[x, 1] == "@" or row[x, 1] == "+"
					render_man
				elsif row[x, 1] == "o"
					render_crate
				elsif row[x, 1] == "*"
					render_stored_crate
				elsif row[x, 1] == "#"
					render_wall
				end
			GL.PopMatrix
		end
	end

	GL.Flush
end

reshape = lambda do |w, h|
	GL.Viewport 0, 0, w, h
	GL.MatrixMode GL::PROJECTION
	GL.LoadIdentity
	GL.Frustum(-1.0, 1.0, -1.0, 1.0, 1.5, 20.0)
	GL.MatrixMode GL::MODELVIEW
	GLU.LookAt 10.0, 10.0, 17.5, 10.0, 10.0, 0.0, 0.0, 1.0, 0.0
end

keyboard = lambda do |key, x, y|
	case key
		when ?Q, ?\C-c
			exit 0
		when ?S
			game.save
		when ?L
			if test ?e, File.join(PATH, "sokoban_saved_game.yaml")
				game = Sokoban.load
			end
		when ?R
			game.restart_level
		when ?U
			game.undo
		when ?j, ?j
			game.move_left
		when ?k, ?K
			game.move_right
		when ?m, ?m
			game.move_down
		when ?i, ?I
			game.move_up
	end

	if game.level_solved?
		game.load_level

		exit 0 if game.over?
	end
	
	GLUT.PostRedisplay
end

GLUT.Init
GLUT.InitDisplayMode GLUT::SINGLE | GLUT::RGB | GLUT::DEPTH
GLUT.CreateWindow "Sokoban"

init

GLUT.KeyboardFunc keyboard
GLUT.ReshapeFunc reshape
GLUT.DisplayFunc display

GLUT.MainLoop

__END__

James Edward Gray II