| Jessehk |
Jul 2nd, 2006 12:23 PM |
[Ruby] Sudoku Solver
Everyone was doing it, so I had to as well. :p
My solution so far is long, but of about 5 different methods I want to employ to solve the puzzle, I've completed 1 to full working order.
I don't know much about computer algorithms (and related math), so my solution attempts to mimic a human solving the puzzle.
So far, the code will look through the supplied puzzle and replace all empty spaces with a class instance, SudokuSolver::Spot. Each spot is supplied with an Array containing all the possibilities for that spot.
The program will then look in the rows and columns of that spot looking at the known numbers, and eliminating possibilities appropriately. At the end of this checking, if there is only one possibility, the number is filled in.
This is just one method I will use to solve the puzzle, but on an easy puzzle, like the one I supplied my program with, 2 spots are already solved.
Here's what I have so far:
solver.rb
:
require 'pp'
class SudokuSolver
class Spot
def initialize
@possible = (1..9).to_a
@number = @possible.length
end
def remove_possibility(n)
@possible.delete(n)
@number = @possible.length
end
def one_possibility?
@number == 1
end
def known
@possible[0]
end
attr_reader :possible, :number
end
def initialize(board)
@board = board.split(/\n/).collect! { |row| process_row(row.scan(/./)) }
assess_board
end
def assess_board
[:rows, :cols].each do |func|
send(func) do |part|
part.collect! { |spot| spot or Spot.new }
end
end
remove_eliminated
end
def cols
0.upto(8) do |x|
col = []
0.upto(8) do |y|
col << @board[y][x]
end
yield col
end
end
def remove_eliminated
[:rows, :cols].each do |func|
send(func) do |part|
part.each do |spot|
if (1..9).include?(spot)
part.select { |x| x.class == Spot }.each do |unknown|
unknown.remove_possibility(spot)
end
end
end
end
end
finalize_answers
end
def finalize_answers
rows do |row|
row.collect! do |spot|
if spot.class == Spot
if spot.one_possibility?
spot.known
else
spot
end
else
spot
end
end
end
end
def process_row(board)
board.collect { |x| if x == '-' then nil else x.to_i end }
end
def rows
@board.each { |row| yield row }
end
def display
count = 0
puts big_divider
rows do |row|
disp = replace_empty_with_spaces(row)
to_show = "| #{disp.join(" | ")} |"
insert_column_seperators(to_show)
puts to_show
count += 1
if count == 3
puts big_divider
count = 0
else
puts little_divider
end
end
end
def big_divider
"+#{"=" * 35}+"
end
def little_divider
"|---|---|---=---|---|---=---|---|---|"
end
def replace_empty_with_spaces(row)
row.collect { |x| if x.class == Spot then ' ' else x end }
end
def empty_spaces
@board.flatten.select { |x| x.nil? or x.class == Spot }.length
end
def to_s
puts "--> #{empty_spaces} empty spaces"
end
def insert_column_seperators(input)
[12, 24].each { |x| input[x] = '=' }
end
attr_reader :board
end
and the main puzzle to test it out:
main.rb
:
$LOAD_PATH.unshift(File.dirname(__FILE__))
require 'solver'
$puzzle = <<-EOF
-8---16--
-7-4---21
5--396---
2-4-5-13-
--89-75--
-57-3-9-2
---563--9
31---2-5-
--58---4-
EOF
board = SudokuSolver.new($puzzle)
board.display
#inspect the board
sleep(2)
pp board
|
