Partial solution for an unsatisfiable query

Help!
1

I’m using the current SWI-Prolog version (but ideally looking for a portable solution).

Consider a simple logicbase such as this:

color(red).
color(green).
color(blue).
color(yellow).
rule1(X) :- color(X), X == red. 
rule2(X) :- color(X), X == green.
rule3(X) :- color(X), X == blue.
complex_rule(A, B) :- rule1(A), rule2(B), rule3(B).

with a query like this:

complex_rule(A, B).

It will fail, because rule2 and rule3 are contradicting each other (as is expected).

If one of the goals is removed however:

complex_rule(A, B) :- rule1(A), rule2(B).%, rule3(B).

the same query will succeed, and bind variables as wanted.

Is there a way to make Prolog remove goals, when the conjunction of all the goals is not satisfiable? In other words, instead of deactivating goals manually, is there some automated exhaustive combinatorial test? Ideally this would work by leveraging Prolog without essentially reimplementing a changed form of satisfiablility test.

Also, is there a way to get a list of conflicting goals?

The purpose is to find solutions that may not be perfect, but satisfy as many constraints/goals as possible(, possibly prioritzing some goals over others).

2

The simple approach is to go with

rule1(A), (rule2(B) ; rule3(B))

But it sounds like you want something more advanced? If so, your requirements need more detail. It wouldn’t be hard to write a meta-interpreter that calls a goal, and if the goal fails ignores the goal. But that isn’t what you want.

For my own work I have written a solver of the sort that tracks and counts the failures of a set of constraints on variables. (If you aren’t familiar, look into CLP and CHR for more sophisticated solvers than basic Prolog.) It would backtrack and try to optimize the total.

The following is top-of-head, and not tested or optimized.

try(Goal, Error) :- call(Goal), Error = 0 ; Error = 1.

check(Error) :- nb_getval(error, Error2), Error <= Error2.
save(Goals, Error) :- nb_setval(error, Error),
       nb_setval(solution, Goals).   % not sure about this line.  assert/retract will work though.

try_system([], 0) :- 
try_system([Goal | Goals], Error) :- 
   try(Goal, Error0), 
   try_system(Goals, Error1),
   Error = Error0 + Error,
   check(Error).

optimize_system(Goals, MaxError, Error) :-
   nb_setval(error, MaxError),
   try_system(Goals, Error),
   save(Goals, Error),
   fail.
optimize_system(Goals, Error) :-
   nb_getval(error, Error),
   nb_getval(solution, Goals).

Finally, you can individually try any of the resultant goals to see if they are satisfied or not.

** this code has bugs. you’ll need to fix them if you want it to work. **

1 Like
3

To give more context: I am writing a solver for a logic game as an exercise (I am beginner and self-learner). You lay out cards on the table, each of which defines a constraint. If you can’t satisfy them all, you want to satisfy all you can.

To achieve that I automatically generate an assertion, such as complex_rule(A, B) :- rule1(A), rule2(B), rule3(B)., and a query, such as complex_rule(A, B), in Delphi (a Pascal like language), and then submit the assertion and query to Prolog.

So in theory I could generate all possible variations of the assertion in Delphi, as necessary, but it would defeat somewhat the point of using Prolog, and I don’t think it would be very efficient to execute that many queries, that have quite some overlap in their requirements.

In other words, the simple approach won’t do.

If a meta-interpreter could solve that, I’d be interested in seeing a simple example (or some more details on how your code works).

4

The program I wrote there, you would just go

Goals = [rule1(A), rule2(B), rule3(B)],
optimize_system(Goals, Error),
findall(Good, (member(Good, Goals), call(Good)), GoodGoals).

It should come back with A = red, B = green, Error = 1.

and GoodGoals = [ rule1(red), rule2(green) ].

Hope that helps. You could also get the failed goals listed, in this case rule3(green). If you want more advanced than that, I’d say it can be done but will require some effort to puzzle out the logic of achieving it.

2 Likes
5

I think I understand it now, but need a little time to process and experiment. If necessary, I’ll write a follow up question.

Thanks for your help!

6

In the following code

try_system([Goal | Goals], Error) :- 
   try(Goal, Error0), 
   try_system(Goals, Error1),
   Error = Error0 + Error,
   check(Error).

shouldn’t it be Error = Error0 + Error1?

I am also a bit confused by the predicate head
optimize_system(Goals, MaxError, Error)
and
optimize_system(Goals, Error).
As far as I can tell optimize_system/3 is never called in the example code in your last post?

Finally, it just dawned onto me that the ordering of rules in a conjunction will matter with this kind of approach.

Say you have a conjuction of rules A, B, C. And B always fails if A is satisfied, then even if B and C are satisfiable it will never test if B is ever satisfiable alone (or satisfiable together with C), but fail directly after A succeeded.
Also, would you ever find out B, C is satisfiable, when A fails? Or did I miss something?

7

It should be

Error is Error0 + Error1

As I said, I just threw the code together in the forum editor, it’s certainly buggy and just usable for understanding the code structure.

You are absolutely right that ordering will matter. In general we’re looking at an exponential runtime but with the ideal ordering it will be linear time.

Regarding the try of A failing, this can happen due to the code.

If B and C are problems because of A, eventually it will try skipping A (error 1) and see if it can get better results without it.

1 Like
8

Yeah, just making sure I understand right, since I am a beginner in Prolog.

I did a quick web search, but could not find what you meant exactly with ideal ordering. Could you provide a link?

9

Ideal ordering is not a technical phrase, it’s just English.

I mean if you have

[A=2, B=4, C=6, D=3, and so on]
and if those answers for A,B,C,D happen to be perfect for all the etc. then the program can very quickly zip through it all just confirming those values are great.

On the other hand, if you reverse that list and only get to your ideal answers as the last 4 goals, the program may be very slow, trying all manner of wrong solutions before finding the right one.

10

Right. I remember reading about an ideal ordering in a Prolog tutorial, something related to DFS, and guessed there was a general (or at least frequently usable) strategy to reorder your queries to achieve that.

Anyways, thanks!