Prolog Flow Free solver

Question

I'm completely new to Prolog and working on a homework assignment My program is supposed to solve flow free problem using depth first, I don't need the whole code for it as its what supposed to do but I need to know how to think to solve it or what parts it will contain.

the points look like that:

dot('R',[3,1],[0,3]).

so this 2 points is red and suppose to connect them

so I was thinking that there will be moves to move from 1 point to another and already it works

move([R,C],[NR,NC]):-

    move_right(R,C,NR,NC).

move([R,C],[NR,NC]):-
     move_Left(R,C,NR,NC).

move([R,C],[NR,NC]):-

    move_Up(R,C,NR,NC).

move([R,C],[NR,NC]):-

    move_Down(R,C,NR,NC).

I think now I need to think about the start and the goal so the start is initial grid which contain points with there colors and they all are not connected so I need to take element from start for example red point and find all paths between the 2 points by using moves then for each element I will have multiple paths so what should I do and is there a goal which I will stop for it ?

May be the question is confusing but really don't know how to solve it specially when trying to get useful from backtracking.

All I need to know that I need for example a function to take something and return another something and so on, without its implementation and I will do that

Answer 1

This is some extensive problem.

Here are some quick hints:

Represent a state of the search space as 5x5 tiles, each of which is non-colored or colored in one of the 5 available colours. With SWI-Prolog, you have the fantastic dict datastructure (an associative array), so we can put this to good use instead of messing around with low-level index computations (might be a bit slower, but who cares!)

Our convention is row number first, column number second

  +-----+-----+-----+-----+-----+
  | 0,0 | 0,1 | 0,2 | 0,3 | 0,4 |
  +-----+-----+-----+-----+-----+
  | 1,0 | 1,1 | 1,2 | 1,3 | 1,4 |
  +-----+-----+-----+-----+-----+
  | 2,0 | 2,1 | 2,2 | 2,3 | 2,4 |
  +-----+-----+-----+-----+-----+
  | 3,0 | 3,1 | 3,2 | 3,3 | 3,4 |
  +-----+-----+-----+-----+-----+
  | 4,0 | 4,1 | 4,2 | 4,3 | 4,4 |
  +-----+-----+-----+-----+-----+

Our clean board is then represented as:

Board =
 _{ 0 : _{ 0 : black, 1: black, 2: black, 3: black, 4: black },
    1 : _{ 0 : black, 1: black, 2: black, 3: black, 4: black },
    2 : _{ 0 : black  1: black, 2: black, 3: black, 4: black },
    3 : _{ 0 : black, 1: black, 2: black, 3: black, 4: black },
    4 : _{ 0 : black, 1: black, 2: black, 3: black, 4: black } }.

We also have 5 pens, starting off a one or the end extremity of a path. The pens have the status fesh (they haven't even put to the board), done (a valid path has been traced and the pen won't nove) or ready.

Pens = 
_{ blue   : { row: 0, col: 0, status: fresh },
   red    : { row: 0, col: 3, status: fresh },  
   yellow : { row: 1, col: 3, status: fresh }, 
   orange : { row: 0, col: 4, status: fresh }, 
   green  : { row: 3, col: 4, status: fresh } }. 

A state of the search space is thus given by:

State = [ Board, Pens ].

And now the depth-first search

A predicate move(Board,Pens) is given the State and deterministically:

• Selects a pen that is not done yet (the colors are selected in fixed, but otherwise freely selectable order; a fun way to do that would be to generate a random sequence of the colors determinsitically from the board state).
• Selects a move for that pen that is possible (again, such that on "redo" a next possible move. If no move is possible, fails, causing backtracking.
  • Special case: if the pen is fresh, the only possible move is to color the tile under the pen and set the pen to ready.
• Generates a new board dict from the existing one.
• Checks whether the path for the pen has been completed. In that case, the pen's color is set to done.
• Checks whether all the paths have been completed.
  • In that case, succeeds.
  • Otherwise, calls itself with the new Board and Pens.

Answer 2

Just imagine you have to switch trains, and your time table will tell you to change tracks. For the time table search algorithm, switching trains is just a possible move. We do the same, in our search concerning pens 1,2,3,4 and 5:

  +-----+-----+-----+-----+-----+
  |  1  |     |     |  2  |  4  |
  +-----+-----+-----+-----+-----+
  |     |     |     |  3  |     |
  +-----+-----+-----+-----+-----+
  |     |     |  3  |     |     |
  +-----+-----+-----+-----+-----+
  |     |  2  |  4  |     |  5  |
  +-----+-----+-----+-----+-----+
  |     |  1  |  5  |     |     |
  +-----+-----+-----+-----+-----+

(instead of colors just numbers, the puzzle is then called numberlink)

First there is the search for a single pen, which is the classical path/4 predicate:

path(X, X, L, L) :- !.
path(X, Z, L, R) :-
   next(X, Y),
   \+ member(Y, L),
   path(Y, Z, [Y|L], R).

We can use the already visited list L, to comfort a multi-pen search:

multi([], L, L).
multi([X-Y|M], L, R) :-
   \+ member(X, L),
   path(X, Y, [X|L], H),
   multi(M, H, R).

Seems to work, since the example board is rather small:

?- multi([(0,4)-(1,0),(1,1)-(3,4),(2,2)-(3,3),
       (2,1)-(4,4),(2,0)-(4,1)],[],L), write(L), nl.
[(4,1),(4,0),(3,0),(2,0),(4,4),(4,3),(4,2),(3,2),
(3,1),(2,1),(3,3),(2,3),(2,2),(3,4),(2,4),(1,4),
(1,3),(1,2),(1,1),(1,0),(0,0),(0,1),(0,2),(0,3),(0,4)]

Open Source:

Brute Force Numberlink Solver
https://gist.github.com/jburse/8c387824f82c239cbf02f3ba893bcf02#file-path-pl