Skip to content
TheChatArchiveThe Chat Archive
Coherecommand-a-03-2025· CohereHugging Face LMArena Human Preference 140K

For some reason, this nonrecursive pathfinding is unsat on this valid example

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Qwenqwen3-30b-a3b’s answer.
  1. User

    For some reason, this nonrecursive pathfinding is unsat on this valid example

  2. Cohere Assistant

    The issue likely stems from the constraints not properly handling the existence of paths or the termination conditions in the non-recursive model. Let's refine the MiniZinc model to ensure it works correctly for valid graphs.

    Below is a corrected and simplified non-recursive MiniZinc model for shortest path finding, focusing on fixing the "unsat" issue.


    🛠️ Corrected Non-Recursive Shortest Path Model

    % Parameters
    int: n; % Number of nodes
    set of int: NODES = 1..n;
    array[NODES, NODES] of int: cost; % Adjacency matrix
    int: source;
    int: target;
    
    % Constants
    int: infinity = max(cost) + 1; % A value larger than any cost
    
    % Decision Variables
    array[NODES] of var 0..infinity: dist; % Distance from source
    
    % Constraints
    constraint dist[source] = 0;
    
    constraint forall(i in NODES where i != source)(
      dist[i] = min(dist[j] + cost[j,i] | j in NODES where cost[j,i] > 0)
    );
    
    % Ensure target is reachable
    constraint dist[target] < infinity;
    
    % Objective: Minimize distance to target
    solve minimize dist[target];
    
    % Output
    output ["Shortest distance to node ", show(target), ": ", show(dist[target])];
    

    🐛 Key Fixes for "unsat" Issues

    1. Infinity Handling:

      • Introduced infinity to represent unreachable nodes.
      • Ensures the model doesn't fail when no path exists (though the example should have a valid path).
    2. Distance Calculation:

      • Used a min expression to correctly compute the shortest distance from neighbors.
    3. Reachability Check:

      • Added a constraint to ensure the target is reachable (dist[target] < infinity).

    📦 Example Data File (data.dzn)

    n = 4;
    source = 1;
    target = 4;
    cost = array2d(1..4, 1..4, [
      [0, 3, 0, 0],
      [0, 0, 2, 0],
      [0, 0, 0, 4],
      [0, 0, 0, 0]
    ]);
    

    🚀 Why This Works

    • Non-Recursive: Uses array constraints and min to compute distances iteratively.
    • Valid Paths: Ensures the target is reachable by checking dist[target] < infinity.
    • Correctness: Mimics Dijkstra's algorithm without recursion or explicit iteration.

    🔍 Debugging Tips if Still "unsat"

    1. Check Graph Connectivity:

      • Ensure there's a path from source to target in the cost matrix.
    2. Validate Costs:

      • Ensure no negative cycles (MiniZinc's min handles non-negative costs correctly).
    3. Simplify Example:

      • Test with a trivial graph (e.g., a linear path) to isolate issues.

    Example trivial graph:

    n = 3;
    source = 1;
    target = 3;
    cost = array2d(1..3, 1..3, [
      [0, 1, 0],
      [0, 0, 1],
      [0, 0, 0]
    ]);
    

    Let me know if the issue persists, and I’ll help debug further!

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