\myheading{Almost recreational math: missing operation(s) puzzle}

The equation:

\begin{lstlisting}
1 ? 2 ? 3 ? 4 ? 5 ? 6 ? 7 ? 8 ? 9 = 0
\end{lstlisting}

Fill ? with -, + or * operation, and find such a sequence, so that the equation would be true.
This is tricky, because of operator precedence, multiplication must be handled at first.
Brackets are also possible.

See also:
\url{https://www.dcode.fr/missing-operators-equation-solver}, \\
\url{https://brilliant.org/wiki/arithmetic-puzzles-operator-search/}.

To solve this, I just enumerate all possible ordered binary search tree of 9 elements, which are
almost the same as expression with 9 terms and all possible variations of brackets.

Then we try each expression...

\lstinputlisting[style=custompy]{puzzles/missing_op/missing_Z3.py}

For 9 terms, there are 1430 binary trees, or expressions (9th \emph{Catalan number}).

For 0, there are 1391 solutions, some of them:

\begin{lstlisting}
(1 + (2 + (3 + (4 + (5 * (6 - (7 - (8 - 9)))))))) = 0                                                     
(1 + (2 + (3 + (4 + (5 * (6 - ((7 - 8) + 9))))))) = 0
(1 + (2 + (3 + (4 + (5 * ((6 - 7) + (8 - 9))))))) = 0
(1 + (2 + (3 - (4 + (5 - ((6 * (7 - 8)) + 9)))))) = 0
(1 + (2 + (3 + (4 + (5 * (((6 - 7) + 8) - 9)))))) = 0
(1 - (2 + (3 + (4 + ((5 - 6) + (7 * (8 - 9))))))) = 0
(1 - (2 + (3 + (4 + ((5 - 6) * ((7 - 8) + 9)))))) = 0

...

((((((1 - (2 - 3)) * (4 - 5)) - 6) + 7) - 8) + 9) = 0
(((((((1 - 2) + 3) + (4 - 5)) * 6) - 7) - 8) + 9) = 0
((((((1 + (2 * (3 * 4))) + 5) - 6) - 7) - 8) - 9) = 0
((((((1 * ((2 + 3) + 4)) - 5) + 6) + 7) - 8) - 9) = 0
(((((((1 + 2) - (3 + 4)) + 5) + 6) - 7) * 8) * 9) = 0
(((((((1 * (2 - 3)) * 4) + 5) * 6) - 7) - 8) + 9) = 0
((((((((1 - 2) + 3) + 4) * 5) - 6) - 7) - 8) - 9) = 0  
\end{lstlisting}

There are no solutions for 5432. But for 5430:

\begin{lstlisting}
(1 + (2 + (3 * ((4 * (5 * (6 * (7 + 8)))) + 9)))) = 5430                                                  
(1 + (2 + (3 * ((4 * ((5 * 6) * (7 + 8))) + 9)))) = 5430
(1 + (2 + (3 * (((4 * 5) * (6 * (7 + 8))) + 9)))) = 5430
(1 + (2 + (3 * (((4 * (5 * 6)) * (7 + 8)) + 9)))) = 5430
(1 + (2 + (3 * ((((4 * 5) * 6) * (7 + 8)) + 9)))) = 5430
((1 + 2) + (3 * ((4 * (5 * (6 * (7 + 8)))) + 9))) = 5430
\end{lstlisting}

Surely, several of these expressions are equivalent to each other,
due to associative property of multiplication and addition.

For 1234:

\begin{lstlisting}
(1 * (2 * (((3 - (4 - ((5 + 6) * 7))) * 8) + 9))) = 1234                                                  
(1 + (2 + ((((3 * ((4 + 5) * 6)) - 7) * 8) - 9))) = 1234
(1 + (2 + (((((3 * (4 + 5)) * 6) - 7) * 8) - 9))) = 1234
(1 + ((2 + (3 * ((4 + 5) * (6 + (7 - 8))))) * 9)) = 1234
(1 + ((2 + (3 * ((4 + 5) * ((6 + 7) - 8)))) * 9)) = 1234
(1 + ((2 + (3 * ((4 + (5 - 6)) * (7 + 8)))) * 9)) = 1234
(1 + ((2 + (3 * (((4 + 5) - 6) * (7 + 8)))) * 9)) = 1234
(1 + ((2 + (3 * (((4 * (5 + 6)) - 7) + 8))) * 9)) = 1234
(1 + ((2 + ((3 * (4 + 5)) * (6 + (7 - 8)))) * 9)) = 1234
(1 - ((2 - (((3 + 4) * 5) + ((6 + 7) * 8))) * 9)) = 1234
(1 + ((2 + ((3 * (4 + (5 - 6))) * (7 + 8))) * 9)) = 1234
(1 + ((2 + ((3 * ((4 + 5) - 6)) * (7 + 8))) * 9)) = 1234
(1 + ((2 - (((3 * (4 - 5)) - 6) * (7 + 8))) * 9)) = 1234
(1 - ((2 + ((3 * ((4 - (5 + 6)) * 7)) + 8)) * 9)) = 1234
(1 - ((2 + ((3 * (((4 - 5) - 6) * 7)) + 8)) * 9)) = 1234
(1 - ((2 + (((3 * (4 - (5 + 6))) * 7) + 8)) * 9)) = 1234
(1 - ((2 + (((3 * ((4 - 5) - 6)) * 7) + 8)) * 9)) = 1234
(1 - ((2 - ((((3 * (4 + 5)) - 6) * 7) - 8)) * 9)) = 1234
(1 - (((2 - ((3 + 4) * 5)) - ((6 + 7) * 8)) * 9)) = 1234
(1 - (((2 - ((3 + (4 * 5)) * 6)) + (7 - 8)) * 9)) = 1234
(1 + (((2 + (3 - (4 * (5 - (6 * 7))))) * 8) + 9)) = 1234
(1 + (((2 + (3 + (4 * ((5 * 6) + 7)))) * 8) + 9)) = 1234
(1 - (((2 + (3 * ((4 - (5 + 6)) * 7))) + 8) * 9)) = 1234
(1 - (((2 + (3 * (((4 - 5) - 6) * 7))) + 8) * 9)) = 1234
(1 - (((2 + ((3 * (4 - (5 + 6))) * 7)) + 8) * 9)) = 1234
(1 - (((2 + ((3 * ((4 - 5) - 6)) * 7)) + 8) * 9)) = 1234
(1 - (((2 - (((3 + (4 * 5)) * 6) - 7)) - 8) * 9)) = 1234
(1 + ((((2 + 3) - (4 * (5 - (6 * 7)))) * 8) + 9)) = 1234
(1 - ((((2 - (3 * ((4 + 5) * 6))) + 7) * 8) - 9)) = 1234
(1 - ((((2 - ((3 + (4 * 5)) * 6)) + 7) - 8) * 9)) = 1234
((1 + 2) + ((((3 * ((4 + 5) * 6)) - 7) * 8) - 9)) = 1234
((1 + 2) + (((((3 * (4 + 5)) * 6) - 7) * 8) - 9)) = 1234
((1 + (2 + (((3 * ((4 + 5) * 6)) - 7) * 8))) - 9) = 1234
((1 + (2 + ((((3 * (4 + 5)) * 6) - 7) * 8))) - 9) = 1234
((1 + ((2 + (3 - (4 * (5 - (6 * 7))))) * 8)) + 9) = 1234
((1 + ((2 + (3 + (4 * ((5 * 6) + 7)))) * 8)) + 9) = 1234
((1 - ((2 - ((3 * ((4 + 5) * 6)) - 7)) * 8)) + 9) = 1234
((1 - ((2 - (((3 * (4 + 5)) * 6) - 7)) * 8)) + 9) = 1234
((1 + (((2 + 3) - (4 * (5 - (6 * 7)))) * 8)) + 9) = 1234
((1 - (((2 - (3 * ((4 + 5) * 6))) + 7) * 8)) + 9) = 1234
((1 - (((2 - ((3 * (4 + 5)) * 6)) + 7) * 8)) + 9) = 1234
(((1 + 2) + (((3 * ((4 + 5) * 6)) - 7) * 8)) - 9) = 1234
(((1 + 2) + ((((3 * (4 + 5)) * 6) - 7) * 8)) - 9) = 1234
\end{lstlisting}

The problem is easy enough to be solved using my
toy-level MK85 SMT-solver:

\lstinputlisting[style=custompy]{puzzles/missing_op/missing_MK85.py}