number_place.rb

#!/usr/bin/ruby

class NumberPlace
	def initialize(ary=nil)
		init(ary)
	end

	def init(ary=nil)
		@cells = Array.new(81) do
			[1, 2, 3, 4, 5, 6, 7, 8, 9]
		end
		@target_cells = Array.new(81) do |index|
			[
				target_cells_x(index),
				target_cells_y(index),
				target_cells_grid(index)
			]
		end
		@rule_cells = rule_cells
		if ary.kind_of?(Array) && ary.size == 81
			ary.each_index do |index|
				if ary[index] >= 1 && ary[index] <= 9
					@cells[index] = [ary[index]]
				end
			end
		end
	end
	def target_cells_x(index)
		x = index % 9
		y = index / 9

		((0 ... y).to_a + ((y+1) ... 9).to_a).map! do |j|
			9 * j + x
		end
	end
	def target_cells_y(index)
		x = index % 9
		y = index / 9

		((0 ... x).to_a + ((x+1) ... 9).to_a).map! do |j|
			9 * y + j
		end
	end
	def target_cells_grid(index)
		x = index % 9
		y = index / 9
		xj = x / 3
		yk = y / 3

		cells = []
		3.times do |k|
			3.times do |j|
				i = 9 * (3 * yk + k) + (3 * xj + j)
				if i != index
					cells << i
				end
			end
		end
		cells
	end
	def rule_cells
		rules = []
		9.times do |j|
			rules << ([9 * 0 + j] + target_cells_x(9 * 0 + j))
		end
		9.times do |j|
			rules << ([9 * j + 0] + target_cells_y(9 * j + 0))
		end
		3.times do |k|
			3.times do |j|
				i = 9 * (3 * k) + (3 * j)
				rules << ([i] + target_cells_grid(i))
			end
		end
		rules
	end


	def solve
		loop do
			solving = solve_step
			break unless solving
		end
	end

	def solve_step
		solving = false

		# @cells[0 ... 81] は各セルごとの可能性を管理
		# たとえば @cells[0] == [1, 4, 9] であれば 1, 4, 9 の
		# いずれかの可能性があることを意味する
		# （インデックスは 0 オリジン、数値は 1 オリジン）

		# @cells[index] = [v] のように数値が確定している場合、
		# 縦、横、グリッドの関連セルに対し、 v の可能性を消去する
		@cells.each_index do |index|
			# 数値が確定していない場合はスキップ
			if @cells[index].size > 1
				next
			end

			# 数値が確定している場合、関連セルに対し、
			# 数値 @cells[index][0] を消去する
			@target_cells[index].each do |tc|
				tc.each do |i|
					v = @cells[i].delete(@cells[index][0])
					solving = true unless v.nil?
				end
			end
		end

		# 次に、各セルの数値の可能性が複数ある場合でも、
		# 数値ごとに確認した場合、特定のセルしか可能性がない
		# ケースが存在する。その場合、数値を確定させる
		@rule_cells.each do |rule|
			numbers = [nil, [], [], [], [], [], [], [], [], []]
			rule.each do |i|
				@cells[i].each do |v|
					numbers[v] << i
				end
			end
			(1 .. 9).each do |v|
				if numbers[v].size == 1 && @cells[numbers[v][0]].size > 1
					@cells[numbers[v][0]] = [v]
					solving = true
				end
			end
		end

		solving
	end

	def inspect
		lines = []
		9.times do |j|
			lines << @cells[9 * j, 9].map! do |v|
				v.size > 1 ? '*' : v[0]
			end.join(' ')
		end
		lines.join("\n")
	end

	def cells
		@cells
	end
end



number_place = NumberPlace.new([
	# 初期値の設定。 0 は不明を意味する
	1, 0, 3,   0, 0, 6,   0, 9, 0,
	0, 9, 0,   3, 0, 0,   7, 0, 4,
	0, 0, 5,   0, 0, 0,   0, 2, 0,

	0, 0, 0,   4, 0, 0,   0, 0, 8,
	0, 0, 0,   0, 1, 0,   0, 3, 0,
	4, 0, 0,   8, 0, 2,   0, 0, 6,

	0, 5, 0,   0, 9, 0,   1, 0, 0,
	2, 0, 0,   0, 0, 3,   0, 0, 0,
	0, 3, 0,   0, 0, 0,   5, 0, 0
])

puts number_place.inspect

puts 

number_place.solve
puts number_place.inspect