class Sudoku
	def initialize(a)
		@possible = Array.new(9*9) { [*1..9] }
		@a = [0]*9*9
		a.each_with_index { |v, i| self[i%9, i/9] = v || 0 }
	end

	def [](x, y)
		@a[9*y+x]
	end
	def poss(x, y)
		@possible[9*y+x]
	end

	def []=(x, y, v)
		9.times { |px| @possible[9*y + px].delete v }
		9.times { |py| @possible[9*py + x].delete v }
		3.times { |dpx| dpx += x - x%3
			3.times { |dpy| dpy += y - y%3
				@possible[9*dpy+dpx].delete v
			}
		}
		@a[9*y+x] = v
	end

	def inspect
		wider = @possible.map { |p| p.length }.max
		s = "\n"
		@a.each_with_index { |v, i|
			if v.zero?
				s << @possible[i].join.center(wider)
			else
				s << v.to_s.center(wider)
			end
			i += 1
			s <<
			if i % 27 == 0: "\n\n"
			elsif i % 9 == 0: "\n"
			elsif i % 3 == 0: '  '
			else ' '
			end
		}
		s.chop
	end

	def solve_one
		found = proc { |x, y, v, reason|
			puts "found #{v} at (#{x+1}, #{9-y}) (#{reason})"
			self[x, y] = v
			self
		}
		9.times { |y|
			count = Hash.new(0)
			9.times { |x|
				next if self[x, y] != 0
				p = poss(x, y)
				return found[x, y, p.first, 'only'] if p.length == 1
				p.each { |v| count[v] += 1 }
			}
			if fnd = count.find { |v, c| c == 1 }
				v = fnd.first
				9.times { |x|
					return found[x, y, v, 'line'] if self[x, y] == 0 and poss(x, y).include? v
				}
			end
		}
		9.times { |x|
			count = Hash.new(0)
			9.times { |y|
				next if self[x, y] != 0
				poss(x, y).each { |v| count[v] += 1 }
			}
			if fnd = count.find { |v, c| c == 1 }
				v = fnd.first
				9.times { |y|
					return found[x, y, v, 'col'] if self[x, y] == 0 and poss(x, y).include? v
				}
			end
		}
		3.times { |dx|  3.times { |dy|
			count = Hash.new(0)
			3.times { |x| x += 3*dx ; 3.times { |y| y += 3*dy
				next if self[x, y] != 0
				poss(x, y).each { |v| count[v] += 1 }
			} }
			if fnd = count.find { |v, c| c == 1 }
				v = fnd.first
				3.times { |x| x += 3*dx ; 3.times { |y| y += 3*dy
					return found[x, y, v, 'square'] if self[x, y] == 0 and poss(x, y).include? v
				} }
			end
		} }
		nil
	end

	def solve
		nil while solve_one
		self
	end
end


if __FILE__ == $0
	p Sudoku.new(ARGV.join.split(//).map { |c| c.to_i }).solve
end