# Why does FindInstance take so long: It is faster with more restrictions than with less?

A support case with the identification [CASE:4347836] was created.

I just noted this little puzzle on twitter by Brillant.org:

\begin{align} A B C\\+ BCA\\ = CDE \end{align}

Given that $$A$$ is even and $$C$$ is odd, what does this tell us about $$B$$? Is it (1) odd (2) even, or (3) could it be even or odd?

So why not give FindInstance a go at this? (We will not include strict inequality and checking for $$A,C$$ being even/odd at first)

FindInstance[
100 a + 10 b + c + 100 b + 10 c + a == 100 c + 10 d + e
&& a != b != c != d
&& a ~ Between ~ { 0, 9 }
&& b ~ Between ~ { 0, 9 }
&& c ~ Between ~ { 0, 9 }
&& d ~ Between ~ { 0, 9 }
&& e ~ Between ~ { 0, 9 }
, { a, b, c, d, e }
, Integers
, 10
]

(*
{ {a -> 0, b -> 6, c -> 7, d -> 3, e -> 7}, {a -> 5, b -> 1, c -> 6, d -> 8, e -> 1},
{a -> 6, b -> 1, c -> 7, d -> 9, e -> 3}, {a -> 6, b -> 1, c -> 8, d -> 0, e -> 4},
{a -> 0, b -> 5, c -> 6, d -> 1, e -> 6}, {a -> 4, b -> 1, c -> 5, d -> 6, e -> 9},
{a -> 4, b -> 2, c -> 6, d -> 9, e -> 0}, {a -> 1, b -> 2, c -> 3, d -> 5, e -> 4},
{a -> 0, b -> 7, c -> 8, d -> 5, e -> 8}, {a -> 2, b -> 4, c -> 7, d -> 1, e -> 9} }
*)

The solutions are quickly found, but we want to make sure that $$a \neq b \ne c \ne d \ne e$$ - which is fulfilled for some of the given solutions already.

But, if we expand the inequality restriction to include $$E$$ ...

FindInstance[
100 a + 10 b + c + 100 b + 10 c + a == 100 c + 10 d + e
&& a != b != c != d != e
&& a ~ Between ~ { 0, 9 }
&& b ~ Between ~ { 0, 9 }
&& c ~ Between ~ { 0, 9 }
&& d ~ Between ~ { 0, 9 }
&& e ~ Between ~ { 0, 9 }
, { a, b, c, d, e }
, Integers
]

... FindInstance runs "forever" on a fast laptop running Version 12.0 (Windows 64 bit). How can this be?

Update

What is even more puzzling: If we add all puzzle restrictions, FindInstance comes up with 6 candidates within 0.16 seconds on my machine (quickly showing that the correct answer is (3)):

FindInstance[
100 a + 10 b + c + 100 b + 10 c + a == 100 c + 10 d + e
&& a != b != c != d != e
&& Mod[ a, 2 ] == 0
&& Mod[ c, 2 ] == 1 (* Thank you, @RolfMertig *)
&& a ~ Between ~ { 0, 9 }
&& b ~ Between ~ { 0, 9 }
&& c ~ Between ~ { 0, 9 }
&& d ~ Between ~ { 0, 9 }
&& e ~ Between ~ { 0, 9 }
, { a, b, c, d, e }
, Integers
, 10
]; // AbsoluteTiming

(* {0.163391, Null} *)

But comment out && Mod[a,2]==0 && Mod[c,2] == 1 and FindInstance runs for minutes without any result (I gave up before an answer came up...). This looks "buggy" to me.

Update 2

The documentation tells us that:

Divisible[n, m] is effectively equivalent to Mod[n, m] == 0

But replacing Mod[a, 2] == 0 by Divisible[a, 2] in the code above will throw the error FindInstance::naqs:

FindInstance: ... is not a quantified system of equations and inequalities.

• AbsoluteTiming[tt = FindInstance[ 100*a + 10*b + c + 100*b + 10*c + a == 100*c + 10*d + e && a != b != c != d != e && Mod[a, 2] == 0 && Mod[c, 2] == 1 && Between[a, {0, 8}] && Between[b, {0, 9}] && Between[c, {1, 9}] && Between[d, {0, 9}] && Between[e, {0, 9}], {a, b, c, d, e}, Integers, 10]] executes in 0.15 seconds on my computer. Nov 5 '19 at 15:20
• Your code after "Update" with Mod[ c, 2 ] != 0 uses also 22 seconds on my machine. But if you replace Mod[c,2]!=0 by Mod[c,2]==1, then it is fast ... Nov 5 '19 at 16:07
• @Rolf Thanks for pointing out, I just noted the "little difference" and updated my post.
– gwr
Nov 5 '19 at 16:09