如何使用回溯算法制作数独求解器又回来了？
本周末，我根据回溯算法研究了Sudoku Solver（ Ruby测验 ）。 数独加载在81个整数（9×9网格）的数组sudoku_arr ，其中0是空点。 valid? 检查sudoku_arr可以是有效数独的方法。
官方的回溯算法是这样的：尝试下一个空白点的值，检查它是否是有效的数独，如果不是将值增加1（最多9），如果有效继续并在下一个点上尝试第一个值，如果没有增加值前一个0。
因此我们必须跟踪前一个数组，这就是我出错的地方，我不确定它是否可以解决。 我的代码中无法正常工作的部分是SudokuSolver类中的SudokuSolver 。 这是代码：
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 (ie, 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
不幸的是，代码并没有回溯到开头。 代码打印：
“increase_index …”“increase_value …”“increase_value …”“increase_value …”“increase_value …”“increase_value …”“increase_value …”“increase_value …”“increase_value ……“”增加以前的指数……“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。
我还没有介绍你的代码，但回溯算法可归结为以下内容：
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存储为sudoku网格的属性。 那不行。 您需要将此值存储在求解程序例程的局部变量中，以便可以将其推送到堆栈并在回溯搜索树时恢复。
knuth发明了一种名为“Dancing links”的算法，可用于数独游戏。 http://en.wikipedia.org/wiki/Dancing_Links
Soduko问题可以通过确切的覆盖问题来解决。 这是文章http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz
这是我的代码来解决确切的覆盖问题，它也可以解决数独和后退部分在dlx（）
const int INF = 0x3f3f3f3f; const int T = 9; const int N = T*T*T+10; const int M = T*T*T*4+T*T*4+10; int id; int L[M],R[M],U[M],D[M]; int ANS[N],SUM[N],COL[M],ROW[M],H[N]; struct Dancing_links { Dancing_links() {} Dancing_links(int n,int m) { for(int i=0; i<=m; i++) { SUM[i] = 0; L[i+1] = D[i] = U[i] = i; R[i]=i+1; } L[m+1]=R[m]=0,L[0]=m,id=m+1; clr(H,-1); } void remove(int c) { L[R[c]] = L[c]; R[L[c]] = R[c]; for(int i=D[c]; i!=c; i=D[i]) for(int j=R[i]; j!=i; j=R[j]) { U[D[j]] = U[j]; D[U[j]] = D[j]; SUM[COL[j]]--; } } void resume(int c) { for(int i=U[c]; i!=c; i=U[i]) for(int j=L[i]; j!=i; j=L[j]) { U[D[j]] = D[U[j]] = j; SUM[COL[j]]++; } L[R[c]] = R[L[c]] = c; } void add(int r,int c) { ROW[id] = r,COL[id] = c; SUM[c]++; D[id] = D[c],U[D[c]] = id,U[id] = c,D[c] = id; if(H[r] < 0) H[r] = L[id] = R[id] = id; else R[id] = R[H[r]],L[R[H[r]]] = id,L[id] = H[r],R[H[r]] = id; id++; } int dlx(int k) { if(R[0] == 0) { /*output the answer*/return k; } int s=INF,c; for(int i=R[0]; i; i=R[i]) if(SUM[i] < s) s=SUM[c=i]; remove(c); for(int r=D[c]; r!=c; r=D[r]) { ANS[k] = ROW[r]; for(int j=R[r]; j!=r; j=R[j]) remove(COL[j]); int tmp = dlx(k+1); if(tmp != -1) return tmp; //delete if multipal answer is needed for(int j=L[r]; j!=r; j=L[j]) resume(COL[j]); } resume(c); return -1; } };