Sudoku: Difference between revisions
Content added Content deleted
(add Ruby) |
|||
| Line 600: | Line 600: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
Example of a back-tracking solver, from [[wp:Algorithmics of sudoku]] |
Example of a back-tracking solver, from [[wp:Algorithmics of sudoku]] |
||
{{works with|Ruby|1.8.7+}} |
|||
<lang ruby>def read_matrix(fh) |
<lang ruby>def read_matrix(fh) |
||
matrix = [] |
matrix = [] |
||
| Line 652: | Line 653: | ||
def solve_sudoku(matrix) |
def solve_sudoku(matrix) |
||
loop do |
|||
options = [] |
options = [] |
||
(0..8).each { |i| |
(0..8).each { |i| |
||
| Line 659: | Line 660: | ||
p = permissible(matrix, i, j) |
p = permissible(matrix, i, j) |
||
# If nothing is permissible, there is no solution at this level. |
# If nothing is permissible, there is no solution at this level. |
||
return |
return nil if p.length == 0 |
||
options.push({:i => i, :j => j, :permissible => p}) |
options.push({:i => i, :j => j, :permissible => p}) |
||
} |
} |
||
| Line 666: | Line 667: | ||
return matrix if options.length == 0 |
return matrix if options.length == 0 |
||
omin = options. |
omin = options.min_by { |x| x[:permissible].length } |
||
a[:permissible].length <=> b[:permissible].length |
|||
} |
|||
# If there is an option with only one solution, set it and re-check permissibility |
# If there is an option with only one solution, set it and re-check permissibility |
||
| Line 681: | Line 680: | ||
mtmp[omin[:i]][omin[:j]] = v |
mtmp[omin[:i]][omin[:j]] = v |
||
ret = solve_sudoku(mtmp) |
ret = solve_sudoku(mtmp) |
||
return ret if ret |
|||
return ret |
|||
end |
|||
} |
} |
||
# We did an exhaustive search on this branch and nothing worked out. |
# We did an exhaustive search on this branch and nothing worked out. |
||
return |
return nil |
||
end |
end |
||
end |
end |
||
def print_matrix(matrix) |
def print_matrix(matrix) |
||
if |
if not matrix |
||
puts "Impossible" |
|||
return |
return |
||
end |
end |
||