#!/usr/bin/ruby

SZ = 8

# colors: r g b y piece star squel squelexp

def gravity(z)
	SZ.times { |x|
		SZ.times { |y|
			next if z[y][x]
			next if not ny = (y+1...SZ).find { |ny_| z[ny_][x] }
			z[ny][x], z[y][x] = z[y][x], z[ny][x]
		}
	}
end

def samecol(c1, c2)
	return if not c1 or not c2
	c1 == c2 or (c1 == 6 and c2 == 7) or (c1 == 7 and c2 == 6)
end

def expl(x, y)
	ret = []
	(-1..1).each { |dx|
		next if x+dx < 0 or x+dx >= SZ
		(-1..1).each { |dy|
			next if y+dy < 0 or y+dy >= SZ
			ret << [x+dx, y+dy]
		}
	}
	ret
end

def propagate_expl(z, ret)
	ret.each { |x, y|
		if z[y][x] == 7
			expl(x, y).each { |n|
				ret << n if not ret.include? n	# .each will walk that too
			}
		end
	}
	ret
end

# stuff to remove (lines + explosions)
def find_lines(z, x, y)
	ret = []
	r = 0 ; r += 1 while x-r >= 0 and samecol(z[y][x-r], z[y][x])
	l = 0 ; l += 1 while x+l < SZ and samecol(z[y][x+l], z[y][x])
	ret.concat((x-r+1..x+l-1).map { |nx| [nx, y] }) if l+r-1 >= 3
	r = 0 ; r += 1 while y-r >= 0 and samecol(z[y-r][x], z[y][x])
	l = 0 ; l += 1 while y+l < SZ and samecol(z[y+l][x], z[y][x])
	ret.concat((y-r+1..y+l-1).map { |ny| [x, ny] }) if l+r-1 >= 3
	propagate_expl(z, ret)
	ret
end

def try_move(z, x, y, d)
	# left right down up
	nx, ny = x, y
	case d
	when 0; nx -= 1
	when 1; nx += 1
	when 2; ny -= 1
	when 3; ny += 1
	end
	return if nx < 0 or ny < 0 or nx >= SZ or ny >= SZ
	return if (d == 0 or d == 2) and z[ny][nx]	# avoid dups
	nz = z.map { |l| l.dup }
	nz[ny][nx], nz[y][x] = nz[y][x], nz[ny][nx]
	crd = find_lines(nz, x, y) + find_lines(nz, nx, ny)
	return if crd.empty?
	while not crd.empty?
		crd.each { |cx, cy| nz[cy][cx] = nil }
		gravity(nz)
		nc = []
		crd.each { |cx, cy| nc.concat find_lines(nz, cx, cy) }
		crd = nc
	end
	nz
end

def bf(z)
	ret = []
	z.each_with_index { |l, y|
		l.each_with_index { |e, x|
			next if not e
			4.times { |d|
				if nz = try_move(z, x, y, d)
					ret << [x, y, d, nz]
				end
			}
		}
	}
	ret
end

def solve(z)
	bf(z).each { |x, y, d, nz|
		if nz.all? { |l| l.compact.empty? }
			return [[x, y, d, nz]]
		elsif out = solve(nz)
			return [[x, y, d, nz]] + out
		end
	}
	nil
end

def show(z)
	puts z.reverse.map { |l| l.map { |c| " #{c || ' '}" }.join }
end

z = <<EOS.lines.map { |l| l.chomp.split(//).map { |i| i.to_i if i != ' ' } }.reverse
   6
  36
  25
  36  6
  565 56
33130336
22127225
33631335
EOS

solve(z).each { |x, y, d, nz|
	d = { 0 => :left, 1 => :right, 2 => :down, 3 => :up }[d]
	puts "#{x}, #{y} -> #{d}"
	show(nz)
}