Onimusha puzzle script

class Board
    def initialize(tiles) @tiles = tiles end
    def solved?
        # ?a means the ASCII value of 'a' (97)
	@tiles[1][1] == ?a and @tiles[1][2] == ?b and
	@tiles[2][1] == ?c and @tiles[2][2] == ?d
    end
    # moves:   12
    #         8  3
    #         7  4
    #          65
    def move(n)
	if legal_move(n) then
	    case n
	    when 1: @tiles[3][1] = @tiles[2][1];@tiles[2][1] = @tiles[1][1]
		    @tiles[1][1] = @tiles[0][1];@tiles[0][1] = " "
	    when 2: @tiles[3][2] = @tiles[2][2];@tiles[2][2] = @tiles[1][2]
		    @tiles[1][2] = @tiles[0][2];@tiles[0][2] = " "

	    when 3: @tiles[1] = @tiles[1][1..3] + " "
	    when 4: @tiles[2] = @tiles[2][1..3] + " "

	    when 5: @tiles[0][2] = @tiles[1][2];@tiles[1][2] = @tiles[2][2]
		    @tiles[2][2] = @tiles[3][2];@tiles[3][2] = " "
	    when 6: @tiles[0][1] = @tiles[1][1];@tiles[1][1] = @tiles[2][1]
		    @tiles[2][1] = @tiles[3][1];@tiles[3][1] = " "

	    when 7: @tiles[2] = " " + @tiles[2][0..2]
	    when 8: @tiles[1] = " " + @tiles[1][0..2]
	    end
	else
	    puts "illegal move"
	end
    end
    # a move is legal if the tile on the opposite side is empty
    def legal_move(n)
        empty = ?\s # ASCII value of space (32)
	case n
	when 1: return @tiles[3][1] == empty
	when 2: return @tiles[3][2] == empty
	when 3: return @tiles[1][0] == empty
	when 4: return @tiles[2][0] == empty
	when 5: return @tiles[0][2] == empty
	when 6: return @tiles[0][1] == empty
	when 7: return @tiles[2][3] == empty
	when 8: return @tiles[1][3] == empty
	else return false
	end
    end
    def get_legal_moves
	legal_moves = []
	(1..8).each do |x| legal_moves += [x] if legal_move(x) end
	return legal_moves
    end
    # non-shallow copy
    def copy() return Marshal.load(Marshal.dump(self)) end
    def to_s()
	"          .- 12 -.\n" +
	"          | #{@tiles[0]} |\n" +
        "          8 #{@tiles[1]} 3\n" +
        "          7 #{@tiles[2]} 4\n" +
        "          | #{@tiles[3]} |\n" +
	"          '- 65 -'"
    end
end

class Brain
    attr_reader :moves_attempted
    def initialize(board) @original_board = board end
    def solve(limit)
        @moves_attempted = 0
        @solved = false
        recursive_descent(@original_board, [], limit)
        return @solved
    end
    # recursive brute force, tries 4^limit times before giving up
    def recursive_descent(board, moves_so_far, limit)
        return if moves_so_far.length >= limit or @solved
        board.get_legal_moves.each do |n|
            @moves_attempted+=1
            new_board = board.copy
            new_board.move(n)
            if new_board.solved? then
                @solved = true
                @solution = moves_so_far + [n]
                return
            else
                solution = recursive_descent(new_board, moves_so_far + [n], limit)
            end
        end
    end
    def print_solution
        puts "SOLVED in #{@solution.length} moves (#{@moves_attempted} moves attempted): "
        board = @original_board.copy
        @solution.each do |m|
            board.move(m)
            puts "move: #{m}"
            puts board
        end
        print "summary - moves: "
        @solution[0..-2].each do |m| print "#{m}, " end
        puts @solution[-1]
    end
end

board = Board.new( [ "  d " ,
		     "c.. " ,
		     " ..a" ,
		     " b  " ] )
puts board
brain = Brain.new(board)
# _extremely_ inefficient way of determining the smallest number of moves
(1..12).each do |moves|
    if brain.solve(moves) then
        brain.print_solution
        exit
    else
        puts "unsolvable in #{moves} moves (#{brain.moves_attempted} moves attempted)"
    end
end