# FindInstance (and Solve, …) abysmally slow on a fully determined system of linear equations and inequalities: why?

I took a quick look for FindInstance and Solve-related questions but came up empty for the aspect that I am curious about. So here is my newbie question:

FindInstance[{
s==9,r==8,d==7,n==6,e==5,y==2,m==1,o==0
},{s,e,n,d,m,o,r,y},Integers]


runs as quickly as one would expect. But

FindInstance[{
s!=e!=n!=d!=m!=o!=r!=y,
s==9,r==8,d==7,n==6,e==5,y==2,m==1,o==0
},{s,e,n,d,m,o,r,y},Integers]


takes ages -- long enough that I ran out of patience before MMA was done.

And now I am curious: Why would Mathematica suddenly display less maths ability than a third-grader?

bill_s suggested something much faster, but it is not equivalent to the original problem. The original inequality required all variable values to be different from all other variable values, such that each value can only be used for one variable. The FindInstance statement in Bill's post only compares x[i] to the ith value, but not to the other n-1 values.

In other news,

FindInstance[{
(*s!=e,s!=n,s!=d,s!=m,s!=o,s!=r,s!=y,*)
(*e!=n,e!=d,e!=m,e!=o,e!=r,e!=y,*)
n!=d,n!=m,n!=o,n!=r,n!=y,
d!=m,d!=o,d!=r,d!=y,
m!=o,m!=r,m!=y,
o!=r,o!=y,
r!=y,
s==9,r==8,d==7,n==6,e==5,y==2,m==1,o==0
},{s,e,n,d,m,o,r,y},Integers]


~1.1 seconds (on my laptop).

FindInstance[{
(*s!=e,s!=n,s!=d,s!=m,s!=o,s!=r,s!=y,*)
e!=n,e!=d,e!=m,e!=o,e!=r,e!=y,
n!=d,n!=m,n!=o,n!=r,n!=y,
d!=m,d!=o,d!=r,d!=y,
m!=o,m!=r,m!=y,
o!=r,o!=y,
r!=y,
s==9,r==8,d==7,n==6,e==5,y==2,m==1,o==0
},{s,e,n,d,m,o,r,y},Integers]


2nd comment uncommentd. ~20 s.

FindInstance[{
s!=e,s!=n,s!=d,s!=m,s!=o,s!=r,s!=y,
e!=n,e!=d,e!=m,e!=o,e!=r,e!=y,
n!=d,n!=m,n!=o,n!=r,n!=y,
d!=m,d!=o,d!=r,d!=y,
m!=o,m!=r,m!=y,
o!=r,o!=y,
r!=y,
s==9,r==8,d==7,n==6,e==5,y==2,m==1,o==0
},{s,e,n,d,m,o,r,y},Integers]


The original version (multiple inequalities in one condition):

Timing[FindInstance[{
s!=e!=n!=d!=m!=o!=r!=y,
s==9,r==8,d==7,n==6,e==5,y==2,m==1,o==0},
{s,e,n,d,m,o,r,y},Integers]]


150 seconds!

• – Mr.Wizard Feb 2 '14 at 10:48
• @Mr.Wizard Thanks, that was one of the questions I came across, and there, at least, MMA had the excuse of actually having to do a little bit of work. :-) – Felix Kasza Feb 2 '14 at 11:06
• Okay, I didn't know if you had seen it. I agree that the behavior you illustrate is enigmatic, and I don't have an explanation for it. In this particular case you could use Reduce @ {s != e != n != d != m != o != r != y, s == 9, r == 8, d == 7, n == 6, e == 5, y == 2, m == 1, o == 0} to remove the inequalities, but this operation itself takes much longer than it arguably should. I would have expected both of your examples to be either fast or slow, rather than one of each. (continued) – Mr.Wizard Feb 2 '14 at 11:13
• FindInstance went with a heuristic method choice that was far from optimal. Next version should be better.. – Daniel Lichtblau Feb 6 '14 at 14:43
• @Felix What you wrote is clear in English. As for the reason, I believe the number of explicit inequalities figures into the method choice heuristic so that could be the cause of worse-than-linear complexity. – Daniel Lichtblau Feb 7 '14 at 15:22

No one has upgraded this post in a long time and as Danny promised all the problems the OP posted have been dealt with. In v 11.1 for instance, the last one now runs in a lot less than 150 seconds.

Timing[FindInstance[{
s!=e!=n!=d!=m!=o!=r!=y,
s==9,r==8,d==7,n==6,e==5,y==2,m==1,o==0},
{s,e,n,d,m,o,r,y},Integers]]

{0.01, {{s -> 9, e -> 5, n -> 6, d -> 7, m -> 1, o -> 0, r -> 8, y -> 2}}}


In the comments, Daniel Lichtblau wrote:

[...] I believe the number of explicit inequalities figures into the method choice heuristic so that could be the cause of worse-than-linear complexity.

So it would seem that FindInstance made an unfortunate choice in tackling this, admittedly odd, set of inequalities.

One possible work-around would be to use smaller, non-overlapping, subsets of inequalities: a!=b!=c!=d&&e!=f!=g!=h and to filter the solution set returned by FindInstance.

• There is no provision for marking a comment as an answer. If after encouraging the comment's author to post it as an answer he does not, it is entirely appropriate to make it into an answer yourself as you did here. (Though I would copy the comment verbatim.) – Mr.Wizard Feb 10 '14 at 13:46

This is more of an extended comment than a genuine answer... but consider this generalization of the problem:

n = 10;
xVec = Array[x, n];
vals = RandomInteger[{0, 10}, n];
Flatten[{Thread[xVec[[1 ;; n/2]] != vals[[1 ;; n/2]]],
Thread[xVec[[n/2 + 1 ;; n]] == vals[[n/2 + 1 ;; n]]]}]

{{x[1] -> 10, x[2] -> 7, x[3] -> 5, x[4] -> 4, x[5] -> 4, x[6] -> 8,
x[7] -> 5, x[8] -> 0, x[9] -> 3, x[10] -> 3}}
{{x[1] -> 0, x[2] -> 0, x[3] -> 0, x[4] -> 0, x[5] -> 0, x[6] -> 0,
x[7] -> 0, x[8] -> 1, x[9] -> 0, x[10] -> 0}}
{x[1] != 7, x[2] != 2, x[3] != 2, x[4] != 2, x[5] != 3, x[6] == 3,
x[7] == 6, x[8] == 5, x[9] == 1, x[10] == 6}


Moreover, it works quite well for even large size problems:

n = 500;
xVec = Array[x, n];
vals = RandomInteger[{0, 10}, n];
First[FindInstance[Thread[xVec == vals], xVec] // Timing]
First[FindInstance[Thread[xVec != vals], xVec] // Timing]
First[Flatten[{Thread[xVec[[1 ;; n/2]] != vals[[1 ;; n/2]]],
Thread[xVec[[n/2 + 1 ;; n]] == vals[[n/2 + 1 ;; n]]]}] // Timing]

2.449844
0.911796
0.000378


Why is the last one so fast compared to the others? It doesn't matter if you rearrange the orders of the three tests. Maybe the slowness has to do with the specific variable names and/or values chosen?

• Too long for a comment, I'll try amending the original post ... – Felix Kasza Feb 7 '14 at 12:47

I am not sure why it takes long time, however, this works quite fast.

Assuming[s != e != n != d != m != o != r != y,
FindInstance[{s == 9, r == 8, d == 7, n == 6, e == 5, y == 2, m == 1, o == 0},
{s, e, n, d, m, o, r, y}, Integers]]

• I don't think FindInstance uses assumptions; if so, this would be equivalent to the OP's first example. – Michael E2 Feb 7 '14 at 0:19

The following is just my guess. Usually != is not dealt with directly, it is broken into a<b || a>b. Then it's natural that the number of cases grows exponentially.