问题描述
我有一个 nxn 区域.我想列出在该区域内不相互接触的所有可能的 kxk m 方格 (k
I have a nxn area. And I want to list all of the positions of possible kxk m squares (k < n) which don't touch each other in that area. I want to list the coordinates of the upper-leftmost squares of those kxk squares. Can you give me some hint about implementing this with Prolog? I'm very new to this language. I just read a small tutorial but now I don't know what to do.They are also touching if their corners touch.
输入和输出应该是这样的:(k:小方块的大小，n:大方块的大小，m:小方块的数量)
The input and output should be like this :(k : size of small square,n : size of big square, m: number of small squares)
>func(k,n,m,O).
>func(1,3,2,O).
O =[1-1,1-3];
O =[1-1,2-3];
O =[1-1,3-1];
O =[1-1,3-2];
O =[1-1,3-3];
O =[1-2,3-1];
O =[1-2,3-2];
O =[1-2,3-3];
O =[1-3,2-1];
O =[1-3,3-1];
O =[1-3,3-2];
O =[1-3,3-3];
O =[2-1,2-3];
O =[2-1,3-3];
O =[2-3,3-1];
O =[3-1,3-3];
No.
推荐答案
我发布了一个解决方案，以生成和测试风格展示了可能的 Prolog 编码.您可以在某些位置放置适当的算术，以完成您的作业.
I post a solution showing a possible Prolog coding, in style generate and test. There is some slot where you'll place appropriate arithmetic, just to complete your assignment.
%% placing
place_squares(Big, Small, Squares) :-
place_not_overlapping(Big, Small, [], Squares).
place_not_overlapping(Big, Small, SoFar, Squares) :-
available_position(Big, Small, Position),
\+ overlapping(Small, Position, SoFar),
place_not_overlapping(Big, Small, [Position|SoFar], Squares).
place_not_overlapping(_Big, _Small, Squares, Sorted) :-
sort(Squares, Sorted).
overlapping(Size, R*C, Squares) :-
member(X*Y, Squares),
... % write conditions here
available_position(Big, Small, Row*Col) :-
Range is Big - Small + 1,
between(1, Range, Row),
between(1, Range, Col).
放置后即可轻松展示
%% drawing
draw_squares(Big, Small, Squares) :-
forall(between(1, Big, Row),
(forall(between(1, Big, Col),
draw_point(Row*Col, Small, Squares)),
nl
)).
draw_point(Point, Small, Squares) :-
( nth1(I, Squares, Square),
contained(Point, Square, Small)
) -> write(I) ; write('-').
contained(R*C, A*B, Size) :-
... % place arithmetic here
具有要求尺寸和绘图的结果
the result with requested dimensions, and drawing
?- place_squares(5,2,Q),draw_squares(5,2,Q).
1122-
1122-
3344-
3344-
-----
Q = [1*1, 1*3, 3*1, 3*3] ;
1122-
1122-
33-44
33-44
-----
Q = [1*1, 1*3, 3*1, 3*4] ;
1122-
1122-
33---
3344-
--44-
Q = [1*1, 1*3, 3*1, 4*3] .
...
place_squares/3 输出已排序，以方便显示，也可用于消除对称性，并计算所有解决方案:
the place_squares/3 output is sorted, to ease displaying, and could as well be used to get rid of symmetry, and get a count of all solutions:
9 ?- setof(Q, place_squares(5,2,Q), L), length(L, N).
L = [[], [1*1], [1*1, 1*3], [1*1, 1*3, 3*1], [1*1, 1*3, 3*1, ... * ...], [1*1, 1*3, ... * ...|...], [1*1, ... * ...|...], [... * ...|...], [...|...]|...],
N = 314.
您可以注意到这接受具有备用"空间的板.您可以过滤掉此类不完整的解决方案，以完成您的任务.
You can note that this accepts boards with 'spare' space. You could filter out such incomplete solutions, to complete your task.
这篇关于在 Prolog 中放置正方形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！