Skip to content
TheChatArchiveThe Chat Archive
Metallama-4-maverick-03-26-experimental· MetaHugging Face LMArena Human Preference 140K

Given a list of facts, edge(a,b) like that, how to write a simple path search algorithm…

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with o3-2025-04-16’s answer.
  1. User

    Given a list of facts, edge(a,b) like that, how to write a simple path search algorithm in prolog?

  2. Meta Assistant

    A classic Prolog question!

    Given a list of facts like edge(a, b), you want to write a simple path search algorithm in Prolog. I'll guide you through it.

    The Problem

    You have a graph represented by a set of edge/2 facts, where edge(A, B) means there's a direct connection (edge) from node A to node B. Your goal is to find a path from a starting node (Start) to a target node (End).

    The Solution

    Here's the simple, yet powerful, Prolog code for a path search algorithm:

    % path(Start, End, Path)
    path(Start, End, [Start, End]) :-
        edge(Start, End).
    path(Start, End, [Start | Rest]) :-
        edge(Start, Intermediate),
        path(Intermediate, End, Rest).
    

    Let's break it down:

    Clause 1: Direct Edge

    path(Start, End, [Start, End]) :-
        edge(Start, End).
    

    If there's a direct edge from Start to End, we've found a path of length 2: [Start, End]. Easy!

    Clause 2: Recursive Step

    path(Start, End, [Start | Rest]) :-
        edge(Start, Intermediate),
        path(Intermediate, End, Rest).
    

    If there's no direct edge, we:

    1. Find an Intermediate node connected to Start via edge(Start, Intermediate).
    2. Recursively search for a path from Intermediate to End, yielding Rest of the path.
    3. If we find such a path, prepend Start to Rest, forming the complete path: [Start | Rest].

    How it works

    1. Prolog tries Clause 1: if edge(Start, End) is true, it returns a path of length 2.
    2. If not, Prolog tries Clause 2:
      • edge(Start, Intermediate) binds Intermediate to a node connected to Start.
      • The recursive call path(Intermediate, End, Rest) searches for a path from Intermediate to End.
      • If a path is found (Rest), Prolog prepends Start to it, forming the final path.

    Example Usage

    Suppose you have these facts:

    edge(a, b).
    edge(b, c).
    edge(c, d).
    edge(a, e).
    edge(e, d).
    

    Query:

    ?- path(a, d, Path).
    

    Prolog will respond with:

    Path = [a, b, c, d] ;
    Path = [a, e, d].
    

    Two paths from a to d are found!

    Tips & Variations

    • To avoid cycles, add a \+ member(Intermediate, Rest) check in Clause 2, ensuring we don't revisit nodes:
    path(Start, End, [Start | Rest]) :-
        edge(Start, Intermediate),
        \+ member(Intermediate, Rest),
        path(Intermediate, End, Rest).
    
    • For undirected graphs, add edge(B, A) for each edge(A, B) fact, or modify the predicate to edge(A, B) :- edge(A, B) ; edge(B, A).
    • To find all paths, use findall/3: findall(Path, path(a, d, Path), AllPaths).
    • For shortest path, you'll need more advanced techniques, like Dijkstra's algorithm or breadth-first search (BFS).

    Now, go ahead and experiment with this simple yet elegant Prolog path search algorithm!

    Happy Prologging!

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.