-1

我有一个 nxn 区域。我想列出在该区域内不相互接触的所有可能的 kxk m 正方形 (k < n) 的位置。我想列出这些 kxk 方块的左上角方块的坐标。你能给我一些关于用 Prolog 实现这个的提示吗？我对这种语言很陌生。我刚刚阅读了一个小教程，但现在我不知道该怎么做。如果他们的角落接触，他们也会接触。

输入和输出应该是这样的：（k：小方块的大小，n：大方块的大小，m：小方块的数量）

>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.
4

1 回答 1

1

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).

after placing, it's easy to display

%%  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] .
...

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.

于 2013-06-07T10:25:00.387 回答