数独解算器很慢，需要更早地考虑约束
Sudoku solver is slow, needs considering constraints earlier
我有一个用 prolog 编写的 NxN 数独求解器。下面的代码适用于 4*4 求解。 （我有一些域信息）但 9x9 的速度很慢。我已经尝试了很多方法来改进创建行功能，它已经在考虑一行中的每个值都应该是唯一的（并且必须包含在它的域中），但是它们没有用。
如果没有任何库，我该如何改进它？
all_distinct(X) :-
sort(X, Sorted),
length(X, OriginalLength),
length(Sorted, SortedLength),
OriginalLength == SortedLength.
good_by_coulmns(Solution) :- length(Solution, Length),
forall((between(1, Length, X), get_column(Solution, X, Y)),
all_distinct(Y)).
get_area(Solution, X, Y, Z) :- length(Solution, Length),
SQRootF is sqrt(Length),
SQRoot is round(SQRootF),
MinCol is SQRoot * (X-1) + 1,
MinRow is SQRoot * (Y-1) + 1,
matrix_block(MinRow, MinCol, SQRoot, SQRoot, Solution, A), flatten2(A,Z).
good_by_areas(Solution) :- length(Solution, Length),
SQRootF is sqrt(Length), SQRoot is round(SQRootF),
forall((between(1, SQRoot, X), between(1, SQRoot, Y), get_area(Solution, X, Y, Z)),
all_distinct(Z)).
createRow(Solution, Domain, Row) :- maplist(member, Row, Domain),
all_distinct(Row),
good_by_coulmns(Solution).%, write(Solution), nl.
tryToSolve(Domains, Solution) :- length(Solution, L), length(Domains, L), !,
maplist(createRow(Solution), Domains, Solution),
good_by_coulmns(Solution),
good_by_areas(Solution).
如果需要，我可以给出缺失的规则，但到目前为止效果很好，所以我们可以将它们用作构建块。
问题更多是关于 A.I 然后是编程。
好吧，您需要对您的数独游戏进行一些限制，以便让它运行得更快。有一个限制，但是它有很多工作，所以我会用数学形式解释和写它，这取决于你如何实现你的代码，你可以很容易地采用它：
思路： 基本思路是，当给你一些数独时，你可以立即填充几个地方，这样程序就不会在很多分支上深入然后失败，然后 backtrack ，相反，如果它在某个更高的节点失败会更好。看下面的图片，如果放置此约束，则可以在 6 个位置阻止 prolog 的方式，并仅在 3 个位置允许它，因为每行有 9 个元素。在许多情况下，它不会探索我标记为 blue.Without 约束的节点，它会一直下降到最后，你会看到它探索了多少额外的分支。
怎么做？ 我们利用数独的特性：
规则：每一行，每一列和每一个网格都有唯一的元素。
算法： 当你得到一些 (sudoku-table) 那么你必须检查前三行 (0,1,2) 是否有在两行中的任何一行中相同的元素。例如，对于第一行中的每个元素，您必须检查该元素是否在第二行或第三行中，如果不在，则转到第二行并尝试查找第二行和第三行中的元素。这里有两种可能性：
你没有匹配：如果前三行没有任何相同的元素然后转到下三行（3,4,5）并在那里找到然后第 (6,7,8) 行。
注意：你只需要检查那些形成网格（3x3矩阵）的线together.For示例行（0,1,2）在一起然后（ 3,4,5)在一起，然后(6,7,8)在一起。
你有一个匹配项：假设你在行 (0,2) 中找到了一个匹配项。因为每一行都可以有一个唯一的元素，所以我们知道这个元素应该在第 1 行，但是我们怎么知道结果行是 1，好吧，我们需要一个公式。看下一个：
数学形式： 你总能通过减法得到结果行。我们在第 0 行和第 2 行进行了匹配。因为这三行在一起，所以我们将它们的行号相加 (0 + 1 + 2 = 3)。由于我们使用变量并且您在 (i = 0 and j = 2) 匹配并且您的总和 = 3
和sum- i - j = 1 so the new element should be in row 1。此公式始终有效：认为您在行号 (i = 4 and j = 5) 处匹配，然后这三个行号的总和
是 4 + 5 + 6 = 15 并减去 15 - 4 -5 = 5. 然而，还有其他方法，但我们使用变量，所以我们需要知道我们必须在哪一行中放置我们在其他中匹配的元素两行。
确定网格： 一旦确定了新元素位于哪一行，下一步就是检查它位于哪个网格，因为每一行都是三个网格（3x3 矩阵）。例如，第 0 行在第一个网格中有元素 (0,1,2)，然后在第二个网格中有 (3,4,5)，然后在第三个网格中有 (6,7,8)。
总共有 (9) 个子网格，从 (0 到 8) 开始。
子网格和行之间的关系：我们只有关于行的信息，所以我们需要找到行和网格数之间的关系。这是一个 NxN 矩阵，所以网格的高度等于网格的宽度（3x3），这意味着每三行一起形成 3 个网格，因为行的长度是 9，网格的长度是 3，所以我们得到 3 个网格高度 3 和长度 3.Example：行 (0,1,2) 形成三个网格，从 0 ,1 ,2 开始，然后是来自另一个网格的行 (4,5,6)：gridnumber(4,5,6 ).
我们可以通过这样做得到他们的网格编号:(假设在第 0 行我们在第 4 列有一个匹配，行号 2 和列号 2 那么我们应该得到网格 0 和网格 1(respt) 因为首先网格是网格 0（列：0 1 2）。
我们使用这个公式得到一维列表中的网格数。
(mod(x,9)/3) + 3*(x/27)
我们现在知道网格 1 和 2 不能有这个元素，因为在每个网格中我们需要一个从 1 到 9 的唯一元素。所以它应该是网格 0 但是如何得到结果网格，嗯，我们可以通过取三个行数的总和（因为行数等于网格数）再次得到它 = 3 并减去其他两个网格的网格数（0 + 1）然后我们得到网格 2。
我们还没有完成，我们需要将这个东西转换为一个索引，因为我们主要使用一维列表。所以这个公式给出了确切的位置：
公式：x = (newRow)*9 + (newGrid)*3 而x就是我们的位置。你可以通过插入 values.Now 来验证这个公式，我们得到了三个可以放置元素的位置。此时你说 list[x] = list[i] 或 list[x+1] = list[i] 或 list[x+2] = list[i].
我有一个用 prolog 编写的 NxN 数独求解器。下面的代码适用于 4*4 求解。 （我有一些域信息）但 9x9 的速度很慢。我已经尝试了很多方法来改进创建行功能，它已经在考虑一行中的每个值都应该是唯一的（并且必须包含在它的域中），但是它们没有用。 如果没有任何库，我该如何改进它？
all_distinct(X) :-
sort(X, Sorted),
length(X, OriginalLength),
length(Sorted, SortedLength),
OriginalLength == SortedLength.
good_by_coulmns(Solution) :- length(Solution, Length),
forall((between(1, Length, X), get_column(Solution, X, Y)),
all_distinct(Y)).
get_area(Solution, X, Y, Z) :- length(Solution, Length),
SQRootF is sqrt(Length),
SQRoot is round(SQRootF),
MinCol is SQRoot * (X-1) + 1,
MinRow is SQRoot * (Y-1) + 1,
matrix_block(MinRow, MinCol, SQRoot, SQRoot, Solution, A), flatten2(A,Z).
good_by_areas(Solution) :- length(Solution, Length),
SQRootF is sqrt(Length), SQRoot is round(SQRootF),
forall((between(1, SQRoot, X), between(1, SQRoot, Y), get_area(Solution, X, Y, Z)),
all_distinct(Z)).
createRow(Solution, Domain, Row) :- maplist(member, Row, Domain),
all_distinct(Row),
good_by_coulmns(Solution).%, write(Solution), nl.
tryToSolve(Domains, Solution) :- length(Solution, L), length(Domains, L), !,
maplist(createRow(Solution), Domains, Solution),
good_by_coulmns(Solution),
good_by_areas(Solution).
如果需要，我可以给出缺失的规则，但到目前为止效果很好，所以我们可以将它们用作构建块。
问题更多是关于 A.I 然后是编程。
好吧，您需要对您的数独游戏进行一些限制，以便让它运行得更快。有一个限制，但是它有很多工作，所以我会用数学形式解释和写它，这取决于你如何实现你的代码，你可以很容易地采用它：
思路： 基本思路是，当给你一些数独时，你可以立即填充几个地方，这样程序就不会在很多分支上深入然后失败，然后 backtrack ，相反，如果它在某个更高的节点失败会更好。看下面的图片，如果放置此约束，则可以在 6 个位置阻止 prolog 的方式，并仅在 3 个位置允许它，因为每行有 9 个元素。在许多情况下，它不会探索我标记为 blue.Without 约束的节点，它会一直下降到最后，你会看到它探索了多少额外的分支。
怎么做？ 我们利用数独的特性：
规则：每一行，每一列和每一个网格都有唯一的元素。
算法： 当你得到一些 (sudoku-table) 那么你必须检查前三行 (0,1,2) 是否有在两行中的任何一行中相同的元素。例如，对于第一行中的每个元素，您必须检查该元素是否在第二行或第三行中，如果不在，则转到第二行并尝试查找第二行和第三行中的元素。这里有两种可能性：
你没有匹配：如果前三行没有任何相同的元素然后转到下三行（3,4,5）并在那里找到然后第 (6,7,8) 行。
注意：你只需要检查那些形成网格（3x3矩阵）的线together.For示例行（0,1,2）在一起然后（ 3,4,5)在一起，然后(6,7,8)在一起。
你有一个匹配项：假设你在行 (0,2) 中找到了一个匹配项。因为每一行都可以有一个唯一的元素，所以我们知道这个元素应该在第 1 行，但是我们怎么知道结果行是 1，好吧，我们需要一个公式。看下一个：
数学形式： 你总能通过减法得到结果行。我们在第 0 行和第 2 行进行了匹配。因为这三行在一起，所以我们将它们的行号相加 (0 + 1 + 2 = 3)。由于我们使用变量并且您在 (i = 0 and j = 2) 匹配并且您的总和 = 3
和sum- i - j = 1 so the new element should be in row 1。此公式始终有效：认为您在行号 (i = 4 and j = 5) 处匹配，然后这三个行号的总和
是 4 + 5 + 6 = 15 并减去 15 - 4 -5 = 5. 然而，还有其他方法，但我们使用变量，所以我们需要知道我们必须在哪一行中放置我们在其他中匹配的元素两行。
确定网格： 一旦确定了新元素位于哪一行，下一步就是检查它位于哪个网格，因为每一行都是三个网格（3x3 矩阵）。例如，第 0 行在第一个网格中有元素 (0,1,2)，然后在第二个网格中有 (3,4,5)，然后在第三个网格中有 (6,7,8)。
总共有 (9) 个子网格，从 (0 到 8) 开始。
子网格和行之间的关系：我们只有关于行的信息，所以我们需要找到行和网格数之间的关系。这是一个 NxN 矩阵，所以网格的高度等于网格的宽度（3x3），这意味着每三行一起形成 3 个网格，因为行的长度是 9，网格的长度是 3，所以我们得到 3 个网格高度 3 和长度 3.Example：行 (0,1,2) 形成三个网格，从 0 ,1 ,2 开始，然后是来自另一个网格的行 (4,5,6)：gridnumber(4,5,6 ).
我们可以通过这样做得到他们的网格编号:(假设在第 0 行我们在第 4 列有一个匹配，行号 2 和列号 2 那么我们应该得到网格 0 和网格 1(respt) 因为首先网格是网格 0（列：0 1 2）。
我们使用这个公式得到一维列表中的网格数。
(mod(x,9)/3) + 3*(x/27)
我们现在知道网格 1 和 2 不能有这个元素，因为在每个网格中我们需要一个从 1 到 9 的唯一元素。所以它应该是网格 0 但是如何得到结果网格，嗯，我们可以通过取三个行数的总和（因为行数等于网格数）再次得到它 = 3 并减去其他两个网格的网格数（0 + 1）然后我们得到网格 2。
我们还没有完成，我们需要将这个东西转换为一个索引，因为我们主要使用一维列表。所以这个公式给出了确切的位置：
公式：x = (newRow)*9 + (newGrid)*3 而x就是我们的位置。你可以通过插入 values.Now 来验证这个公式，我们得到了三个可以放置元素的位置。此时你说 list[x] = list[i] 或 list[x+1] = list[i] 或 list[x+2] = list[i].