1

I'm trying to implement a sudoku-like puzzle solver that involves groups in prolog, and where one of the rules is that the same value cannot be repeated in the same group. My code 'works', but it ends up 'splitting into two branches':

:- use_module(library(clpfd)).

solve(Input) :-
    append(Input, Items),
    bagof(V, member(G-V, Items), Group),
    length(Group, Len),
    Group ins 1..Len,
    all_distinct(Group).

input(I) :- I = [
    [a-1, b-_],
    [a-_, b-1]
].

?- input(I), solve(I)
I = [[a-1, b-_], [a-2, b-1]] ;
I = [[a-1, b-2], [a-_, b-1]].

Ideally with this example I'd want it to return a single I value with all values filled, but I'm at a loss as to what's even happening. Why is it branching like this? What should I try to do so it doesn't branch?

Edit: I've changed all values to use 'X-Y' format. Also, here's a more complex example of what I want to achieve:

input(I) :- I = [[a-1, b-_, b-2],
                 [a-_, c-_, b-1],
                 [a-2, a-4, b-3]].

?- input(I), solve(I).
I = [[a-1, b-4, b-2],
     [a-3, c-1, b-1],
     [a-2, a-4, b-3]].

The current algorithm correctly solves for each group, but in a different branch each.

João Haas
  • 1,883
  • 13
  • 13

2 Answers2

3

This should do the trick:

input(I) :- I = [
    [a-1, b-_],
    [a-_, b-1]
].
input(I) :- I = [[a-1, b-_, b-2],
                 [a-_, c-_, b-1],
                 [a-2, a-4, b-3]].

solve(Input) :-
    append(Input, Items),
    findall(ID, member(ID-_, Items), IDs),
    \+ (member(ID, IDs), \+ ground(ID), throw(error(instatiation_error,solve/1))),
    bagof(
        ID-Group-Len,
        (   member(ID, IDs),
            bagof(V, member(ID-V, Items), Group),
            length(Group, Len)
        ),
        Groups
    ),
    maplist(constraints, Groups).

constraints(_-Group-Len) :-
    Group ins 1..Len,
    all_distinct(Group).

But if the ID isn't ground (contains a variable) then it will throw an exception.

notoria
  • 2,053
  • 1
  • 4
  • 15
  • Aha! This is exactly what I wanted to do, some way to 'unify' the different results in that bagof. Guess the trick is just wrapping it into another bagof haha. Also, what you you mean by 'if the ID isn't ground'? You mean if it is undefined? – João Haas Dec 12 '22 at 15:15
  • Produce an instantiation error if it does not work. – false Dec 12 '22 at 15:34
2

First, whenever you are loading a Prolog file, read the warnings listed. Practically all systems (Scryer, SICStus, SWI) warn you about a singleton variable G. And in fact, that is your direct problem:

?- input(I), append(I,Items), bagof(V, member((G, V), Items), Group).
   I = [[(a,1),(b,_A)],[(a,_B),(b,1)]],
   Items = [(a,1),(b,_A),(a,_B),(b,1)],
   G = a, Group = [1,_B]
;  I = [[(a,1),(b,_A)],[(a,_B),(b,1)]],
   Items = [(a,1),(b,_A),(a,_B),(b,1)],
   G = b, Group = [_A,1].

So bagof/3 has two answers, once for G = a and the other for G = b. But you are not interested in this variable. So instead, quantify that variable accordingly.

?- input(I), append(I,Items), bagof(V, G^member((G, V), Items), Group).
   I = [[(a,1),(b,_A)],[(a,_B),(b,1)]],
   Items = [(a,1),(b,_A),(a,_B),(b,1)],
   Group = [1,_A,_B,1].

In general, there are four remarks:

  1. Mixing constraints and bagof/3 or for that matter setof/3 does not work in general. In your case you had quite some luck because at the point in time of executing bagof, there wasn't any constraint yet. But generally, prefer direct definitions like maplist/3 instead. In fact with library(lambda) you could write
..., maplist(\ (_,V)^V^true, Items, Group), ...

  1. It is more common in Prolog to use a minus for pairs than this comma. Thus [a-1,b-2] in place of [(a,1),(b,2)].

  2. In programs using finite domain constrains the part responsible for modeling (the core relation) is often separated from the actual search part (the labeling part). Currently, there is no labeling part in your program at all. So you cannot be sure if what you got is true or not.

  3. On the one hand you want that all second arguments of your pairs are distinct, but then you are stating that two of them should be 1. This cannot be true.

false
  • 10,264
  • 13
  • 101
  • 209
  • I think you didn't understood my question. I *want* to group items based on wether G is 'a' or 'b', that's the whole idea of the algorithm. The idea is that I can fill the empty values with the values missing from each group, (where a 'group' is represented by the first atom for each value), but I want this to result in a single result. I've updated the question to add a more meaningful example. – João Haas Dec 12 '22 at 13:47
  • I've also changed the values to use `X-Y` syntax, since I agree that's better – João Haas Dec 12 '22 at 13:55
  • What do you want to express with `all_distinct/1` when you say `... [a-3, c-1, b-1] ...`? – false Dec 12 '22 at 13:59
  • *... the same value cannot be repeated in the same group ...* what do you mean here by value, and what by group, given above example? – false Dec 12 '22 at 14:09
  • I'm not calling the `all_distinct` on each line, that's what the `bagof` is being used for. `bagof` is grouping items by their `G`, and then ensuring the items of each group go from 1 to the size of the group. Since there's only 1 missing value for each group, calling `all_distinct` restricts the value to a single result, which is why the algorithm is currently working. So, in my example, `all_distinct` is called on the 'a' group with values `[1, 1..4, 3, 4]`, which allows prolog to set the 2nd variable correctly. The only issue is that it branches the possible solutions, which is weird. – João Haas Dec 12 '22 at 14:14
  • You really need a better description of what you want, sorry. – false Dec 12 '22 at 14:36
  • I don't think what I'm trying to do is that complex. There's a matrix where each item has a value and a group. Values go from 1 to the size of the group, and there can't be repeated values in the same group. The problem tries to find what some non-initialized values will end up as. – João Haas Dec 12 '22 at 15:13
  • @false (from discussing on a Prolog Discord), what they wanted was to get the pairs out of the original sublists and group by the first item in the pair, so all the `a-_` are one group, all the `b-_` are another group. And then apply constraints to the second item in the pairs, within each group, so `a-[1, _]` constrained so the numbers must be `ins 1..GroupALen` And `b-[_, 2]` constrained to be `ins 1..GroupBLen`. And they were hitting a problem where findall or bagof (unclear) was making copies of the variables, so constraining the grouped variables did not bind the original Input variables. – TessellatingHeckler Dec 12 '22 at 15:29
  • 1
    @TessellatingHeckler: Thanks, too much disco these days. Be it -rd or -urse – false Dec 12 '22 at 15:33