Pi Estimation using Integers
Here are three approximations which I came up with, just by sitting down and "playing" with the numbers (no brute-force algorithm needed):
1.) $\pi \approx 3+\dfrac {(5 \times 7)^{(\large8/9)^4}} {2^6+1} = 3.1415926539$
2.) $\pi \approx \left (\dfrac{3^7} {5+8+9} -2\right)^{1/4} = 3.141592652$
3.) $\pi \approx \dfrac{7^3+2 \times 6} {(8+5) \times 9 - 4} = \dfrac {355} {113} = 3.1415929$
I'm sure that there are other solutions out there, these are just the first that I could think of.
I find formula, which provides $11$ correct digits of $\pi$ (including the leading $3.$):
$$ \begin{array}{|c|}\hline\\ {\Large \pi \approx \;}{\huge 3 +} \dfrac {\huge 9^{^{\frac{2}{5\cdot 7} - (1+6)^{-4}}}} {\huge 8} \large = 3.1415926535 \color{Tan}{916691}..., \\ \hline \end{array}\tag{1} $$ error (deviation) is equal to $\Delta = 1.875904... \times 10^{-12}$.
The question is closely related to pandigital approximation of $\pi$
(see http://mathworld.wolfram.com/PiApproximations.html), eq. $(32),(35) - (38)$.
Other solutions with high accuracy (which provide $10$ correct digits):
\begin{array}{lrrr} \phantom{WWWWWWWWWWWWW} & & & \\ \pi\approx {\Large 1+\dfrac{(6-9^{-5})^{(4+7)^{8^{-2}}}}{3}} & = 3.141592653 \color{Tan}{473482}... & (\Delta=1.163107... \times 10^{-10}); & (2) \end{array} \begin{array}{lrrr} \phantom{WWWWWWWWWWWWW} & & & \\ \pi\approx \dfrac{\huge 12^{ \frac{7-\frac{3^{-5}}{6}}{8 \cdot 9}}}{\Large 4} & = 3.141592653 \color{Tan}{437419}... & (\Delta=1.523732... \times 10^{-10}); & (3) \end{array}
\begin{array}{lrrr} \phantom{WWWWWWWWWWWWW} & & & \\ \pi\approx {\large 56^{4^{\Large-9^{-3^{-2}}}}}-\dfrac{7-1}{8} & = 3.141592653 \color{Tan}{772701}... & (\Delta=1.829078... \times 10^{-10}); & (4) \end{array} formula $(4)$ looks like "telescope".
\begin{array}{lrrr} \phantom{WWWWWWWWWWWWW} & & & \\ \pi\approx \Bigl(4 \cdot 92^{3/8}\Bigr)^{\Large\frac{1+\frac{6}{7}}{5}} & = 3.141592653 \color{Tan}{854014}... & (\Delta=2.642208... \times 10^{-10}); & (5) \end{array}
\begin{array}{lrrr} \phantom{WWWWWWWWWWWWW} & & & \\ \pi\approx 94 \cdot \left(\dfrac{8}{13}\right)^{7} - \dfrac{5^{-6}}{2} & = 3.141592653 \color{Tan}{854369}... & (\Delta=2.645759... \times 10^{-10}); & (6) \end{array}
\begin{array}{lrrr} \phantom{WWWWWWWWWWWWW} & & & \\ \pi\approx 4-1+\dfrac{\Bigl((6-7^{-3})\cdot 9\Bigr)^{\Large 2^{-5}}}{8} & = 3.141592653 \color{Tan}{863925}... & (\Delta=2.741318... \times 10^{-10}); & (7) \end{array}
\begin{array}{lrrr} \phantom{WWWWWWWWWWWWW} & & & \\ \pi\approx 3+\dfrac{1}{7+4^{-2}} - \left(6-\dfrac{5}{8}\right)^{-9} & = 3.141592653 \color{Tan}{303244}... & (\Delta=2.865490... \times 10^{-10}); & (8) \end{array}
\begin{array}{lrrr} \phantom{WWWWWWWWWWWWW} & & & \\ \pi\approx {\large 3+\dfrac{1-9^{\Large-(6-8^{-5})}}{7+4^{-2}}} & = 3.141592653 \color{Tan}{904056}... & (\Delta=3.142632... \times 10^{-10}); & (9) \end{array}
\begin{array}{lrrr} \phantom{WWWWWWWWWWWWW} & & & \\ \pi\approx \color{gray}{3+\dfrac{\left(5 \cdot 7\right)^{(8/9)^4}}{2^6+1}} & \color{gray}{ = 3.141592653 \color{Tan}{915932}...} & \color{gray}{ (\Delta=3.261394... \times 10^{-10});} & \color{gray}{(10)} \end{array} formula $(10)$ is obtained by user14069, see above (cited just for accuracy comparison).
\begin{array}{lrrr} \phantom{WWWWWWWWWWWWW} & & & \\ \pi\approx \color{gray}{3+\dfrac{1-(9-8^{-5})^{-6}}{7+4^{-2}}} & \color{gray}{= 3.141592653 \color{Tan}{916501}...} & \color{gray}{(\Delta=3.267085... \times 10^{-10});} & \color{gray}{(11)} \end{array} formula $(11)$ is obtained by Ed Pegg, see source (cited just for accuracy comparison).
\begin{array}{lrrr} \phantom{WWWWWWWWWWWWW} & & & \\ \pi\approx 3+\dfrac{75248}{9^6-1} & = 3.141592653 \color{Tan}{921421}... & (\Delta=3.316278... \times 10^{-10}); & (12) \end{array}
\begin{array}{lrrr} \phantom{WWWWWWWWWWWWW} & & & \\ \pi\approx 3+\dfrac{1-9^{-6}}{7+4^{-2}} & = 3.141592653 \color{Tan}{921922}... & (\Delta=3.321291... \times 10^{-10}); & (13) \end{array} formula $(13)$ looks very easy; it contains $7$ digits only.
\begin{array}{lrrr} \phantom{WWWWWWWWWWWWW} & & & \\ \pi\approx 3+\dfrac{5-4-9^{-6}}{7+\dfrac{1}{2 \cdot 8}} & = 3.141592653 \color{Tan}{921922}... & (\Delta=3.321291... \times 10^{-10}); & (13') \end{array}
\begin{array}{lrrr} \phantom{WWWWWWWWWWWWW} & & & \\ \pi\approx 3+\dfrac{8\cdot(1-9^{-6})}{57-\dfrac{2}{4}} & = 3.141592653 \color{Tan}{921922}... & (\Delta=3.321291... \times 10^{-10}); & (13'') \end{array}
formulas $(13'), (13'')$ are equal to $(13)$, but use all digits.
\begin{array}{lrrr} \phantom{WWWWWWWWWWWWW} & & & \\ \pi\approx 3+\dfrac{8}{\Bigl(1+9^{-6}\Bigr)\cdot \Bigl(57-\dfrac{2}{4}\Bigr)} & = 3.141592653 \color{Tan}{922423}... & (\Delta=3.326304... \times 10^{-10}); & (14) \end{array}
\begin{array}{lrrr} \phantom{WWWWWWWWWWWWW} & & & \\ \pi\approx {\large \dfrac{1+\Biggl(\dfrac{2^{\Large 4^{6/5}}}{9}\Biggr)^3}{8}-7} & = 3.141592653 \color{Tan}{226228}... & (\Delta= 3.635644... \times 10^{-10}); & (15) \end{array}
\begin{array}{lrrr} \phantom{WWWWWWWWWWWWW} & & & \\ \pi\approx \dfrac{3}{\dfrac{1}{4}-{\Large 7^{- \bigl(2+5^{6^{-8}}\bigr)} }}-9 & = 3.141592653 \color{Tan}{223921}... & (\Delta= 3.658712... \times 10^{-10}); & (16) \end{array}
\begin{array}{lrrr} \phantom{WWWWWWWWWWWWW} & & & \\ \pi\approx 3+\left(8-1+(2 \cdot 5)^{4/9} \right)^{-6/7} &= 3.141592653 \color{Tan}{169312}... &(\Delta=4.204806...\times 10^{-10}); &(17) \end{array}
\begin{array}{lrrr} \phantom{WWWWWWWWWWWWW} & & & \\ \pi\approx {\Large 3 \cdot \Bigl(1+\frac{4}{9} \Bigr)^{5^{-8^{6 \cdot 7^{-2}}}}} & = 3.141592653 \color{Tan}{160095}... & (\Delta= 4.296978... \times 10^{-10}); & (18) \end{array}
\begin{array}{lrrr} \phantom{WWWWWWWWWWWWW} & & & \\ \pi\approx 3+\left(8-1+4^{-2}\right)^{\Large{-7^{\Large{5\cdot 6^{-9}}}}} &= 3.141592653 \color{Tan}{130264}... &(\Delta=4.595292... \times 10^{-10}); &(19) \end{array}
\begin{array}{lrrr} \phantom{WWWWWWWWWWWWW} & & & \\ \pi\approx \dfrac{7}{5}\cdot \Biggl(\Large 1 + 4^{\LARGE 2^{\Large -\frac{8-9^{-6}}{3}}}\Biggr) &= 3.141592653 \color{Tan}{021507}... &(\Delta=5.682853... \times 10^{-10}). &(20) \end{array}
Note: formulas $(3) - (6), (12), (13''), (14)$ contain concatenation of digits. Probably this trick is not allowed in contest/task.
And I'd like to say a few words about famous approximation
$\pi \approx \dfrac{355}{113}$.
$\pi \approx \dfrac{2485}{791} = 3.141592\color{Tan}{920353}...$ ($7$ correct digits). It contains $1$ operation only.
And about beauty of fraction $\dfrac{355}{113}$:
what a nice pandigital finite generalized continued fractions for $\pi$:
$$
\begin{array}{|ccc|}
\hline
& \Large\pi & \\
& \wr\wr & \\
2+\cfrac{9}{5+\cfrac{4}{1+\cfrac{3}{7+\cfrac{6}{8\color{#DDDDDD}{\small +0}}}}}
& = \dfrac{355}{113} = &
3+\cfrac{1}{6+\cfrac{9}{8+\cfrac{4}{5+\cfrac{7}{2\color{#DDDDDD}{\small +0}}}}} \\
\hline
\end{array}$$
These formulas looked intriguing, so I decided to try to compute some of them myself with Maple, using the approximation $$\pi \approx \frac{355}{113} \approx 3.1415929.$$
The algorithm uses dynamic programming where the nodes are the subsets of $\{1,2,3,\ldots,8,9\}$ and the corresponding value is a table of all integer values less than some maximum that can be expressed by a legal formula as specified in the problem definition using the digits in the subset. The recursive step splits the argument into two sets and combines the values obtained for them using the five operators that are given. In the present case I used $360$ as the maximum value because $355<360.$ Finally in order to express a fraction we iterate over all 2-partitions of the nine digits, looking to find a pair where the first subset can express the numerator and the second one the denominator. The approximations are not limited to $\pi$, one may try for any fraction with small numerator and denominator.
Here are some of the formulas that I obtained: $$\frac{1 \times \left(2 \times 6 + {7}^{3}\right)}{5 + 9 \times \left(4 + 8\right)}$$ $$\frac{1 + 5 + 6 + {7}^{3}}{{9}^{2} + 4 \times 8}$$ $$\frac{5 \times \left(8 + 9 \times \left(1 + 6\right)\right)}{{7}^{2} + {4}^{3}}$$ $$\frac{5 \times \left(\left(8 \times 9\right) - 1\right)}{7 - \left(\frac{4 - \left({6}^{3}\right)}{2}\right)}$$ $$\frac{4 + 8 + {7}^{3}}{1 - \left(9 - \left({\left(5 + 6\right)}^{2}\right)\right)}$$ $$\frac{\left(2 + 3\right) \times \left(\left(8 \times 9\right) - 1\right)}{\left(4 \times \left(5 \times 6\right)\right) - 7}$$ $$\frac{5 \times \left(\left(6 \times \left(3 + 9\right)\right) - 1\right)}{\left({\left(4 + 7\right)}^{2}\right) - 8}$$ $$\frac{\left(6 - 1\right) \times \left(8 + 7 \times 9\right)}{{2}^{5} + {3}^{4}}$$
Here are some examples obtained by enabling concatenation: $$ \frac{5 \times 71}{2 - \left(3 - \left(6 + 9 \times \left(4 + 8\right)\right)\right)}$$ $$ \frac{71 \times \left(2 + 3\right)}{4 + 5 + 6 + 98}$$ $$ \frac{5 \times \left(73 - 2\right)}{6 - \left(1 - \left(9 \times \left(4 + 8\right)\right)\right)}$$ $$ \frac{5 \times \left(9 + 62\right)}{1 + 8 \times \left(3 + 4 + 7\right)}$$ $$ \frac{5 \times \left(7 + {8}^{2}\right)}{1 + 3 \times 6 + 94}$$ $$ \frac{\left(7 \times 52\right) - 9}{1 - \left(8 \times \left(4 - \left(3 \times 6\right)\right)\right)}$$ $$ \frac{5 \times \left(7 + 64\right)}{1 - \left(9 - \left({\left(3 + 8\right)}^{2}\right)\right)}$$ $$ \frac{\left(51 \times \left(3 + 4\right)\right) - 2}{8 + 7 \times \left(6 + 9\right)}$$ $$ \frac{31 + 9 \times \left({6}^{2}\right)}{4 \times 7 + 85}$$ $$ \frac{\left(9 - 4\right) \times \left(72 - 1\right)}{83 + 5 \times 6}$$ $$ \frac{5 \times \left(8 + 64 - 1\right)}{92 + 3 \times 7}$$ $$ \frac{\left(9 \times 41\right) - \left(6 + 8\right)}{7 + 2 \times 53}$$ $$ \frac{4 + 8 + {7}^{\left(\frac{9}{3}\right)}}{51 + 62} $$ $$ \frac{5 + 7 \times \left(\left(6 \times 9\right) - 4\right)}{31 + 82}$$
The following examples have special property which is left to the reader to discover. $$ \frac{71 \times \left(2 + 8\right)}{4 + 3 \times \left(9 + 65\right)}$$ $$ \frac{71 \times \left(4 + 6\right)}{2 \times \left(3 \times 5 + 98\right)}$$ $$ \frac{5 \times \left(61 + {3}^{4}\right)}{{2}^{7} + 98}$$ $$ \frac{\left(9 \times \left(84 - 5\right)\right) - 1}{\left(3 \times 76\right) - 2}$$ $$ \frac{6 - \left(8 \times \left(4 - 92\right)\right)}{1 + 3 \times 75}$$ $$ \frac{\left(4 + 6\right) \times \left(8 + 7 \times 9\right)}{1 + {\left(3 \times 5\right)}^{2}}$$
Last but not least, we have $$\frac{3 \times \left(5 \times 71\right)}{9 + \left(8 \times 42\right) - 6}$$ $$\frac{71 \times \left(6 + 9\right)}{2 + 5 + 4 \times 83}$$ $$\frac{41 + 8 \times \left({2}^{7}\right)}{{3}^{5} + 96}$$ $$\frac{\left(6 + 9\right) \times \left(72 - 1\right)}{\left(8 \times 43\right) - 5}$$ $$\frac{3 \times \left(5 \times \left(\left(8 \times 9\right) - 1\right)\right)}{\left({7}^{\left(\frac{6}{2}\right)}\right) - 4}$$ $$\frac{1 + \left(5 + 9\right) \times \left(82 - 6\right)}{\left({7}^{3}\right) - 4}.$$
It would be interesting to know whether the next best approximation, which according to Wikipedia is $$\frac{52163}{16604} \approx 3.141592387$$ can be represented this way, whether there is another fraction with a smaller denominator that produces more correct places and whether one has to add concatenation to the set of operators for this to occur.
This is the code of the Maple program. Enjoy!
with(combinat,powerset); maxval := 360; repr := proc(s) local d, f, dstr, fstr, dtstr, ftstr, res, aprob, bprob, x, y, leftset, rightset, check, typeset; option remember; res := table(); if nops(s) = 1 then d := op(1,s); res[d] := [d, sprintf("%d", d), sprintf("%d", d)]; return op(res); fi; check := proc(val) if type(res[val], list) then return false; fi; if type(val, integer) and abs(val)<maxval then return true fi; return false; end proc; typeset := proc(dtstr, what, ftstr) local pard, parf; if length(dtstr)=1 then pard := dtstr; else pard := sprintf("\\left(%s\\right)", dtstr); fi; if length(ftstr)=1 then parf := ftstr; else parf := sprintf("\\left(%s\\right)", ftstr); fi; if evalb(what = "+") then return sprintf("%s + %s", dtstr, ftstr); elif evalb(what = "-") then return sprintf("%s - %s", pard, parf); elif evalb(what = "*") then return sprintf("%s \\times %s", pard, parf); elif evalb(what = "/") then return sprintf("\\frac{%s}{%s}", dtstr, ftstr); fi; return sprintf("{%s}^{%s}", pard, parf); end proc; for leftset in powerset(s) do rightset := s minus leftset; if nops(leftset)=0 or nops(rightset)=0 then next fi; aprob := repr(leftset); bprob := repr(rightset); if nops(op(op(res))) = 2*maxval-1 then next fi; for x in op(aprob) do for y in op(bprob) do d := x[1]; dstr:= x[2]; dtstr := x[3]; f := y[1]; fstr:= y[2]; ftstr := y[3]; if check(d+f) then res[d+f] := [d+f, sprintf("(%s) + (%s)", dstr, fstr), typeset(dtstr, "+", ftstr)]; fi; if check(d-f) then res[d-f] := [d-f, sprintf("(%s) - (%s)", dstr, fstr), typeset(dtstr, "-", ftstr)]; fi; if check(d*f) then res[d*f] := [d*f, sprintf("(%s) * (%s)", dstr, fstr), typeset(dtstr, "*", ftstr)]; fi; if f <> 0 and check(d/f) then res[d/f] := [d/f, sprintf("(%s) / (%s)", dstr, fstr), typeset(dtstr, "/", ftstr)]; fi; if not(d=0 or f=0) and evalf(abs(f*log(d))<10) and check(d^f) then res[d^f] := [d^f, sprintf("(%s) ^ (%s)", dstr, fstr), typeset(dtstr, "^", ftstr)]; fi; od od; od; return op(res); end; approx_frac := proc(what) local allset, numerset, denomset, x, y, xt, yt, xpair, ypair; allset := {seq(k, k=1..9)}; for numerset in powerset(allset) do denomset := allset minus numerset; if nops(numerset)>=1 and nops(denomset)>=1 then xt := repr(numerset); yt := repr(denomset); xpair := xt[numer(what)]; ypair := yt[denom(what)]; if type(xpair, list) and type(ypair, list) then printf("(%s) / (%s) %a %a\n\\frac{%s}{%s}\n\n", xpair[2], ypair[2], xpair[1]/ypair[1], evalf(xpair[1]/ypair[1]), xpair[3], ypair[3]); fi; fi; od; end;