Rotate a matrix in Prolog

Question

How can I rotate a 4 x 4 matrix about its center point in Prolog ? I can simply rearrange the elements in case of 4 x 4 matrix but how to do this for a general case like N x N ?

Answer 1

What you want is not quite matrix transposition... but almost!

:- use_module(library(clpfd)).

matrix_rotated(Xss, Zss) :-
   transpose(Xss, Yss),
   maplist(reverse, Yss, Zss).

Sample query:

?- matrix_rotated([[a1,a2,a3,a4],
                   [b1,b2,b3,b4],
                   [c1,c2,c3,c4]], Xss).
Xss = [[c1,b1,a1],
       [c2,b2,a2],
       [c3,b3,a3],
       [c4,b4,a4]].

Answer 2

Someone is wrong on the internet, so duty calls. We must obey Cunningham's Law, after all.

This answer makes good use of library(clpfd) as found in SWI-Prolog.

:- use_module(library(clpfd)).

rotate_clockwise(Matrix, N, Rotated) :-
    N_mod_4 #= N mod 4,
    rotate_clockwise_(N_mod_4, Matrix, Rotated).

rotate_clockwise_(0, M, M).
rotate_clockwise_(1, M, R) :-
    transpose(M, R0),
    maplist(reverse, R0, R).
rotate_clockwise_(2, M, R) :-
    reverse(M, R0),
    maplist(reverse, R0, R).
rotate_clockwise_(3, M, R) :-
    transpose(M, R0),
    reverse(R0, R).

You can rotate a rectangular matrix by flipping it twice (try it out with a book or something). Depending on the two axes along which you flip, you get one of the 3 non-trivial rotations: if we agree that "one rotation" is 90 degrees clockwise, then you can rotate 0, 1, 2, or 3 times. In the code above:

• flip along horizontal axis is reverse
• flip along vertical axis is maplist(reverse)
• flip along the top-left-lower-right axis is transpose

As to why not just define rotating once 90 degrees clockwise and then rotate multiple times: well, it is actually more code! With the definition above, no matter what valid arguments we give to rotate_clockwise/3, it does the right rotation, doesn't do unnecessary flips, and keeps the caller code short.

?- rotate_clockwise([[a,b,c],[d,e,f]], -1, R). % once counter-clockwise
R = [[c, f], [b, e], [a, d]].

?- rotate_clockwise([[a,b,c],[d,e,f]], 2, R). % 180 degrees
R = [[f, e, d], [c, b, a]].

?- rotate_clockwise([[a,b,c],[d,e,f]], 168, R). % rotate once each hour, for a week
R = [[a, b, c], [d, e, f]].

?- rotate_clockwise([[a,b,c],[d,e,f]], N, R). % enumerate all possibilities
R = [[a, b, c], [d, e, f]],
N mod 4#=0 ;
R = [[d, a], [e, b], [f, c]],
N mod 4#=1 ;
R = [[f, e, d], [c, b, a]],
N mod 4#=2 ;
R = [[c, f], [b, e], [a, d]],
N mod 4#=3.

?- Matrix = [[a],[b]],
   rotate_clockwise(Matrix, -1, R),
   rotate_clockwise(Matrix, 3, R). % those two mean the same
Matrix = [[a], [b]],
R = [[a, b]].

Answer 3

as noted, transpose/2 isn't the right solution. I've coded something (maybe a bit too much general), that allows to specify the amount of rotation in term of number of cells to shift to right. Shift defaults to 1, but then I noted that to get 90° rotations, the shift is decreasing while passing to inner frames. Passing an anonymous variable to matrix_rotate/3 has the effect of using the current inner frame size. Then, it rotates 90° clockwise.

/** <module> matrix_rotate
 *
 *  answer to http://stackoverflow.com/questions/35594027/rotate-a-matrix-in-prolog
 *  --------
 *
 *  source file /home/carlo/prolog/matrix_rotate.pl
 *  created at mer feb 24 16:43:50 2016
 *
 *  @author carlo
 *  @version 0.9.9
 *  @copyright carlo
 *  @license LGPL v2.1
 */

:- module(matrix_rotate,
    [matrix_rotate/2
    ,matrix_rotate/3
    ,matrix_allocate/4
    ,matrix_row_col_element/4
    ,rowcol/3
    ]).

:- meta_predicate matrix_allocate(3, +,+,-).

matrix_allocate(Pred, NRows, NCols, Mat) :-
    bagof(Vs, Row^(
        between(1, NRows, Row),
        bagof(C, Col^(between(1, NCols, Col), call(Pred, Row, Col, C)), Vs)
    ), Mat).

empty(_R,_C,_).
rowcol(R, C, (R,C)).

matrix_rotate(Mat, Rot) :-
    matrix_rotate(Mat, 1, Rot).
matrix_rotate(Mat, Shift, Rot) :-
    matrix_is_square(Mat, Size),
    matrix_allocate(empty, Size, Size, Rot),
    frames_shift(Mat, Shift, 1, Rot),
    (   Size mod 2 =:= 1
    ->  Cen is Size // 2 + 1,
        matrix_row_col_element(Mat, Cen, Cen, E),
        matrix_row_col_element(Rot, Cen, Cen, E)
    ;   true
    ).

frames_shift(Mat, Shift, Frame, Rot) :-
    length(Mat, Size),
    Frame =< Size // 2,
    (   integer(Shift)
    ->  ActualShift = Shift
    ;   ActualShift is Size - (Frame - 1)*2 - 1
    ),
    frame(Mat, Frame, L),
    shift_right(L, ActualShift, S),
    frame(Rot, Frame, S),
    F is Frame+1,
    !, frames_shift(Mat, Shift, F, Rot).
frames_shift(_Mat, _Shift, _Frame, _Rot).

matrix_is_square(Mat, Size) :-
    length(Mat, Size),
    forall(member(Row, Mat), length(Row, Size)).

matrix_row_col_element(Mat, Row, Col, El) :-
    nth1(Row, Mat, Cells),
    nth1(Col, Cells, El).

shift_right(List, Shift, Shifted) :-
    length(Post, Shift),
    append(Pre, Post, List),
    append(Post, Pre, Shifted).

frame(Mat, N, Frame) :-
    length(Mat, S),
    T is N, B is S-N+1,
    L is N, R is S-N+1,
    matrix_range_elements(Mat, T,T, L,R-1, Top),
    matrix_range_elements(Mat, T,B-1, R,R, Right),
    matrix_range_elements(Mat, B,B, R,L+1, Bottom),
    matrix_range_elements(Mat, B,T+1, L,L, Left),
    append([Top, Right, Bottom, Left], Frame).

matrix_range_elements(Mat, RStart, RStop, CStart, CStop, Elems) :-
    bagof(E, matrix_element_between(Mat, RStart, RStop, CStart, CStop, E), Elems).

matrix_element_between(Mat, RStart, RStop, CStart, CStop, Elem) :-
    signed_between(RStart, RStop, R),
    signed_between(CStart, CStop, C),
    matrix_row_col_element(Mat, R, C, Elem).

signed_between(Start, Stop, I) :-
    A is Start, B is Stop,
    ( B < A -> between(B, A, N), I is A+B-N ; between(A, B, I) ).

This snippets highlights some general pattern useful while processing matrices as list of lists. And some of the difficulties, too...

Example usage:

?- matrix_allocate(rowcol,4,4,M),matrix_rotate(M,_,R),maplist(writeln,R).
[(4,1),(3,1),(2,1),(1,1)]
[(4,2),(3,2),(2,2),(1,2)]
[(4,3),(3,3),(2,3),(1,3)]
[(4,4),(3,4),(2,4),(1,4)]
M = [[(1, 1),  (1, 2),  (1, 3),  (1, 4)], [(2, 1),  (2, 2),  (2, 3),  (2, 4)], [(3, 1),  (3, 2),  (3, 3),  (3, 4)], [(4, 1),  (4, 2),  (4, 3),  (4, 4)]],
R = [[(4, 1),  (3, 1),  (2, 1),  (1, 1)], [(4, 2),  (3, 2),  (2, 2),  (1, 2)], [(4, 3),  (3, 3),  (2, 3),  (1, 3)], [(4, 4),  (3, 4),  (2, 4),  (1, 4)]].

?- matrix_allocate(rowcol,3,3,M),matrix_rotate(M,_,R),maplist(writeln,R).
[(3,1),(2,1),(1,1)]
[(3,2),(2,2),(1,2)]
[(3,3),(2,3),(1,3)]
M = [[(1, 1),  (1, 2),  (1, 3)], [(2, 1),  (2, 2),  (2, 3)], [(3, 1),  (3, 2),  (3, 3)]],
R = [[(3, 1),  (2, 1),  (1, 1)], [(3, 2),  (2, 2),  (1, 2)], [(3, 3),  (2, 3),  (1, 3)]].