Sucky Sudoku solver

gistfile1.rb

class SudokuSolver
	def initialize (m_input = Array.new(9) { [] }, m_solve = Array.new(9) { [] })
		@m_input = m_input
		@m_solve = m_solve

		0.upto(80) do |i|
			set_cell(i, 0, @m_input)
			set_cell(i, 0, @m_solve)
		end
	end

	def set_cell(cell, value, matrix)
		if cell.between?(0,80) and value.between?(0,9)
			matrix[cell/9][cell%9] = value
			return true
		end
	end
	
	def get_cell(cell, matrix)
		return cell.between?(0,80) ? matrix[cell/9][cell%9] : false
	end

	# Transforms each cell (0-80) to the corresponding top-left (0,3, ... ,57,60) of each 3x3 square.
	def fix_pos(cell)
		return 27*(cell/9/3) + 3*(cell/3%3)
	end

	def get_valid(cell, matrix)
		return false if !(cell).between?(0,80)
		
		valid = [1,2,3,4,5,6,7,8,9]

		# Look for duplicates in row / column.
		0.upto(8) do |n|
			valid[matrix[n][cell%9]-1] = 0 if matrix[n][cell%9] != 0
			valid[matrix[cell/9][n]-1] = 0 if matrix[cell/9][n] != 0
		end

		# Look for duplicates in "square".
		0.upto(2) do |n|
			[0,9,18].each do |m|
				value = get_cell(fix_pos(cell) + n + m, matrix) 
				valid[value - 1] = 0 if value.between?(1,9)
			end
		end

		return valid.delete_if { |x| x == 0 }
	end

	def solve(i = 0, input_matrix = @m_input, solve_matrix = @m_solve)
		return true if i == 81

		# Do not modify the input matrix.
		return solve(i+1, input_matrix, solve_matrix) if solve_matrix[i/9][i%9] != 0 and solve_matrix[i/9][i%9] == input_matrix[i/9][i%9] 

		get_valid(i, solve_matrix).each do |n|
			set_cell(i, n, solve_matrix)
			return true if solve(i+1, input_matrix, solve_matrix)
			set_cell(i, 0, solve_matrix) 
		end

		return false
	end

	# Very simple user-input mode.
	def fill(matrix = @m_input)
		0.upto(80) do |i|
			matrix[i/9][i%9] = "*"
			puts ascii(matrix) + "\nPick a number 0-9 (Enter or 0 is blank):"
			matrix[i/9][i%9] = 0
			
			input = gets.chomp.to_i
			puts "\n\n\n==========================================\n\n\n"
			
			if !get_valid(i, matrix).push(0).include?(input)
				puts "* * * * * * * * * * * * *\n Warning: invalid choice! \n* * * * * * * * * * * * *"
				redo
			end

			set_cell(i, input, matrix)
		end

		@m_solve = @m_input
	end

	# ASCII-version of the Sudoku puzzle.
	def ascii(matrix = @m_solve)
		ascii = String.new
		0.upto(80) do |n|
			ascii = ascii + "\n+-------+-------+-------+" if n % 27 == 0
			ascii = ascii + "\n" if n % 9  == 0
			ascii = ascii + "| " if n % 3 == 0
			ascii = ascii + (get_cell(n, matrix) != 0 ? get_cell(n, matrix).to_s : "_") + " "
			ascii = ascii + "|" if n % 9 == 8
		end
		
		return ascii + "\n+-------+-------+-------+"
	end
end

# Example of how to use it.
# User inputs the sudoku puzzle from commandline.
s = SudokuSolver::new
s.fill
start_time = Time.now
s.solve
puts "* * * * * * * * * * * * *\nSolved it in #{Time.now - start_time}s!\n* * * * * * * * * * * * * #{s.ascii}"