ruby - 如何使具有回溯算法的数独求解器返回？

Question

这个周末我研究了一个基于回溯算法的数独求解器 (Ruby quiz)。数独被加载到一个包含 81 个整数(9x9 网格)的数组 sudoku_arr 中，其中 0 是空位。有一个 valid? 方法检查 sudoku_arr 是否可以是一个有效的数独。

official backtracking algorithm是这样的:在下一个空点尝试值，检查它是否有效数独，如果不是将值增加 1(最多 9)，如果有效继续并在下一个点尝试第一个值，如果不是增加前一个 0 的值。

因此我们必须跟踪之前的数组，这是我出错的地方，我不确定是否可以解决。下面我的代码中不起作用的部分是 SudokuSolver 类中的 solve_by_increasing_value_previous_index。这是代码:

require 'pp'

sudoku_str = "
+-------+-------+-------+
| _ 6 _ | 1 _ 4 | _ 5 _ |
| _ _ 8 | 3 _ 5 | 6 _ _ |
| 2 _ _ | _ _ _ | _ _ 1 |
+-------+-------+-------+
| 8 _ _ | 4 _ 7 | _ _ 6 |
| _ _ 6 | _ _ _ | 3 _ _ |
| 7 _ _ | 9 _ 1 | _ _ 4 |
+-------+-------+-------+
| 5 _ _ | _ _ _ | _ _ 2 |
| _ _ 7 | 2 _ 6 | 9 _ _ |
| _ 4 _ | 5 _ 8 | _ 7 _ |
+-------+-------+-------+"

class SudokuException < StandardError
  attr_reader :sudoku_arr
  def initialize(message, sudoku_arr)
    super(message)
    @sudoku_arr = sudoku_arr
  end
end

class Sudoku

  attr_accessor :sudoku_arr, 
                :index_of_tried_value,
                :tried_value

  def initialize(sudoku_arr, index_of_tried_value, tried_value)
    @sudoku_arr = sudoku_arr
    @index_of_tried_value = index_of_tried_value
    @tried_value = tried_value
  end

  def rows_valid?
    rows_have_unique_values?(@sudoku_arr)
  end

  def columns_valid?
    rows_have_unique_values?(@sudoku_arr.each_slice(9).to_a.transpose.flatten!)
  end

  def squares_valid?
    tmp_a = @sudoku_arr.each_slice(3).to_a

    rows_have_unique_values?(
    (tmp_a[0] << tmp_a[3]  << tmp_a[6]  << tmp_a[1]  << tmp_a[4]  << tmp_a[7]  <<
    tmp_a[2]  << tmp_a[5]  << tmp_a[8]  << tmp_a[9]  << tmp_a[12] << tmp_a[15] <<
    tmp_a[10] << tmp_a[13] << tmp_a[16] << tmp_a[11] << tmp_a[14] << tmp_a[17] <<
    tmp_a[18] << tmp_a[21] << tmp_a[24] << tmp_a[19] << tmp_a[22] << tmp_a[25] <<
    tmp_a[20] << tmp_a[23] << tmp_a[26]).flatten!)
  end

  def valid?
    rows_valid? && columns_valid? && squares_valid?
  end

  def rows_have_unique_values?(arr)
    (arr[0,9]- [0]).uniq.size == (arr[0,9]- [0]).size &&
    (arr[9,9]- [0]).uniq.size == (arr[9,9]- [0]).size && 
    (arr[18,9]-[0]).uniq.size == (arr[18,9]-[0]).size && 
    (arr[27,9]-[0]).uniq.size == (arr[27,9]-[0]).size && 
    (arr[36,9]-[0]).uniq.size == (arr[36,9]-[0]).size && 
    (arr[45,9]-[0]).uniq.size == (arr[45,9]-[0]).size && 
    (arr[54,9]-[0]).uniq.size == (arr[54,9]-[0]).size && 
    (arr[63,9]-[0]).uniq.size == (arr[63,9]-[0]).size && 
    (arr[72,9]-[0]).uniq.size == (arr[72,9]-[0]).size 
  end

end


class SudokuSolver

  attr_accessor :sudoku_arr, 
                :indeces_of_zeroes

  def initialize(str)
    @sudoku_arr = str.gsub(/[|\+\-\s]/,"").gsub(/_/,'0').split(//).map(&:to_i)
    @indeces_of_zeroes = []
    @sudoku_arr.each_with_index { |e,index| @indeces_of_zeroes << index if e.zero? }
  end

  def solve
    sudoku_arr = @sudoku_arr
    try_index = @indeces_of_zeroes[0]
    try_value = 1
    sudoku = Sudoku.new(sudoku_arr, try_index, try_value)
    solve_by_increasing_value(sudoku)
  end

  def solve_by_increasing_value(sudoku)

    if sudoku.tried_value < 10
      sudoku.sudoku_arr[sudoku.index_of_tried_value] = sudoku.tried_value
      if sudoku.valid?
        pp "increasing_index..."
        solve_by_increasing_index(sudoku)
      else
        pp "increasing_value..."
        sudoku.tried_value += 1
        solve_by_increasing_value(sudoku)
      end
    else
      pp "Increasing previous index..."
      solve_by_increasing_value_previous_index(sudoku)
    end
  end

  def solve_by_increasing_index(sudoku)
    if sudoku.sudoku_arr.index(0).nil? 
      raise SudokuException(sudoku.sudoku_arr.each_slice(9)), "Sudoku is solved."
    end

    sudoku.index_of_tried_value = sudoku.sudoku_arr.index(0)
    sudoku.tried_value = 1

    solve_by_increasing_value(sudoku)
  end

  def solve_by_increasing_value_previous_index(sudoku)
    # Find tried index and get the one before it
    tried_index = sudoku.index_of_tried_value
    previous_index = indeces_of_zeroes[indeces_of_zeroes.index(tried_index)-1]

    # Setup previous Sudoku so we can go back further if necessary:

    # Set tried index back to zero
    sudoku.sudoku_arr[tried_index] = 0
    # Set previous index
    sudoku.index_of_tried_value = previous_index
    # Set previous value at index
    sudoku.tried_value = sudoku.sudoku_arr[previous_index]
    pp previous_index
    pp sudoku.tried_value
    # TODO Throw exception if we go too far back (i.e., before first index) since Sudoku is unsolvable

    # Continue business as usual by increasing the value of the previous index
    solve_by_increasing_value(sudoku)
  end

end

sudoku_solver = SudokuSolver.new(sudoku_str)
sudoku_solver.solve

不幸的是，代码没有回溯到开头。代码打印:

"increasing_index..." "increasing_value..." "increasing_value..." "increasing_value..." "increasing_value..." "increasing_value..." "increasing_value..." "increasing_value..." "increasing_value..." "Increasing previous index..." 16 2

在一个循环中，直到它抛出一个 SystemStackError，因为堆栈级别太深。

发生的情况是“回溯”不超过一个索引。当 solve_by_increasing_value_previous_index 转到前一个索引时，它会在那里取前一个值。在这种情况下，它是 2，但 2 不起作用，因此我们应该将它减少到 1 并继续，如果这不起作用，则丢弃 2 并再次将其设为 0，然后返回更远的地方。

不幸的是，我没有看到实现此算法的简单方法。 _{(我想到的是一个 @too_much_looping 变量，它在 solve_by_increasing_value_previous_index 被调用时递增，并在 81 次后重置。但这只会帮助进行再返回一次，我们就不能循环回到开头。}\

希望有人能给我一些帮助!也非常欢迎一般代码评论，我怀疑这不是 100% 地道的 Ruby。

Answer 1

我还没有仔细阅读您的代码，但回溯算法归结为以下内容:

int solve(char board[81]) {
    int i, c;
    if (!is_valid(board)) return 0;
    c = first_empty_cell(board);
    if (c<0) return 1; /* board is full */
    for (i=1; i<=9; i++) {
        board[c] = i;
        if (solve(board)) return 1;
    }
    board[c] = 0;
    return 0;
}

这是一个递归函数，在它找到的第一个空单元格中尝试从 1 到 9 的每个值(由 first_empty_cell() 返回) ).如果这些值都没有导致解决方案，那么您一定位于搜索树的死分支上，因此可以将有问题的单元格重置为零(或您用来指示未填充单元格的任何值)。

当然，还有很多其他事情可以让您的软件更快地得出解决方案，但就回溯而言，仅此而已。

---

附录:

好的，我现在正在浏览您的代码。看起来您正在将 index_of_tried_value 存储为数独网格的属性。那行不通的。您需要将此值存储在求解器例程的局部变量中，以便在您回溯搜索树时将其压入堆栈并恢复。