<< Back to previous view

[LOGIC-162] FD logic doesn't always return all solutions Created: 20/Oct/14  Updated: 21/Oct/14

Status: Open
Project: core.logic
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Viktar Basharymau Assignee: David Nolen
Resolution: Unresolved Votes: 0
Labels: finite-domains
Environment:

org.clojure/core.logic 0.8.8



 Description   

Given the following code

(run* [x11 x12 x13 
       x21 x22     x24
       x31     x33 x34
           x42 x43 x44]
      (fd/in x11 x12 x13 x21 x22 x24 x31 x33 x34 x42 x43 x44 (fd/interval 1 9))
      (fd/eq (= (+ x11 (/ x12 x13))   5)
             (= (+ x21 (/ x22   2)) x24)
             (= (+ x31 (/   6 x33)) x34)
             (= (+   4 (/ x42 x43)) x44)
             (= (+ x11 (/ x21 x31))   4)
             (= (* x12 (/ x22   6)) x42)
             (= (+ x13 (-   2 x33)) x43)
             (= (+ (-  5 x24) x34)  x44)))

I have {{([1 4 1 3 6 6 1 1 7 4 2 6] [2 6 2 4 6 7 2 1 8 6 3 6])}} as a result.

However, as soon as I change (fd/interval 1 9) to (fd/interval 0 9), the result becomes an empty sequence. However, I expect it to include at least the two aforementioned solutions.



 Comments   
Comment by David Nolen [ 21/Oct/14 4:34 AM ]

It would help if you could confirm that the issue is present without using fd/eq - which is just macro sugar. Writing out the long form is tedious but it will help isolate the issue. Thanks.

Comment by Viktar Basharymau [ 21/Oct/14 8:08 AM ]

I actually suspect that the bug is in `fd/eq`. Here is a smaller test case:

(run* [q]
      (fd/in q (fd/interval 1 2))
      (fd/eq (= (/ q q) 1)))

It returns `(1 2)` as expected, but as soon as I change `fd/interval` to `0 2`, it returns an empty seq.





[LOGIC-52] Bug in finite domains (+fd, infd) Created: 10/Sep/12  Updated: 28/Jul/13  Resolved: 26/Oct/12

Status: Closed
Project: core.logic
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: naeg Assignee: David Nolen
Resolution: Completed Votes: 1
Labels: +fd, bug, finite-domains, infd
Environment:

Clojure 1.4, core.logic 0.8-alpha3



 Description   

When running the code:

(run* [q]
(fresh [a b c d]
(infd a b c d (domain 1 3 4 5))
(+fd b 1 a)
(+fd c 1 b)
(+fd d 1 c)
(== q [a b c d])))

I get the ouput:

([5 4 3 1])

But I would expect:

()

Because [5 4 3 1] is no sequence where the next element is always one number higher than the one before.

It seems to me like +fd behaves as it would take the next element in the domain, instead of taking the next higher number (I hope I didn't misunderstand +fd or infd).



 Comments   
Comment by naeg [ 11/Sep/12 4:48 PM ]

There is workaround using membero:

(run* [q]
  (fresh [a b c d]
    (everyg #(membero % [1 3 4 5]) [a b c d])
    (+fd b 1 a)
    (+fd c 1 b)
    (+fd d 1 c)
    (== q [a b c d])))

=> ()

Note that this is quite a lot slower than it would be with infd.

Comment by David Nolen [ 26/Oct/12 1:03 AM ]

This is fixed try the latest 0.8.0 beta





Generated at Wed Oct 22 22:04:35 CDT 2014 using JIRA 4.4#649-r158309.