Get unvisited coordinates in Prolog

Question

I am attempting to write a rule in SWI-Prolog for coordinates that have not already been visited. In my current example, the grid is a simple 4x4.

visited(1,1).
visited(2,1).
visited(1,2).

candidate(X,Y) :- \+visited(A,B), X >= 1, X =< 4, Y >= 1, Y =< 4.

When I call candidate(Xcoordinate, Ycoordinate). my goal is to have it print out (in this case):

X = 1, Y = 3 ;
X = 1, Y = 4 ;
X = 2, Y = 2 ;
X = 2, Y = 3 ;
X = 2, Y = 4 ;
X = 3, Y = 1 ;
X = 3, Y = 2 ;
X = 3, Y = 3 ;
  ...etc...

Whenever I attempt to call this though, always get an error about either >=/2 or =</2 that the arguments are not sufficiently instantiated.

What am I doing wrong?

BretC BretC · Accepted Answer · 2016-12-06T14:12:24

You cannot use such operators on variables that have not been instantiated. If I asked you "What is X + 2", how would you answer it?

Your program probably needs a way of knowing how many rows and columns there are, for example...

width(2).
height(2).

row(X) :-
   height(W),
   count_down(W, X).

col(X) :-
   width(W),
   count_down(W, X).

count_down(N, N) :- N > 0.
count_down(W, X) :-
   V is W - 1,
   V > 0,
   count_down(V, X).

Now your program can find a valid row or column number...

3 ?- row(X).
X = 2 ;
X = 1 ;
false.

4 ?- col(X).
X = 2 ;
X = 1 ;
false.

Now you can find unvisited cells as so...

candidate(X, Y) :-
    % Pick a row
    row(X),
    % Pick a column
    col(Y),
    % See if it has not been visited...
    \+ visited(X, Y).

Trace output

2 ?- trace.
true.

[trace] 2 ?- candidate(X, Y).
   Call: (6) candidate(_G3053, _G3054) ? creep
   Call: (7) row(_G3053) ? creep
   Call: (8) width(_G3138) ? creep
   Exit: (8) width(2) ? creep
   Call: (8) count_down(2, _G3053) ? creep
   Call: (9) 2>0 ? creep
   Exit: (9) 2>0 ? creep
   Exit: (8) count_down(2, 2) ? creep
   Exit: (7) row(2) ? creep
   Call: (7) col(_G3054) ? creep
   Call: (8) height(_G3138) ? creep
   Exit: (8) height(2) ? creep
   Call: (8) count_down(2, _G3054) ? creep
   Call: (9) 2>0 ? creep
   Exit: (9) 2>0 ? creep
   Exit: (8) count_down(2, 2) ? creep
   Exit: (7) col(2) ? creep
   Call: (7) visited(2, 2) ? creep
   Fail: (7) visited(2, 2) ? creep
   Redo: (6) candidate(2, 2) ? creep
   Exit: (6) candidate(2, 2) ? creep
X = Y, Y = 2 .

Edit

I should have set rows and cols to 4...

Here are all the answers it finds when I set that...

1 ?- candidate(X, Y).
X = Y, Y = 4 ;
X = 4,
Y = 3 ;
X = 4,
Y = 2 ;
X = 4,
Y = 1 ;
X = 3,
Y = 4 ;
X = Y, Y = 3 ;
X = 3,
Y = 2 ;
X = 3,
Y = 1 ;
X = 2,
Y = 4 ;
X = 2,
Y = 3 ;
X = Y, Y = 2 ;
X = 1,
Y = 4 ;
X = 1,
Y = 3 ;
false.

Get unvisited coordinates in Prolog

1 Answers

Trace output

Edit