问无clpfd prolog中的sudoku求解器

EN

没有clpfd，您必须编写一个经典的生成和测试搜索。clpfd的好处是约束限制了搜索空间。不过，您可以在不使用clpfd的情况下进行仿真。让我们简化一下任务，这样我就可以说明了。如何找到解这两个方程的X和Y值:X+Y= 10，2*X +Y-1= 15？

首先，对两个方程进行编码：

eq1(X,Y) :- 10 is X + Y.
eq2(X,Y) :- 15 is 2*X + Y - 1.

现在，在求解器谓词中创建搜索空间：

solution(X, Y) :- 
  between(1, 10, X), between(1, 10, Y),
  eq1(X,Y),
  eq2(X,Y).

现在您可以运行它并看到：

?- solution(X,Y).
X = 6,
Y = 4 ;
false.

这比clpfd的效率要低，因为clpfd会注意到一些有助于约束搜索空间的方程：

?- [library(clpfd)].
true.

?- X + Y #= 10, 2*X + Y - 1 #= 15.
2*X+Y#=16,
X+Y#=10.

?- X + Y #= 10, 2*X + Y - 1 #= 15, X in 1..10.
X = 6,
Y = 4.

你看，它已经知道只有一个解决方案，我根本不需要约束Y。太令人印象深刻了！但是您仍然可以不使用clpfd使用Prolog，更糟糕的是。)在本例中，我们可能尝试了所有10x10=100可能的组合来找到这个解决方案。效率不高。但也不是不可能。

那么，对于sudoku，你需要找出哪些约束条件呢？可能是这样的：

unique(Row) :- sort(Row, Sorted), length(Row, Length), length(Sorted, Length).
all_digits(Row) :- forall(between(1,9,X), memberchk(X, Row)).

以此类推。

编辑：组合复杂度估计

假设我们做了一个完全没有原则的搜索:也就是说，我们甚至尝试明显错误的情况，就像所有9的网格一样。我们有9x9=81细胞和9个可能的值(1-9)。这将产生9^81 =一个非常大的数字，在您的一生中不太可能被检查。而这些网格中的大部分都将是无效的排列。

假设限制搜索，使每一行都是1-9的排列。一共有9个！1-9的排列；有了其中的9，你可以将结果乘以9，所以应该有9!^9。这仍然很可怕！通过组合3x3网格约束，clpfd可能会进一步降低效率；我不确定我将如何手动完成这一工作，除非采用半过程的方式，选择3x3网格排列，然后将其中的每一行传递给下一个3x3网格选择。

值得注意的是，经典Prolog程序中的大多数优化都可以归结为要么让生成步骤生成更好的合格候选人，要么使测试步骤更便宜。更明显的实现对于检查更复杂的实现仍然是有用的。

感谢@mat检查我的数学和推荐这篇关于数独组合问题的优秀文章。