vb.net - 数独求解/生成算法问题

Question

我正在创建一个将在 vb.net 中生成数独谜题的程序，并且由于我这样做的方式，我需要它解决棋盘位置(以特定的随机顺序访问单元格)然后解决再次以相反的顺序。我正在为此使用递归求解器。

这是我正在使用的代码:

Public Function solve(ByRef board() As Integer) As Boolean
    For i = 0 To 80
        If board(order(i)) = 0 Then
            For j = 1 To 9
                board(order(i)) = j
                If check_conflicts(board, order(i)) = False Then
                    If solve(board) = True Then
                        Return True
                    End If

                End If
            Next
            board(order(i)) = 0
            Return False
        End If
    Next

    Return True
End Function

其中 check_conflicts 是一个函数，它确定一个特定的单元分配是否与板直接冲突(因此板被传递并且单元的索引 order(i)也通过了)。当 order 是 0 到 80 的列表时，此函数按预期工作，但是如果 order 是随机打乱的列表，则该函数需要非常长的时间(有时超过一分钟) ) 但通常会得到正确答案。当 order 是从 80 到 0 的数字列表时，该函数不解决任何问题并始终返回 false。

我试过单步执行代码，但使用递归函数很难。不知道有没有人能看出我犯的逻辑错误，谢谢!

Answer 1

This function works as expected when the order is a list of 0 to 80, however if order is a randomly shuffled list then the function takes incredibly long (sometimes upwards of a minute) but usually gets the correct answer.

原因可能是当递归树随着递归深度呈指数增长时，当你逐行处理数字时(而不是随机顺序)，大部分无效排列被提前切掉了。您永远不必在第一行不一致的情况下处理第二行。

When order is a list of numbers from 80 to 0, the function does not solve anything and always returns false.

一些建议:

1) 尝试将 order(i) 替换为 80-i 以确保问题不在 order() 函数中；

2) 每次调用 check_conflicts(board, order(i)) 时，也调用 check_conflicts(inverse(board), 80-order(i)) 和如果它们的结果不相等，则抛出异常。