Basic logic programming in Scala

Question

I have a fun little problem where I'm presented with a logic clause like so:

Rule 1. A, B and C are unique, and are numbers from 1 to 3 (so every number is used).
Rule 2. B < 2
Rule 3. C > 2

Now (assuming this quick example I just came up with actually validates :P), it's easy to see

A = 2
B = 1
C = 3

But that's a very contrived example.

What about if you have 20 (or ten thousand) rules, and they overlapped. Assume there is valid single answer, and you have access to the rules somehow (be it a list of predicates say).

Is there a nice, general, intuitive solution? I know Prolog could solve it with certain libraries, but my attempts proved futile. I know I could just brute force permutate all numbers in the range, and then manually check they conform to the rules. But that seems pretty lame.

Answer 1

Brute force solution

First I create all possible inputs based on rule 1 which happens to be all permutations:

val all = (1 to 3).permutations

Then I define remaining rules:

val rule2 = (a: Int, b: Int, c: Int) => b < 2
val rule3 = (a: Int, b: Int, c: Int) => c > 2

And I simply filter out solutions that do not match all the rules:

val solutions = all.
  filter(i => rule2(i(0), i(1), i(2))).
  filter(i => rule3(i(0), i(1), i(2))).
  toList

solutions.toList prints one and only valid solution:

List(Vector(2, 1, 3))

Note that because permutations are generated lazily, this implementation isn't really that ineffective (e.g. rule3 is only applied on solutions that passed rule2).

You can use foldLeft() to apply arbitrary number of predicates:

val rules = List(rule2, rule3)

rules.
  foldLeft(all)((solutionsSoFar, rule) => 
    solutionsSoFar.filter(s => 
      rule(s(0), s(1), s(2))
    )
  )

Drools

Have a look at Drools business rule engine. Just put all possible solutions as knowledge base and define rules using nice DSL.

Answer 2

You could be interested by this blog where the author shows in a three-parts article how to do Logic Programming in Scala :

http://ambassadortothecomputers.blogspot.com/feeds/posts/default?alt=rss

Answer 3

This is a job for constraints. There are several constraint solvers for java. My favourite is JaCoP. There is a nice scala DSL for it, so it almost looks like Prolog constraints. Here is the typical SENDMOREMONEY example: http://www.hakank.org/jacop/SendMoreMoney.scala