# ruby – 高效的置换树算法

>在分支点尝试所有可能的解决方案

>如果无法解决单元格,则终止分支

>如果达到解决方案,则终止分支

```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>]```