Skip to content

Instantly share code, notes, and snippets.

@perspectivezoom
Created June 26, 2012 03:00
Show Gist options
  • Save perspectivezoom/2992997 to your computer and use it in GitHub Desktop.
Save perspectivezoom/2992997 to your computer and use it in GitHub Desktop.
class SudokuBoard
def initialize(board_str)
@board = board_str.split("").map { |value| Cell.new(value.to_i) }
@groups = []
(generate_rows + generate_cols + generate_grids).each do |group_member_indices_ar|
group_cell_members = group_member_indices_ar.map { |index| @board[index] }
@groups << Group.new(group_cell_members)
end
puts to_s
end
def solve
if complete?
return to_s
else
@board.select { |cell| !cell.solved? }.each do |cell|
cell.potential_values.each do |val|
cell.value = val
result = SudokuBoard.new(to_s).solve
if result.is_a?(String)
return result
end
end
return false #This is the key error checking step. Reaching this line indicates that we have encountered an unsolved cell that, thanks to previous guessing, has no possible valid values. This line of inquiry is a dead end.
end
end
end
def to_s
@board.map { |cell| cell.value }.join
end
private
def complete?
!to_s.include? '0'
end
def generate_rows
ar = (0..80).to_a
Array.new(9).map { ar.shift(9) }
end
def generate_cols
cols = Array.new(9,[])
(0..80).to_a.each { |index| cols[index % 9] += [index] }
cols
end
def generate_grids
grids = Array.new(9,[])
(0..80).to_a.each { |index| grids[(index / 9 / 3 * 3) + ((index % 9) / 3)] += [index]}
grids
end
end
class Group
def initialize(cell_members_ar)
@cells = cell_members_ar
@cells.each { |cell| cell.add_group(self)}
end
def taken_values
@cells.map {|cell| cell.value}.select { |val| val > 0 }
end
end
class Cell
attr_accessor :value
def initialize(value)
@value = value
@groups = []
end
def potential_values
if solved?
[]
else
potential_values_ar = (1..9).to_a
@groups.each { |group| potential_values_ar -= group.taken_values}
potential_values_ar
end
end
def add_group(group)
@groups << group
end
def solved?
@value > 0
end
end
#board = SudokuBoard.new("619030040270061008000047621486302079000014580031009060005720806320106057160400030")
board = SudokuBoard.new("096040001100060004504810390007950043030080000405023018010630059059070830003590007")
#board = SudokuBoard.new("300000000050703008000028070700000043000000000003904105400300800100040000968000200")
puts "final answer #{board.solve}"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment