class Puzzle
 def initialize(x,y)
   @board = mkboard(x,y)
   @x, @y = x, y
 end

 def mkboard(x,y)
   board = Array.new(x*y) { |e| e+1 }
   board[-1] = nil
   board
 end

 def put(x,y,c)
   @board[y*@x+x] = c
 end
 
 def get(x,y)
   @board[y*@x+x]
 end

 # index -> coordinates
 def i2c(idx)
   [(idx % @x), (idx / @x)]
 end

 def dump
   (0..(@y-1)).to_a.each { |y| (0..(@x-1)).to_a.each { |x| $stdout.print get(x,y) ? "%4d" % get(x,y) : '    '  }; puts }
 end
 
 def solved? 
   @board == mkboard(@x,@y) && @moved 
 end

 def move(direction)
   x,y = i2c(@board.index(nil))
   fx, fy = x,y

   case direction
      when 'u'
       fy = y+1
     when 'd'
       fy = y-1
     when 'l'
       fx = x+1
     when 'r'
       fx = x-1
   end

   return if ((fx >= @x) || (fx < 0) || (fy >= @y) || (fy < 0))
   return if ((fx == x) && (fy == y))
 
   @moved = true
   
   put(x,y, get(fx,fy))
   put(fx,fy,nil)
 end
 
 def shuffle
   100.times { move 'udlr'[(rand*4).to_i].chr }
 end
end

p = Puzzle.new((ARGV[0] || 3).to_i,(ARGV[1] || 3).to_i)

while (!p.solved?) do
 p.dump
 print "Use (U)p, (D)own, (L)eft, (R)ight, (S)huffle, (Q)uit: "
 command = $stdin.gets[0].chr.downcase
 
 p.shuffle if command == 's'
 exit if command == 'q' 
 p.move command
end

puts
10.times { $stdout.print '*'; sleep 0.1; $stdout.flush } 
puts " You won!\n"