Skip to content

Instantly share code, notes, and snippets.

@jkaihsu
Created March 19, 2013 15:06
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jkaihsu/5196883 to your computer and use it in GitHub Desktop.
Save jkaihsu/5196883 to your computer and use it in GitHub Desktop.
Not done yet.
class Sudoku
def initialize(string)
string_of_array = string.split("")
@board = Array.new(9) {string_of_array.shift(9)}
end
def solve!
first_empty = find_empty_cell
possible = possibilities(first_empty)
puts "This is: #{first_empty[0]}, #{first_empty[1]}, #{possible}"
reassign(first_empty[0], first_empty[1], possible)
end
def find_empty_cell(x_coordinate = 0, y_coordinate = 0)
x_coordinate.upto(8) do |x|
y_coordinate.upto(8) do |y|
if @board[x][y] == '0'
x_coordinate = x
y_coordinate = y
return [x_coordinate, y_coordinate]
end
end
end
end
def possibilities(first_empty)
x_coordinate = first_empty[0]
y_coordinate = first_empty[1]
possibilities = ['1','2','3','4','5','6','7','8','9']
row = evaluate_row(x_coordinate, y_coordinate, possibilities)
col = evaluate_column(x_coordinate, y_coordinate, possibilities)
grid = evaluate_grid(x_coordinate, y_coordinate, possibilities)
possibilities = row + col + grid
possibilities.select { |number| possibilities.count(number) > 2 }.uniq
end
def evaluate_row(x_coordinate, y_coordinate, possibilities)
possibilities = possibilities - @board[x_coordinate]
end
def evaluate_column(x_coordinate, y_coordinate, possibilities)
column = []
@board.each do |num|
column << @board[@board.index(num)][y_coordinate]
end
possibilities = possibilities - column
end
def evaluate_grid(x_coordinate, y_coordinate, possibilities)
grid_array =
[ [[0,0], [0,1], [0,2], [1,0], [1,1], [1,2], [2,0], [2,1], [2,2]],
[[0,3], [0,4], [0,5], [1,3], [1,4], [1,5], [2,3], [2,4], [2,5]],
[[0,6], [0,7], [0,8], [1,6], [1,7], [1,8], [2,6], [2,7], [2,8]],
[[3,0], [3,1], [3,2], [4,0], [4,1], [4,2], [5,0], [5,1], [5,2]],
[[3,3], [3,4], [3,5], [4,3], [4,4], [4,5], [5,3], [5,4], [5,5]],
[[3,6], [3,7], [3,8], [4,6], [4,7], [4,8], [5,6], [5,7], [5,8]],
[[6,0], [6,1], [6,2], [7,0], [7,1], [7,2], [8,0], [8,1], [8,2]],
[[6,3], [6,4], [6,5], [7,3], [7,4], [7,5], [8,3], [8,4], [8,5]],
[[6,6], [6,7], [6,8], [7,6], [7,7], [7,8], [8,6], [8,7], [8,8]]
]
grid = []
grid_array.each do |x|
if x.include?([x_coordinate, y_coordinate])
grid = x
end
end
grid_poss = []
grid.each do |x,y|
grid_poss << @board[x][y]
end
possibilities = possibilities - grid_poss
end
def reassign(x_coordinate, y_coordinate, possibilities)
if possibilities.length == 1
p "This is from evaluate_grid, solved @ x = #{x_coordinate}, y = #{y_coordinate}: #{possibilities}"
self.next_cell(x_coordinate, y_coordinate, possibilities[0])
else
if y_coordinate == 8
y_coordinate = 0
x_coordinate = x_coordinate + 1
self.find_empty_cell(x_coordinate, y_coordinate)
else
self.find_empty_cell(x_coordinate, y_coordinate+1)
end
end
end
def next_cell(x_coordinate, y_coordinate, answer)
p "This is the original board:"
p self
@board[x_coordinate][y_coordinate] = answer
puts "This is from reassign, new value: #{@board[x_coordinate][y_coordinate]}"
p "This is the new board:"
p self
self.find_empty_cell(y_coordinate)
end
def to_s
@board.map{|r| r.join(" ")}.join "\n"
end
end
# board_string = File.readlines('sample.unsolved.txt').first.chomp
game = Sudoku.new('003021600900305001001806400008102900700000008006708200002609500800203009005010300')
puts game
puts game.solve!
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment