92 lines
2.2 KiB
Ruby
92 lines
2.2 KiB
Ruby
def read_matrix(data)
|
|
lines = data.lines
|
|
9.times.collect { |i| 9.times.collect { |j| lines[i][j].to_i } }
|
|
end
|
|
|
|
def permissible(matrix, i, j)
|
|
ok = [nil, *1..9]
|
|
check = ->(x,y) { ok[matrix[x][y]] = nil if matrix[x][y].nonzero? }
|
|
# Same as another in the column isn't permissible...
|
|
9.times { |x| check[x, j] }
|
|
# Same as another in the row isn't permissible...
|
|
9.times { |y| check[i, y] }
|
|
# Same as another in the 3x3 block isn't permissible...
|
|
xary = [ *(x = (i / 3) * 3) .. x + 2 ] #=> [0,1,2], [3,4,5] or [6,7,8]
|
|
yary = [ *(y = (j / 3) * 3) .. y + 2 ]
|
|
xary.product(yary).each { |x, y| check[x, y] }
|
|
# Gathering only permitted one
|
|
ok.compact
|
|
end
|
|
|
|
def deep_copy_sudoku(matrix)
|
|
matrix.collect { |row| row.dup }
|
|
end
|
|
|
|
def solve_sudoku(matrix)
|
|
loop do
|
|
options = []
|
|
9.times do |i|
|
|
9.times do |j|
|
|
next if matrix[i][j].nonzero?
|
|
p = permissible(matrix, i, j)
|
|
# If nothing is permissible, there is no solution at this level.
|
|
return if p.empty? # return nil
|
|
options << [i, j, p]
|
|
end
|
|
end
|
|
# If the matrix is complete, we have a solution...
|
|
return matrix if options.empty?
|
|
|
|
i, j, permissible = options.min_by { |x| x.last.length }
|
|
|
|
# If there is an option with only one solution, set it and re-check permissibility
|
|
if permissible.length == 1
|
|
matrix[i][j] = permissible[0]
|
|
next
|
|
end
|
|
|
|
# We have two or more choices. We need to search both...
|
|
permissible.each do |v|
|
|
mtmp = deep_copy_sudoku(matrix)
|
|
mtmp[i][j] = v
|
|
ret = solve_sudoku(mtmp)
|
|
return ret if ret
|
|
end
|
|
|
|
# We did an exhaustive search on this branch and nothing worked out.
|
|
return
|
|
end
|
|
end
|
|
|
|
def print_matrix(matrix)
|
|
puts "Impossible" or return unless matrix
|
|
|
|
border = "+-----+-----+-----+"
|
|
9.times do |i|
|
|
puts border if i%3 == 0
|
|
9.times do |j|
|
|
print j%3 == 0 ? "|" : " "
|
|
print matrix[i][j] == 0 ? "." : matrix[i][j]
|
|
end
|
|
puts "|"
|
|
end
|
|
puts border
|
|
end
|
|
|
|
data = <<EOS
|
|
394__267_
|
|
___3__4__
|
|
5__69__2_
|
|
_45___9__
|
|
6_______7
|
|
__7___58_
|
|
_1__67__8
|
|
__9__8___
|
|
_264__735
|
|
EOS
|
|
|
|
matrix = read_matrix(data)
|
|
print_matrix(matrix)
|
|
puts
|
|
print_matrix(solve_sudoku(matrix))
|