gistfile1.rb

class Array
	def invert
		[1,2,3,4,5,6,7,8,9].select do |i|
			! self.include?i
		end
	end
end

class Unsolvable < Exception
end

class Sudoku
	def initialize(str)
		@elim, @rows = [], []
		str.split(/\n/).each do |row|
			@rows << row.split(/[\s+,]/).collect {|i| i.to_i > 0 ? i.to_i : '.'}
		end
	end

	def row(i)
		@rows[i].dup
	end

	def col(i)
		col = []
		@rows.each do |row|
			col << row[i]
		end
		col
	end

	def square(x,y,ignore=false)
		x = 0 if x < 3
		x = 3 if x < 6 && x > 3
		x = 6 if x > 6
		y = 0 if y < 3
		y = 3 if y < 6 && y > 3
		y = 6 if y > 6
		square = []
		@rows[y..y+2].each do |row|
			row[x..x+2].each do |i|
				if ignore && x == x && y == y
					square << '.'
				else
					square << i
				end
			end
		end
		square
	end

	def number_unsolved
		count = 0
		@rows.each do |row|
			row.each do |i|
				count += 1 if i == '.'
			end
		end
		count
	end

	def solve_step!(guess=0)
		@rows.each_with_index do |row,y|
			row.each_with_index do |i,x|
				if i == '.'
					i = ( row.select{|a| a != '.'} + col(x).select{|a| a != '.'} + square(x,y).select{|a| a != '.'} ).invert
				else
					i = [i]
				end
				if i.length == 1
					guess = 0 if @rows[y][x] == '.'
					@rows[y][x] = i[0]
				elsif i.length < 1
					raise Unsolvable
				elsif i.length <= guess
					@rows[y][x] = i[rand(i.length)]
					return true
				end
			end
		end
		false
	end

	def is_consistent
		iz  = true
		@rows.each_with_index do |row,y|
			row.each_with_index do |i,x|
				r = row.dup
				r[x] = '.'
				c = col(x)
				c[y] = '.'
				s = square(x,y,true)
				possible = ( r.select{|a| a != '.'} + c.select{|a| a != '.'} + s.select{|a| a != '.'} ).invert
				iz = iz && possible.include?(i)
			end
		end
		iz
	end

	def to_s
		r = ''
		@rows.each do |row|
			row.each do |i|
				r << "#{i} "
			end
			r << "\n"
		end
		r
	end
end

string = $stdin.read

s = Sudoku.new(string)

steps = 0
guess = 0
last_unsolved = s.number_unsolved
while last_unsolved > 0
	puts s
	puts "\n---"
	begin
		if s.solve_step!(guess)
			guess = 0
		end
	rescue Unsolvable
		warn 'Unsolvable because of guess... trying again...'
		s = Sudoku.new(string)
		last_unsolved = s.number_unsolved
		guess = 0
		steps = 0
		next
	end
	if s.number_unsolved == last_unsolved
		warn 'Had to try guessing... may fail.'
		guess += 1
	end
	if guess > 9
		puts "\nSEEMS UNSOLVABLE\n"
		break
	end
	last_unsolved = s.number_unsolved
	steps += 1
end

puts s

puts
puts "The solution #{s.is_consistent ? 'is' : 'is not'} consistent."

puts
puts "After #{steps} steps..."