#!/usr/bin/ruby

class Grille
	# constructeur
	def initialize()
		@cases = Array.new(9)
		for i in 0...@cases.length
			@cases[i] = Array.new(9)
			for j in 0...@cases[i].length
				@cases[i][j] = [1,2,3,4,5,6,7,8,9]
			end
		end
	end
	
	def Grille.new_from_stdin()
		g = Grille.new
		num = 0
		while ligne = gets
			if (ligne =~ /\|\s*([\d\.])\s*([\d\.])\s*([\d\.])\s*\|\s*([\d\.])\s*([\d\.])\s*([\d\.])\s*\|\s*([\d\.])\s*([\d\.])\s*([\d\.])\s*\|/)
				g.def_ligne(num, [$1, $2, $3, $4, $5, $6, $7, $8, $9])
				num+=1
			end
		end
		return g
	end
	
	# transformation en chaine
	def to_s()
		sep = "+-------+-------+-------+\n"
		res = sep.dup
		for i in 0...@cases.length
			for j in 0...@cases[i].length
				if j % 3 == 0
					res += "| "
				end
				if @cases[i][j].kind_of?(Integer)
					symb = "*** " + @cases[i][j].to_s + " ***"
				else
					symb = ""
					@cases[i][j].each { |x| symb += x.to_s }
					(9-symb.length).times { symb += "." }
				end
				res += symb + " "
			end
			res += "|\n"
			if i % 3 == 2
				res += sep
			end
		end
		return res + "[[" + empreinte.to_s + "]]\n"
	end
	
	def []=(i, j, val)
		@cases[i][j] = val
	end
	
	def [](i,j)
		return @cases[i][j]
	end
	
	def def_ligne(i, vals)
		for j in 0...@cases[i].length
			v = vals[j].to_i
			if v != 0
				@cases[i][j] = v
			end
		end
	end
	
	def clone
		g = Grille.new
		for i in 0...@cases.length
			for j in 0...@cases[i].length
				if @cases[i][j].kind_of?(Array)
					g[i,j] = @cases[i][j].clone
				else
					g[i,j] = @cases[i][j]
				end
			end
		end
		return g
	end
	
	def simplifie_ligne(i)
		ligne = @cases[i]
		for j in 0...ligne.length
			la_case = ligne[j]
			if la_case.kind_of?(Integer)
				for k in 0...ligne.length
					elt = ligne[k]
					if elt.kind_of?(Array)
						elt.delete_if { |x| x == la_case }
						# suppression de la liste si longueur = 1
						if elt.length == 1
							ligne[k] = elt[0]
						end
					end
				end
			end
		end
	end
	
	def simplifie_colonne(j)
		for i in 0...@cases.length
			la_case = @cases[i][j]
			if la_case.kind_of?(Integer)
				for k in 0...@cases.length
					elt = @cases[k][j]
					if elt.kind_of?(Array)
						elt.delete_if { |x| x == la_case }
						# suppression de la liste si longueur = 1
						if elt.length == 1
							@cases[k][j] = elt[0]
						end
					end
				end
			end
		end
	end
	
	def simplifie_carre(i,j)
		# 1- relève tous les entiers
		to_del = Array.new
		for u in 0...3
			for v in 0...3
				elt = @cases[i*3+u][j*3+v]
				if elt.kind_of?(Integer)
					to_del << elt
				end
			end
		end
		
		# 2- les supprime des listes
		for u in 0...3
			for v in 0...3
				elt = @cases[i*3+u][j*3+v]
				if elt.kind_of?(Array)
					elt.delete_if { |x| to_del.index(x) }
					if elt.length == 1
						@cases[i*3+u][j*3+v] = elt[0]
					end
				end
			end
		end
	end
	
	def unique_colonne(j)
		# 1- compte le nombre de fois que chaque terme indéterminé apparaît
		indet = Hash.new(0)
		for i in 0...@cases.length
			elt = @cases[i][j]
			if elt.kind_of?(Array)
				elt.each { |x| indet[x] += 1 }
			else
				indet[elt] += 1
			end
		end
		
		# 2- élimine les termes qui n'apparaissent qu'une seule fois
		indet.each { |nombre, fois|
			if fois == 1
				for i in 0...@cases.length
					elt = @cases[i][j]
					if elt.kind_of?(Array)
						if elt.index(nombre)
							@cases[i][j] = nombre
						end
					end
				end
			end
		}
	end
	
	def iter_ligne(i)
		for j in 0...@cases[i].length
			res = yield @cases[i][j]
			if res != nil
				@cases[i][j] = res
			end
		end
	end
	
	def iter_ligne_indet(i)
		iter_ligne(i) { |elt|
			if elt.kind_of?(Array)
				yield elt
			else
				nil
			end
		}
	end
	
	def unique_ligne(i)
		# 1- compte le nombre de fois que chaque terme indéterminé apparaît
		indet = Hash.new(0)
		iter_ligne(i) { |elt|
			if elt.kind_of?(Array)
				elt.each { |x| indet[x] += 1 } 
			else
				indet[elt] += 1
			end
			nil
		}
		
	
		# 2- élimine les termes qui n'apparaissent qu'une seule fois
		indet.each { |nombre, fois|
			#print nombre, " => ", fois, "\n"
			if fois == 1
				iter_ligne_indet(i) { |liste|
					if liste.index(nombre)
						nombre
					else
						nil
					end
				}
			end
		}
	end
	
	def empreinte
		res = 0
		@cases.each { |ligne|
			ligne.each { |elt|
				#res *= 10
				if elt.kind_of?(Array)
					res += elt.length
				else
					res += 1
				end
			}
		}
		return res
	end
	
	def simplifie_max
		empr = 0
		passe = 0
		while empr != empreinte
			empr = empreinte
			
			##print "Simplification [", passe, "] A\n", to_s
			
			# par lignes
			for i in 0...9
				simplifie_ligne(i)
				unique_ligne(i)
			end
			
			##print "Simplification [", passe, "] B\n", to_s
			
			# par colonnes
			for i in 0...9
				simplifie_colonne(i)
				unique_colonne(i)
			end
			
			##print "Simplification [", passe, "] C\n", to_s
			
			# par carres
			for i in 0...3
				for j in 0...3
					simplifie_carre(i,j)
				end
			end
			
			passe += 1
		end
	end
	
	# renvoie un triplet indet_y, indet_x, indet_vals
	def trouve_indet
		for i in 0...@cases.length
			for j in 0...@cases[i].length
				if @cases[i][j].kind_of?(Array)
					return [i, j, @cases[i][j]]
				end
			end
		end
		return nil
	end
	
	# renvoie: 1 => ok, 0 => pas encore, -1 => absurde
	def resolue?
		#print "Test resolue?\n"
	
		e = empreinte
		if e>81 or e<81
			return 0
		end
		
		#print "empreinte ok\n"
		#print to_s
		
		# empreinte == 81
		for i in 0...9
			liste_l = (1..9).to_a
			liste_c = (1..9).to_a
			liste_b = (1..9).to_a
			for j in 0...9
				liste_l.delete_if { |x| x == @cases[i][j] }
				liste_c.delete_if { |x| x == @cases[j][i] }
				liste_b.delete_if { |x| x == @cases[(i/3)*3+(j/3)][(i%3)*3+(j%3)] }
			end
			
			if liste_l.length>0 or liste_c.length>0 or liste_b.length>0
				#print "pbm: i=", i, " j=", j, "\n"
				return -1
			end
		end
		
		return 1
				
	end
	
	def resolution
		simplifie_max
		#print "Version simplifiee au max:\n", to_s
		case resolue?
			when 1
				print "Solution:\n", to_s, "\n"
				return true
			
			when -1
				return false
				
			when 0
				temp = trouve_indet
				
				if temp == nil
					print "PROBLEM:\n", to_s, "\n"
					return false
				end
				
				i = temp[0]
				j = temp[1]
				possibilites = temp[2]
				
				uneOK = false
				possibilites.each { |poss|
					#print "** rec: (#{i},#{j}) = #{poss}\n"
					g = clone
					g[i,j] = poss
					#print "** Grille utilisée lors de la récursion:\n", g
					if g.resolution
						uneOK = true
					end
				}
				
				return uneOK
		end
	end
end


def showRE(a,re)
	a = a.chomp
  if a =~ re
    print "#{a}: #{$`}<<#{$&}>>#{$'}\n"
  else
    print "#{a}: no match\n"
  end
end

g = Grille.new_from_stdin

print g

print "Simplification:\n"

g.resolution

#g.iter_ligne_indet(4) { |x| x << 0 }

#print g

#print g

#for i in 0...9
#	g.unique_ligne(i)
#	print "unique_ligne(#{i}):\n", g
#end