gistfile1.rb

# A program to solve sodoku.

# First a few definitions, starting with array division

class Array
	define_method "/" do |len|
		a = []
		each_with_index do |x,i|
			a << [] if i % len == 0
			a.last << x
		end
		a
	end
	
	def count(item)
		count = 0
		each do |x|
			if x == item
				count++
			end
		end
		count
	end
end

class Sudoku
	def initialize
		grid_numbers = (0..80).to_a

		# We need to create the groups: rows, squares, columns

		rows = grid_numbers / 9

		cols = []
		(0..8).to_a.each do |x|
			cols[x] = []
			rows.each do |row|
				cols[x] << row[x]
			end
		end

		boxes = []
		3.times do |x|
			row_a = rows[x * 3] / 3
			row_b = rows[x * 3 + 1] / 3
			row_c = rows[x * 3 + 2] / 3
			3.times do |y|
				boxes << row_a[y] + row_b[y] + row_c[y]
			end
		end
			
		@groups = rows + cols + boxes
			
		# Now we find all the 'neiboughs' of any cell

		@neiboughs = {}
		@cell_groups = {}

		(0..80).to_a.each do |cell|
			@neiboughs[cell] = []
			@cell_groups[cell] = []
			@groups.each_with_index do |group, group_index|
				if group.member?(cell)
					@neiboughs[cell] = @neiboughs[cell] + group
					@cell_groups[cell] << group_index
				end
			end
			@neiboughs[cell].uniq!
		end

		# Create our cell possabilities

		@possible = {}

		(0..80).to_a.each do |cell|
			@possible[cell] = (1..9).to_a
		end
		
		# We need all the unused numbers in each groups
		
		@group_possible = {}
		
		(0..26).to_a.each do |group|
			@group_possible[group] = (1..9).to_a
		end
	end
	
	def sample
		".2.178.3..4.3.2.9.1.......6..86.35..3.......4..67.92...8.9.1.6..1.436.5."
	end
	
	def show (cell)
		a = []
		81.times do |x|
			a[x] = false
		end
		@neiboughs[cell].each do |x|
			a[x] = true
		end
		9.times do |y|
			9.times do |x|
				if (x + 9 * y) == cell
					print "* "
				else
					if a[x + 9 * y]
						print "X "
					else
						print ". "
					end
				end
			end
			puts ""
		end
	end
	
	def output
		9.times do |y|
			9.times do |x|
				if @possible[(x + 9 * y)].size == 1
					print @possible[(x + 9 * y)].first.to_s + " "
				else
					print ". "
				end
			end
			puts ""
		end
	end
		
	# Read in sudoku data
	def read(data)
		#data = ".2.178.3..4.3.2.9.1.......6..86.35..3.......4..67.92...8.9.1.6..1.436.5."

		data.gsub!(".", "0")
		data.delete! '^0-9_'

		grid_data = data.split("")

		(0..80).to_a.each do |cell|
			if grid_data[cell].to_i != 0
				@possible[cell] = [grid_data[cell].to_i]
			end
		end
	end

	# Now we have the data, the solving begings!
	def solve
		
		
	end
	
	def data
		@possible
	end
	
	#private
	
	def reduce
		# Removes any possabilities that are impossible
		81.times do |cell|
			@neiboughs[cell].each do |neibough|
				if @possible[neibough].size == 1 and @possible[cell].member?(@possible[neibough].first) and neibough != cell
					@possible[cell] = @possible[cell] - @possible[neibough]
					if @possible[cell].size == 1
						@cell_groups[cell].each do |group|
							@group_possible[group] = @group_possible[group] - @possible[cell]
						end
					end
				end
			end
		end
	end
	
	def deduce
		81.times do |cell|
			possible = (1..9).to_a
			@cell_groups[cell].each do |group|
				possible = possible - ((1..9).to_a - @group_possible[group])
			end
			@possible[cell] = possible
		end
	end
	
	def solved?
		# If all cells have a single possability after calling reduce, the puzzle is solved
		reduce
		
		81.times do |cell|
			if @possible[cell].size > 1
				return false
			end
		end
		
		true
	end

end