这个周末我写了一个数独求解器（基于回溯算法）(Ruby quiz)。数独被加载到一个包含81个整数的数组
因此，我们必须跟踪先前的数组，这就是我出错的地方，我不确定是否能够解决。下面是我代码中未能正常工作的部分：
很不幸，代码没有回溯到开头。代码输出：
“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。
sudoku_arr中（9x9网格），其中0表示空位。有一个valid?方法用于检查sudoku_arr是否是有效的数独。
官方回溯算法如下：尝试在下一个空位上放置数字，检查是否是有效的数独，如果不是，则将该位置的值增加1（最大到9），如果有效，则继续并尝试在下一个空位上放置第一个数字，如果无效，则将前一个0的值增加1。因此，我们必须跟踪先前的数组，这就是我出错的地方，我不确定是否能够解决。下面是我代码中未能正常工作的部分：
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。
board[c] = 0;将当前单元格的值恢复为“未填充”，并将零（="未解决"）的值返回到调用solve()的for循环中，其中前一个未填充的单元格正在被考虑。如果前一个单元格的所有测试都失败，则前一个单元格也将重置为零，并尝试为其之前的单元格尝试新值。以此类推... - r3mainer# 在索引处设置先前的值 sudoku.tried_value = sudoku.sudoku_arr[previous_index] + 1，不幸的是，它无法完成数独的最后部分，因为出现了“堆栈层级过深错误”，你能看到解决这个问题的方法吗？PS我接受你的答案，因为你基本上已经回答了它。:-)谢谢。 - user2609980i一样）。（好吧，除非你创建一个由81个元素组成的数组来存储每个单元格的搜索进度，我想。但为什么要费那个劲呢？） - r3mainer