Prolog数独块算法

Question

如何在Prolog中获取块中的所有元素？在我的代码中，大小可以动态更改，因此块大小不同，4x4 = 4个元素，9x9 = 9个元素等等。块被切割成正方形，因此在4x4中，水平长度为round(sqrt(4))=2，垂直长度为round(sqrt(4))=2。在9x9中...sqrt(9)...因此块的高度和宽度为3。我需要一个有效的算法来获取元素。

我的数独列表是这样构建的：

L=[ [4,3,1,2], [2,1,4,3], [3,4,2,1], [1,2,3,4] ],

因此，这是一个列表，其中包含数独中每行的列表。检查行和列没有问题，使用all_different检查行，转置整个列表，使用转置列表检查all_different。

但是由于数独的动态大小，我无法编写适用于块的固定代码。有没有任何想法？我考虑了flatten（L）并使用偏移量来获取正确的块，但是这种方法似乎非常困难？

请帮助我！

- viktor

---

你所说的“block”，是指整个9x9标准数独划分成的九个3x3小方块之一吗？ - Anko

Answer 1

一个可能的解决方案如下（假设您有大小为 blocksize x blocksize 的块，标准数独中所有数字都相等，可以调整以匹配其他布局）：

1. 让a = [],...,[]成为blocksize个桶的列表。
2. 将每一行分成blocksize部分。
3. 将第一部分放入第一个桶中，第二部分放入第二个桶中，以此类推。如果到达最后一个桶，请重新从第一个桶开始。
4. 完全展开a。
5. 再次将结果分割为blocksize x blocksize的块。

在您的示例中：

L=[ [4,3,1,2], [2,1,4,3], [3,4,2,1], [1,2,3,4] ]
Partitions => [[4,3] [1,2] [2,1] [4,3] [3,4] [2,1] [1,2] [3,4]]
Bucketed => [[4,3] [2,1] [3,4] [1,2]] [[1,2] [4,3] [2,1] [3,4]]
Flattened => [4,3,2,1,3,4,1,2,1,2,4,3,2,1,3,4]
Partitioned => [4,3,2,1], [3,4,1,2], [1,2,4,3], [2,1,3,4]]

- Howard

Answer 2

这里有一些简单的Prolog代码，可以将以列表嵌套列表的形式表示的矩阵转置。其思想是通过从每个现有行中取出头部来创建一个新的“第一行”，然后在“剩余”尾部的列表上进行递归操作。

transpose([[ ]|_],[ ]) :- !.
transpose(A,[H|T]) :-
    decap_List(A,H,B),
    transpose(B,T).

decap_List([ ],[ ],[ ]).
decap_List([[H|T]|Rows],[H|Hs],[T|Ts]) :-
    decap_List(Rows,Hs,Ts).

例如：

?- transpose([[1,2,3],[4,5,6],[7,8,9]],X).

X = [[1, 4, 7], [2, 5, 8], [3, 6, 9]] 

然而，对于一个大小为K²xK²的通用数独矩阵，您还需要在矩阵中以KxK的大小铺设每个“盒子”中的“所有不同”的条目。使用与之前相同的设计，您还需要一个谓词来重新打包数独矩阵成为“盒子”列表的列表。

要做到这一点，只需要进一步的谓词将矩阵分成每组K行。

part_K_rows([ ],_,[ ]) :- !.
part_K_rows(A,K,[H|T]) :-
    get_K_rows(A,K,H,B),
    part_K_rows(B,K,T).

get_K_rows(A,0,[ ],A) :- !.
get_K_rows([H|T],K,[H|Z],B),
    J is K-1,
    get_K_rows(T,J,Z,B).

将part_K_rows/3应用于原数独矩阵，然后对每个结果行分区进行转置，并对它们中的每个应用part_K_rows/3，即可生成所需的“盒子”列表。

- hardmath