Created
November 4, 2012 11:16
-
-
Save n1313/4011429 to your computer and use it in GitHub Desktop.
How I stopped worrying and tried writing ruby
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Ahahaha. Stop worrying. Read this: http://www.slideshare.net/sergeymoiseev/worried-code