如何使带有回溯算法的Sudoku求解器返回？ [英] How to make Sudoku solver with backtracking algorithm go back?
问题描述
这个周末，我基于回溯算法研究了Sudoku Solver（ Ruby测验）。数独加载到由81个整数（9x9网格）组成的数组 sudoku_arr 中，其中0是空白点。有一种 valid？方法可检查 sudoku_arr 是否可以是有效的数独。
官方的回溯算法像这样：在下一个空白点尝试值，检查它是否是有效的数独，如果不是，则将值增加1（最多9），如果有效，则在下一个点尝试第一个值，如果不增加前一个0的值。 / p>
在这里，我们必须跟踪先前的数组，这就是我要出错的地方，我不确定是否可以解决。我下面的代码中不起作用的部分是 SudokuSolver 类中的 solve_by_increasing_value_previous_index 。代码如下：
要求'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（消息，sudoku_arr）
super（消息）
@sudoku_arr = sudoku_arr
结束
结束
类数独
attr_accessor：sudoku_arr，
：index_of_tried_value，
：tried_value
def initialize（sudoku_arr，index_of_tried_value，tryd_value）
@sudoku_arr = sudoku_arr
@index_of_tried_value = index_of_tried_value
@tried_value = tryd_value
end
def rows_valid？
rows_have_unique_values？（@ sudoku_arr）
结束
def columns_valid？
rows_have_unique_values？（@ sudoku_arr.each_slice（9）.to_a.transpose.flatten！）
结束
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有效吗？
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
结束
结束
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<<索引是否为e.zero？ }
结束
def解决
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）
结束
def resolve_by_increasing_value（sudoku）
如果sudoku.tried_value< 10
sudoku.sudoku_arr [sudoku.index_of_tried_value] = sudoku.tried_value
如果sudoku.valid？
pp增加索引...
solve_by_increasing_index（数独）
否则
pp增加值...
sudoku.tried_value + = 1
solve_by_increasing_value （数独）
结束
否则
pp增加前一个索引...
solve_by_increasing_value_previous_index（数独）
结束
结束
def resolve_by_increasing_index（sudoku）
如果sudoku.sudoku_arr.index（0）.nil吗？
引发SudokuException（sudoku.sudoku_arr.each_slice（9）），数独已解决。
结束
sudoku.index_of_tried_value = sudoku.sudoku_arr.index（0）
sudoku.tried_value = 1
solve_by_increasing_value（sudoku）
结束
defsolve_by_increasing_value_previous_index（sudoku）
＃查找已尝试索引并获取之前的索引）-1]
＃设置上一个数独，以便在需要时可以进一步返回：
＃将尝试过的索引设置回零
sudoku.sudoku_arr [tried_index] = 0
＃设置上一个索引
sudoku.index_of_tried_value = previous_index
＃设置上一个索引
sudoku.tried_value = sudoku.sudoku_arr [previous_index]
pp previous_index
pp sudoku.tried_value
＃TODO由于数独无法解决，如果我们走得太远（即在第一个索引之前），则抛出异常
＃继续照常营业增加上一个索引的值
solve_by_increasing_value（sudoku）
结束
结束
sudoku_solver = SudokuSolver.new（sudoku_str）
sudoku_solver .solve
不幸的是，代码没有回溯到开始。代码显示：
increasing_index ...
increasing_value ...
increasing_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 resolve（char board [81]）{
int i，c;
if（！is_valid（board））返回0；
c = first_empty_cell（board）;
if（c< 0）返回1； / *木板已满* /
for（i = 1; i <= 9; i ++）{
board [c] = i;
if（solve（board））return 1；
}
董事会[c] = 0；
返回0；
}
这是一个递归函数，它在找到的第一个空单元格中尝试从 1 到 9 的每个值（由 first_empty_cell（）返回。如果这些值都不导致解决方案，那么您必须位于搜索树的无效分支上，因此可以将有问题的单元格重置为零（或用于指示未填充单元格的任何值）。
当然，您可以做很多其他事情来使您的软件更快地到达解决方案，但就回溯而言，仅此而已。 p>
附录：
好的，我正在遍历您的代码现在。您似乎将 index_of_tried_value 存储为数独网格的属性。那行不通。您需要将此值存储在求解程序例程的局部变量中，以便在回溯搜索树时可以将其推入堆栈并进行恢复。
This weekend I worked on a Sudoku Solver (Ruby quiz) based on a backtracking algorithm. The sudoku is loaded in an array sudoku_arr of 81 integers (9x9 grid) where 0's are empty spots. There is a valid? method which checks if the sudoku_arr can be a valid sudoku.
The official backtracking algorithm goes like this: try value on next empty spot, check if it is valid sudoku, if not increase value by 1 (upto 9), if valid go on and try first value on next spot, if not increase value of previous 0.
Hereby we have to keep track of the previous array, and that is where I am going wrong and I am not sure if it can be solved. The part of my code below that is not working is the solve_by_increasing_value_previous_index in the SudokuSolver class. Here's the code:
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
Unfortunately the code does not backtrack to the beginning. The code prints:
"increasing_index..." "increasing_value..." "increasing_value..." "increasing_value..." "increasing_value..." "increasing_value..." "increasing_value..." "increasing_value..." "increasing_value..." "Increasing previous index..." 16 2
in a loop till it throws a SystemStackError because the stack level is too deep.
What happens is that the "backtracking" does not go further back than one index. When the solve_by_increasing_value_previous_index goes to the previous index it takes the previous value there. In this case it is a 2, but the 2 is not working and we should therefore decrease it to a 1 and continue, and if that does not work, discard the 2 and make it a 0 again and go back further.
Unfortunately I do not see an easy way to implement this algorithm. (What I thought of was a @too_much_looping variable that gets incremented when the solve_by_increasing_value_previous_index gets called, and after 81 times gets a reset. But this only helps with going back one more time, we cannot loop back to the beginning. \
I hope someone can provide me with some help! General code comments are very welcome too, I have a suspicion this is not 100% idiomatic Ruby.
I haven't yet waded through your code, but the backtracking algorithm boils down to the following:
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;
}
This is a recursive function that tries each value from 1 to 9 in the first empty cell it finds (returned by first_empty_cell()). If none of these values leads to a solution, then you must be on a dead branch of the search tree, so the cell in question can be reset to zero (or whatever value you use to indicate an unfilled cell).
Of course, there are a lot of other things you could do to make your software arrive at a solution faster, but as far as backtracking goes, that's all there is to it.
Addendum:
OK, I'm wading through your code now. It looks like you're storing index_of_tried_value as an attribute of the sudoku grid. That won't work. You need to store this value in a local variable of the solver routine so it can be pushed onto the stack and recovered when you backtrack down the search tree.
这篇关于如何使带有回溯算法的Sudoku求解器返回？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
