How can I solve the "Riddle of Nine" 9 programmatically?

Question

How can I solve this puzzle programmatically? Can someone help me with some kind of pseudo code or something like that?

Nine 9 s

Combining nine 9 with any number of operators +, -, *, /, (,), what is the smallest positive integer that cannot be expressed?

Prompt:

• The answer is not zero. You can express zero as follows: (9-9) * (9 + 9 + 9 + 9 + 9 + 9 + 9). In addition, zero is not a positive integer.

• The answer is not one. You can express the following: 9 - (9 * 9 - 9) / 9 + 9 - 9 + 9 - 9

• This is not a trick.

• Be sure to handle the brackets correctly.

Notes:

• You cannot use exponent.
• You cannot concatenate (for example, put two 9 together to make 99).
• - .
• , 10.

---

, , , , . , - . - ?

Answer 1

: 195, - Python, , exp1 OP exp2. 0.165 .

exp = [set() for _ in xrange(10)]
exp[0].add(0)
exp[1].update([9, -9])
for i in xrange(1, 10):
  for a in list(exp[i]):
    for j in xrange(i, 10):
      for b in list(exp[j-i]):
        exp[j].update([a+b, a-b, a*b])
        if b != 0:
          exp[j].add(a/b)

n = 0
while n in exp[9]:
  n += 1
print n

---

EDIT: ( ), .

    if ((b != 0) and ((a/b) == float(a)/b)):
      exp[j].add(a/b)

138. ( 1386/10 [ -1386/-10] 138)

Answer 2

195, http://members.iinet.net.au/~tmorrow/mathematics/ninenines/ninenines.html