Prolog homework problem?

Question

the problem is ; we have a funtion take 3 argument, like; func ( [[0, 0, 0, 1, 0], [0, 1, 1, 1, 0], [0, 0, 1, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0]], (1, 1), X ) the first one is nested list, which is show 5x5 matrix and 1s means it is full, 0 means empty and, the second parameter (1,1) our starting point 1st row 1st column, the 3rd parameter X is ; variable that we will unify with the points that are accessible from the starting point which is (1,1) so if asked;

?- func ( [ [0,0,0,1] [0,0,1,0] [0,0,1,1] [0,0,1,0] ], (1,1), X).

output is:

X = (1, 1);

X = (1, 2);

X = (1, 3);

X = (2, 2);

X = (3, 2);

X = (4, 1);

X = (4, 2);

false.

when we start from (1,1) we can move up, down, left and right; since no left and up movement while on (1,1) look right if empty, write it, look down empty write down, go the (1,2) again, move right or left or up or down, and so on.

here the reason why we didnot write the outputs, (2,4) (4,4) if for example point (2,3) is full and (2,4) is empty we look that can we go point (2,4) one by one, I mean, if left , up and down of them is full, we can't go point (2,4) using this point, since they are full.

I try to explain the problem. If there is a question please write?

I wait for the possible solutions or algorithms;) thanks

Answer 1

My solution: get the textbook, sit at the computer, and figure it out for yourself! Simply labelling something as homework doesn't excuse not doing it yourself.

Answer 2

lastly I done it, here is the code;

%returns the nth element from the list
nth([F|_],1,F).
nth([_|R],N,M) :- N > 1, N1 is N-1, nth(R,N1,M).

%returns true if cell is empty: gets the cell value at (StartRow,StartColumn) and returns whether the value is 0
isempty(Maze,StartRow,StartColumn) :- nth(Maze,StartRow,Line),nth(Line,StartColumn,Y), Y == 0.

%returns the head of the list
head([Elem|_],Elem).

%find accessible returns empty list if not in maze size (1 to N for row and column)
findaccessible(Maze, (StartRow,StartColumn), [], _) :- head(Maze,L),length(L,N), (StartColumn > N ; StartRow > N ; StartColumn < 1 ; StartRow < 1).

%find all empty cells and retain them in X. L retains the current found cells in order to avoid returning to visited positions.
findaccessible(Maze, (StartRow,StartColumn), X, L) :- 
  %if cell is empty, retain position and add it to the list
  isempty(Maze,StartRow,StartColumn) -> (union(L,[(StartRow,StartColumn)],L1),X1 = [(StartRow,StartColumn)], 

  %check right column and if element not visited, find all accessible cells from that point and unify the lists
  SR is StartRow, SC is StartColumn+1,(member((SR,SC),L) -> union(X1,[],X2) ; (findaccessible(Maze, (SR,SC), Tmp1, L1), union(X1,Tmp1,X2))),
  %check down row and if element not visited, find all accessible cells from that point and unify the lists
  SR2 is StartRow+1,SC2 is StartColumn, (member((SR2,SC2),L) -> union(X2,[],X3) ; (findaccessible(Maze, (SR2,SC2), Tmp2, L1), union(X2,Tmp2,X3))),
  %check left column and if element not visited, find all accessible cells from that point and unify the lists

  SR3 is StartRow, SC3 is StartColumn-1, (member((SR3,SC3),L) -> union(X3,[],X4) ; (findaccessible(Maze, (SR3,SC3), Tmp3, L1), union(X3,Tmp3,X4))),
  %check up row and if element not visited, find all accessible cells from that point and unify the lists
  SR4 is StartRow-1, SC4 is StartColumn, (member((SR4,SC4),L) -> union(X4,[],X) ; (findaccessible(Maze, (SR4,SC4), Tmp4, L1), union(X4,Tmp4,X)))) ; X = [].

%lists each result
%if no more results return false
results(_,[]) :- fail.
%return the result or return the rest of the results
results(X,[Head|Rest]) :- X = Head ; results(X,Rest).

%accessible predicate that finds all empty accessible cells and then list each of them
accessible(Maze, (StartRow,StartColumn), X) :- findaccessible(Maze, (StartRow,StartColumn), Lst, []), !, results(X,Lst).

%sample test run
%accessible([[0, 0, 0, 1, 0], [0, 1, 1, 1, 0], [0, 0, 1, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0]], (1, 1), X).