I tried to write an algorithm to solve any sudoku. However, my initial approach was wrong, because I did not understand that a well-formed sudoku should have only one solution.
Thus, the resulting algorithm is not optimized for solving sudoku and is much more general: it recursively generates every possible outcome / layout for the current sudoku layout. Thus, the algorithm can theoretically find any solution for an empty sudoku (but I / we / the human race will probably not be there to see the way out).
My first question is: for this type of search algorithm, what is the best approach - how can my algorithm be improved? The overall strategy was as follows:
- try all possible solutions at the branch point
- completion of the branch if the cell cannot be resolved.
- completion of the branch if a decision is reached
The structure and approach were adapted from a time-resolved solution outlined to solve the eight queens problem in SICP ( https://mitpress.mit.edu/sicp/full-text/book/book-ZH-15.html ) and it looks like this is a backtracking algorithm (with a “time” state entered into the machine), is this true in my case?
My second question is: how can I use the Ruby> = 2.x Lazy functionality to generate an enumerable when working with a recursive algorithm?
- - (sudoku).first(x) x-. /. , , , , .
key code , : https://gist.github.com/djtango/fe9322748cf8a055fc0e
def solve(sudoku)
guess(simplify_sudoku(sudoku))
end
def guess(sudoku, row = 0, column = 0)
return sudoku.flatten if end_of_grid?(row, column)
return guess(sudoku, row + 1, 0) if end_of_column?(column)
return guess(sudoku, row, column + 1) if filled?(sudoku, row, column)
return nil if insoluble?(sudoku, row, column)
permissible_values(sudoku, row, column).map do |value|
guess(update_sudoku(sudoku, value, row, column), row, column + 1)
end
end
def simplify_sudoku(sudoku)
return sudoku if no_easy_solutions?(sudoku)
simplify_sudoku(fill_in(sudoku))
end
def fill_in(sudoku)
new_sudoku = copy_sudoku(sudoku)
new_sudoku.map.with_index do |row, row_index|
row.map.with_index do |column, column_index|
solution = permissible_values(new_sudoku, row_index, column_index)
easy_and_not_filled?(solution, new_sudoku, row_index, column_index) ? [solution.first] : column
end
end
end
:
permissible_values(sudoku, row, column).map do |value|
guess(update_sudoku(sudoku, value, row, column), row, column + 1)
end
:
solve(blank_sdk)
=> #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 5, 6, 7, 8, 9]>:map>
solve(blank_sdk).first(10)
=> [#<Enumerator::Lazy: #<Enumerator::Lazy: [2, 3, 4, 5, 6, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 3, 4, 5, 6, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 4, 5, 6, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 5, 6, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 6, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 5, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 5, 6, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 5, 6, 7, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 5, 6, 7, 8]>:map>]
solve(blank_sdk).first(1000000000000)
=> [#<Enumerator::Lazy: #<Enumerator::Lazy: [2, 3, 4, 5, 6, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 3, 4, 5, 6, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 4, 5, 6, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 5, 6, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 6, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 5, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 5, 6, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 5, 6, 7, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 5, 6, 7, 8]>:map>]