3

如何在prolog中获取块的所有元素?大小可以在我的代码中动态改变,因此块大小不同,4x4 = 4 个元素,9x9= 9 个元素等。块被切成正方形,所以在 4x4 中,水平长度是圆形(sqrt(4))= 2 和垂直块的长度是圆形(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_diff 用行检查,转置整个List,all_different 用转置后的列表检查。

但由于数独的动态大小,我无法为这些块编写修复代码。所以有人知道吗?我考虑过 flatten(L) 并使用偏移量来获得正确的块,但这样做似乎很难吗?

请帮我!

4

2 回答 2

2

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

  1. 让我们a = [],...,[]成为一个blocksize桶列表。
  2. 将每一行分成blocksize几部分。
  3. 将第一部分放入第一个桶中,第二部分放入第二个桶中,以此类推。如果您到达最后一个存储桶,请再次从第一个存储桶开始。
  4. a完全展平
  5. 将结果再次划分为blocksizexblocksize个块

在您的示例中:

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]]
于 2011-06-04T16:01:45.253 回答
1

这是一些简单的 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应用于每个分区,将生成所需的“盒子”列表列表。

于 2011-06-04T19:26:33.247 回答