Create a gist now

Instantly share code, notes, and snippets.

Sudoku solver
def cross(cols, rows)
cols.split('').product(rows.split('')).map{|c, r| c + r}
end
$digits = '123456789'
$rows = 'ABCDEFGHI'
$cols = $digits
$squares = cross($rows, $cols)
$unitlist = $cols.split('').map{|c| cross($rows, c)} +
$rows.split('').map{|r| cross(r, $cols)} +
['ABC', 'DEF', 'GHI'].product(['123', '456', '789']).map{|c, r| cross(c, r)}
$units = Hash[$squares.zip($squares.map{|s| $unitlist.select{|u| u.include?(s)}})]
$peers = Hash[$squares.zip($squares.map{|s| $units[s].flatten.uniq - [s]})]
def parse_grid(grid)
values = Hash[$squares.zip($squares.map{$digits.dup})]
grid_values(grid).each{|s, d|
return false if $digits.include?(d) && !assign(values, s, d)
}
values
end
def grid_values(grid)
chars = grid.split('').select{|c| $digits.include?(c) || '0.'.include?(c)}
raise ArgumentError.new("can't convert grid into a Hash") if chars.size != 81
Hash[$squares.zip(chars)]
end
def assign(values, s, d)
other_values = values[s].delete(d)
if other_values.split('').all?{|d2| eliminate(values, s, d2)}
values
else
false
end
end
def eliminate(values, s, d)
return values if !values[s].include?(d)
values[s] = values[s].delete(d)
case values[s].size
when 0
return false
when 1
d2 = values[s]
return false if !$peers[s].all?{|s2| eliminate(values, s2, d2)}
end
$units[s].each{|u|
dplaces = u.select{|s2| values[s2].include?(d)}
case dplaces.size
when 0
return false
when 1
return false if !assign(values, dplaces[0], d)
end
}
values
end
def display(values)
width = 1 + $squares.map{|d| d.size}.max
line = (['-' * (width * 3)] * 3).join('+')
$rows.split('').each{|r|
$cols.split('').each{|c|
print values[r + c].center(width)
print '|' if '36'.include?(c)
print "\n" if c == '9'
}
puts line if 'CF'.include?(r)
}
puts
end
def solve(grid)
search(parse_grid(grid))
end
def search(values)
return false if !values
return values if $squares.all?{|s| values[s].size == 1}
s, n = values.select{|s, d| d.size > 1}.min_by{|s, d| d.size}
values[s].split('').map{|d| search(assign(values.dup, s, d))}.find{|v| v}
end
display(solve('003020600900305001001806400008102900700000008006708200002609500800203009005010300'))
display(solve('4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'))
display(solve('005300000800000020070010500400005300010070006003200080060500009004000030000009700'))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment