Skip to content

Instantly share code, notes, and snippets.

@n1313
Created November 4, 2012 11:16
Show Gist options
  • Save n1313/4011429 to your computer and use it in GitHub Desktop.
Save n1313/4011429 to your computer and use it in GitHub Desktop.
How I stopped worrying and tried writing ruby
class Sudoku
def initialize(string)
@grid = string.gsub(/[^0-9]/, "").split('').map(&:to_i).each_slice(9).to_a
@empty = []
@possibles = Array.new(9){ [] }
@grid.each_with_index do |row, r|
row.each_with_index do |cell, c|
if cell == 0
@empty << [r,c]
@possibles[r][c] = possible(r,c)
else
@possibles[r][c] = nil
end
end
end
end
def status
puts @empty.inspect
puts @possibles.inspect
end
def put(value, r, c)
@grid[r][c] = value
@empty.delete([r,c])
@possibles[r][c] = nil
(@empty & changed(r,c)).each { |coords| @possibles[coords[0]][coords[1]] = possible(*coords) }
end
def changed(r,c)
changed = []
(0..8).each do |n|
changed << [r, n]
changed << [n, c]
end
(changed + square_coords(r,c)).uniq
end
def array_valid?(array)
(1..9).to_a.all? { |n| array.count(n) < 2 }
end
def draw
@grid.each_with_index do |row, r|
puts '+GRID-----------------+---------------------+---------------------+' if r % 3 == 0
row.each_with_index do |cell, c|
print '|' if c % 3 == 0
print cell == 0 ? ' ' : cell.to_s.center(7)
end
puts '|'
end
puts '+---------------------+---------------------+---------------------+'
end
def draw_possibles
@possibles.each_with_index do |row, r|
puts '+POSS-----------------+---------------------+---------------------+' if r % 3 == 0
row.each_with_index do |cell, c|
print '|' if c % 3 == 0
print cell.to_s.center(7)
end
puts '|'
end
puts '+---------------------+---------------------+---------------------+'
end
def row_values(n)
@grid[n]
end
def col_values(n)
@grid.map { |row| row[n] }
end
def square_values(r, c)
square = []
square_coords(r,c).each { |coords| square << @grid[coords[0]][coords[1]] }
square
end
def row_possibles(n)
@possibles[n]
end
def col_possibles(n)
@possibles.map { |row| row[n] }
end
def square_possibles(r, c)
square = []
square_coords(r,c).each { |coords| square << @possibles[coords[0]][coords[1]] }
square
end
def square_coords(r, c)
coords = []
row_from = 3 * r.div(3)
row_to = row_from + 2
col_from = 3 * c.div(3)
col_to = col_from + 2
(row_from..row_to).each do |r|
(col_from..col_to).each do |c|
coords << [r, c]
end
end
coords
end
def missing(values)
(1..9).to_a - values
end
def possible(r, c)
if @grid[r][c] == 0
missing(row_values(r)) & missing(col_values(c)) & missing(square_values(r, c))
else
nil
end
end
def rows_valid?
(0..8).to_a.all? { |n| array_valid?(row_values(n)) }
end
def cols_valid?
(0..8).to_a.all? { |n| array_valid?(col_values(n)) }
end
def squares_valid?
(0..2).to_a.all? { |n| array_valid?(square_values(n*3, n*3)) }
end
def valid?
rows_valid? & cols_valid? & squares_valid?
end
def solved?
@empty.empty? & valid?
end
def heuristic_a
while !@empty.empty?
definite = @empty.select { |coords| @possibles[coords[0]][coords[1]].one? }
break if definite.empty?
definite.each { |coords| put(@possibles[coords[0]][coords[1]].first, *coords) }
end
end
def heuristic_b
if !@empty.empty?
heuristic_b_rows
heuristic_b_cols
heuristic_b_squares
end
end
def heuristic_b_rows
(0..8).each do |n|
heuristic_b_array(row_possibles(n))
end
end
def heuristic_b_cols
@possibles = @possibles.transpose
heuristic_b_rows
@possibles = @possibles.transpose
end
def heuristic_b_squares
(0..2).each do |n|
square = heuristic_b_array(square_possibles(n*3, n*3))
square.each_with_index do |cell, i|
r = n*3 + i.div(3)
c = n*3 + i%3
@possibles[r][c] = cell
end
end
end
def heuristic_b_array(array)
count = Array.new(10){0}
array.each do |a|
next unless a
a.each { |b| count[b] += 1 }
end
singles = []
count.each_with_index { |n, i| singles << i if n == 1 }
singles.each do |s|
array.each_with_index do |a,i|
next unless a
if a.index(s)
puts "Was #{array[i]}, now [#{s}]"
array[i] = [s]
end
end
end
array
end
def solve
puts ''
#while !solved?
heuristic_a
heuristic_b
heuristic_a
heuristic_b
#end
draw
puts valid? ? 'Valid' : 'Invalid'
puts solved? ? 'Solved' : 'Not solved'
end
end
# puzzle = Sudoku.new('530-070-000-600-195-000-098-000-060-800-060-003-400-803-001-700-020-006-060-000-280-000-419-005-000-080-079')
# puzzle.solve
# puzzle = Sudoku.new('100-489-006-730-000-040-000-001-295-007-120-600-500-703-008-006-095-700-914-600-000-020-000-037-800-512-004')
# puzzle.solve
# puzzle = Sudoku.new('000-260-701-680-070-090-190-004-500-820-100-040-004-602-900-050-003-028-009-300-074-040-050-036-703-018-000')
# puzzle.solve
# puzzle = Sudoku.new('020-608-000-580-009-700-000-040-000-370-000-500-600-000-004-008-000-013-000-020-000-009-800-036-000-306-090')
# puzzle.solve
puzzle = Sudoku.new('200-300-000-804-062-003-013-800-200-000-020-390-507-000-621-032-006-000-020-009-140-601-250-809-000-001-002')
puzzle.solve
@bopm
Copy link

bopm commented Nov 4, 2012

Ahahaha. Stop worrying. Read this: http://www.slideshare.net/sergeymoiseev/worried-code

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment