Prolog - Searching within a list of lists - how to do it

Posted on 2004-11-13
Last Modified: 2008-02-01

I'm working on a program that lacks this one thing to be complete. :(
It's about a simple robot that cleans a room; the room is represented through a 10x10 map divided into squares, each square having it's own unique pair of x,y coordinates. I'm representing the coordinates via a list that contains two elements: [Xcoord,Ycoord], and a path through the room is represented via a sequence of squares in a list: [[0,0],[0,1][1,1]], for example. The robot doesn't move diagonally.
Now I need to find out how to get to a certain square being on another square; for example, I'm on [5,4] and I need to get to [0,0] - I need a predicate that returns me a list with a possible path through these squares, and I just can't do it :((( The closest I got didn't even work correctly. :(((( I know I could just subtract/sum the coordinates of the original position to get the result I want, but that's not what I need :(

Can someone please post some ideas, links and/or code examples on this?

Thanx in advance :)
Question by:bass20
    LVL 4

    Expert Comment

    Might be that you find the answer that here:

    I've had use of this site before when it came to mathematical problems, maybe it will help you as well?
    Good luck,
    LVL 1

    Author Comment

    No Prolog there...
    LVL 3

    Assisted Solution

    lets say that your command would work like this

    the best way to get the correct path would be to move horizontaly at first till you reach the spot and then vertically towards it (or vice versa if you like)...
    so you could create a recursive command that gives u all the horizontal coordinates and then the vertical (you may have to rearrange your coordinates list to
    more lists). I'll post the code a.s.a.p.
    LVL 2

    Assisted Solution

    What you want is a recursive algorithm,
    This is what it would do:

    mark current location as "been here"
    if can go north go north if at destination return true
    if can go south go south if at destination return true
    if can go east go east if at destination return true
    if can go west go west if at destination return true
    if no move available return false
    unmark location

    if you want I'll find the algorithm, I have it somewhere

    Because you want a list of every posible solution you will need to find the number of possible solutions and call this recursive function that many times.

    However you will get list of moves that are unnecessary such as
    east, north, east, south
    east, east
    east, south, east, north

    (all bring robot to same location)
    Is this what you want?

    LVL 3

    Accepted Solution

    take a look at this one: it's a bit different than your type of map&pathfinding but it'll give you some ideas...

    you can also see if u can grasp anything out of this sourcecode i found in a book....
    :- [pmeters].
    graph :-

    path([H|T], Y, [H|T]) :-
          H = Y.

    path([H|T], Y, Path) :-
          \+ member(Next,[H|T]),
          path([Next,H|T],Y, Path).

    adjacent(H,Next) :- d(H,Next);d(Next,H).

    If you combine this algorithm with the horizontal/vertical movement you can get it to work pretty easily...

    You may also want to check this link:
    Or this one:


    Featured Post

    Highfive + Dolby Voice = No More Audio Complaints!

    Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

    Join & Write a Comment

    Suggested Solutions

    One of the biggest challenges facing freelancers is balancing multiple projects and deadlines. Organizational skills and time management are key to keeping up with projects and staying on track. Luckily, we’ve curated seven tools to help you focus o…
    Whether you believe the “gig economy,” as it has been dubbed, is the next big economic paradigm shift ( or an overstated trend (…
    Where to go on the main page to find the job listings. How to apply to a job that you are interested in from the list that is featured on our Careers page.
    Want to pick and choose which updates you receive? Feel free to check out this quick video on how to manage your email notifications.

    734 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    24 Experts available now in Live!

    Get 1:1 Help Now