ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 27 Jun 2016 20:09:41 +0200Solving Logic Problemshttps://ask.sagemath.org/question/33935/solving-logic-problems/ A few years ago I asked [this](http://ask.sagemath.org/question/10068/solving-logic-problems/) question. I have another question along the same lines. Sorry about the <-> notation, I don't know how else to indicate bijection:
children = { Abe, Dan, Mary, Sue }
ages = { 3, 5, 6, 9 }
children <-> ages #bijection - one child per one age
Abe > Dan #Abe is older than Dan
Sue < Mary #Sue is younger than Mary
Sue = Dan + 3 #Sue's age is Dan's age plus 3 years
Mary > Abe #Mary is older than Abe
Can sagemath determine that:
Abe = 5
Dan = 3
Mary = 9
Sue = 6Mon, 27 Jun 2016 18:06:30 +0200https://ask.sagemath.org/question/33935/solving-logic-problems/Answer by tmonteil for <p>A few years ago I asked <a href="http://ask.sagemath.org/question/10068/solving-logic-problems/">this</a> question. I have another question along the same lines. Sorry about the <-> notation, I don't know how else to indicate bijection:</p>
<pre><code>children = { Abe, Dan, Mary, Sue }
ages = { 3, 5, 6, 9 }
children <-> ages #bijection - one child per one age
Abe > Dan #Abe is older than Dan
Sue < Mary #Sue is younger than Mary
Sue = Dan + 3 #Sue's age is Dan's age plus 3 years
Mary > Abe #Mary is older than Abe
</code></pre>
<p>Can sagemath determine that:</p>
<pre><code>Abe = 5
Dan = 3
Mary = 9
Sue = 6
</code></pre>
https://ask.sagemath.org/question/33935/solving-logic-problems/?answer=33936#post-id-33936For such a small problem, an easy way to solve this in Sage is to iterate over all possible permutations and return the compatible ones (brute force method). Actually, you only need Python:
sage: from itertools import permutations
sage: Abe, Dan, Mary, Sue = range(4)
sage: ages = [3, 5, 6, 9]
sage: for p in permutations(ages):
....: if p[Abe] > p[Dan] and p[Sue] < p[Mary] and p[Sue] == p[Dan] + 3 and p[Mary] > p[Abe]:
....: print p
(5, 3, 9, 6)
Mon, 27 Jun 2016 18:46:01 +0200https://ask.sagemath.org/question/33935/solving-logic-problems/?answer=33936#post-id-33936Comment by coder0xff for <p>For such a small problem, an easy way to solve this in Sage is to iterate over all possible permutations and return the compatible ones (brute force method). Actually, you only need Python:</p>
<pre><code>sage: from itertools import permutations
sage: Abe, Dan, Mary, Sue = range(4)
sage: ages = [3, 5, 6, 9]
sage: for p in permutations(ages):
....: if p[Abe] > p[Dan] and p[Sue] < p[Mary] and p[Sue] == p[Dan] + 3 and p[Mary] > p[Abe]:
....: print p
(5, 3, 9, 6)
</code></pre>
https://ask.sagemath.org/question/33935/solving-logic-problems/?comment=33937#post-id-33937The case I present is contrived. What general method can offer solutions for which the set of candidates is "large"?Mon, 27 Jun 2016 18:54:17 +0200https://ask.sagemath.org/question/33935/solving-logic-problems/?comment=33937#post-id-33937Comment by tmonteil for <p>For such a small problem, an easy way to solve this in Sage is to iterate over all possible permutations and return the compatible ones (brute force method). Actually, you only need Python:</p>
<pre><code>sage: from itertools import permutations
sage: Abe, Dan, Mary, Sue = range(4)
sage: ages = [3, 5, 6, 9]
sage: for p in permutations(ages):
....: if p[Abe] > p[Dan] and p[Sue] < p[Mary] and p[Sue] == p[Dan] + 3 and p[Mary] > p[Abe]:
....: print p
(5, 3, 9, 6)
</code></pre>
https://ask.sagemath.org/question/33935/solving-logic-problems/?comment=33939#post-id-33939So, the question is : could you provide an example of instance that you are interested in ?Mon, 27 Jun 2016 19:05:28 +0200https://ask.sagemath.org/question/33935/solving-logic-problems/?comment=33939#post-id-33939Comment by tmonteil for <p>For such a small problem, an easy way to solve this in Sage is to iterate over all possible permutations and return the compatible ones (brute force method). Actually, you only need Python:</p>
<pre><code>sage: from itertools import permutations
sage: Abe, Dan, Mary, Sue = range(4)
sage: ages = [3, 5, 6, 9]
sage: for p in permutations(ages):
....: if p[Abe] > p[Dan] and p[Sue] < p[Mary] and p[Sue] == p[Dan] + 3 and p[Mary] > p[Abe]:
....: print p
(5, 3, 9, 6)
</code></pre>
https://ask.sagemath.org/question/33935/solving-logic-problems/?comment=33938#post-id-33938This is more like an algorithmic question. It really depends on what "large" means. In whole generality such problems are likely to be NP-hard, so there is no much hope to get asymptotically faster ways. That said, there might be ways to express the problem as an integer linear program and use a strong solver, see http://doc.sagemath.org/html/en/reference/numerical/sage/numerical/mip.html and http://doc.sagemath.org/html/en/thematic_tutorials/linear_programming.html
Also, it depends on the kind of instances of your problem, because some of them might belong to some nicer class which could be solved by polynomial means. For example, if there are only comparisons, you can look for linear extensions of partial orders.Mon, 27 Jun 2016 19:04:17 +0200https://ask.sagemath.org/question/33935/solving-logic-problems/?comment=33938#post-id-33938Comment by coder0xff for <p>For such a small problem, an easy way to solve this in Sage is to iterate over all possible permutations and return the compatible ones (brute force method). Actually, you only need Python:</p>
<pre><code>sage: from itertools import permutations
sage: Abe, Dan, Mary, Sue = range(4)
sage: ages = [3, 5, 6, 9]
sage: for p in permutations(ages):
....: if p[Abe] > p[Dan] and p[Sue] < p[Mary] and p[Sue] == p[Dan] + 3 and p[Mary] > p[Abe]:
....: print p
(5, 3, 9, 6)
</code></pre>
https://ask.sagemath.org/question/33935/solving-logic-problems/?comment=33940#post-id-33940I don't really have a better example. My interest is in solving arbitrary systems of constraints, which I understand is a tall order. I believe the first step is to identify what problem domain a set of constraints belongs to. For example, you can model aerodynamic drag as a function "constrained" by an ODE and boundary conditions. Recognizing that problem class, a solution can be determined symbolically. However, I don't know what problem domain my original question falls into; only that it's presented in some logic that includes arithmetic operations and inequalities. I believe Prolog can handle questions like this, so I hoped that sagemath could too. I also noticed that there's a "sudoku" function which, to me atleast, indicates some kind of satisfiability solving.Mon, 27 Jun 2016 19:34:55 +0200https://ask.sagemath.org/question/33935/solving-logic-problems/?comment=33940#post-id-33940Comment by coder0xff for <p>For such a small problem, an easy way to solve this in Sage is to iterate over all possible permutations and return the compatible ones (brute force method). Actually, you only need Python:</p>
<pre><code>sage: from itertools import permutations
sage: Abe, Dan, Mary, Sue = range(4)
sage: ages = [3, 5, 6, 9]
sage: for p in permutations(ages):
....: if p[Abe] > p[Dan] and p[Sue] < p[Mary] and p[Sue] == p[Dan] + 3 and p[Mary] > p[Abe]:
....: print p
(5, 3, 9, 6)
</code></pre>
https://ask.sagemath.org/question/33935/solving-logic-problems/?comment=33942#post-id-33942How can my question be expressed as an ILP problem?Mon, 27 Jun 2016 20:09:41 +0200https://ask.sagemath.org/question/33935/solving-logic-problems/?comment=33942#post-id-33942