generate a valid equation using specified operators

Question

A twist on a recently asked question, you are given a list of operators and a result and you need to find integers which, when operated on by those operators, generate the result.

Example 1

input

+ + * / 13

possible output

4 8 2 2 4

which means that 4 + 8 + 2 * 2 / 4 = 13.

More specifically, you are given a sequence of N operators (between 1 and 5 inclusive) and an integer result, space separated. You must print N+1 integers, space separated, in the range 1 through 9, inclusive, that when alternated with the operators produce the result.

The operators are +,-,*,/. They have the natural precedence order (* and / before + and -, left associative). Divides must be integral divides, a divide with a fractional result is not allowed. Operators must appear in the order given.

Most problems will have more than one solution. Printing any of them, or any subset of them, is fine. If there is no solution, print NO SOLUTION.

Example 2

input

/ + - - 16

output

9 1 9 1 1

Example 3

input

+ 5

output

1 4
2 3
3 2
4 1

(or any nonempty subset of those lines)

Example 4

input

+ + 30

output

NO SOLUTION

Example 5

input

/ + / 3

output

6 3 5 5

note that 3 2 3 2 is not a solution, as 3/2+3/2=3 is true but the individual divides have fractional values.

Standard code golf, shortest answer wins.

Answer 1

Perl, 129 160 151 chars

sub a{my($s,$t,$o)=splice@_,0,3;@_?map{a("$s $_","$t$o$_",@_)}1..9:
$o-eval$t||$o-eval"use integer;$t"||exit say$s}a"","","",split$",<>;say"NO SOLUTION"

Fun with recursion. The program exits upon finding the first valid tuple.

The eval has to be done twice, in and out of integer-only mode, in order to avoid invalid solutions like that given in example 5 in the description.

Answer 2

Python (197 212 277)

Related question, related answer. Gives the answer and an error if there is one, else prints "NO SOLUTION".

import re,itertools as I
e=eval;a=raw_input().split();c=1;b=len(a)
for i in I.product('123456789',repeat=b):
 d=''.join(sum(zip([j+'.'for j in i],a),()))[:3*b-1]
 if e(d)==int(a[-1])and all([e(n)%1==0 for n in re.findall('\d./\d.',d)]):print' '.join(i);c=0
print"NO SOLUTION"*c

Answer 3

Scala 333

val o=args.init
val e=args.last
val n=(1 to 9)
val i=new bsh.Interpreter
def b(o:Array[String],s:String=""):Boolean={
if(s.isEmpty)n.exists(y=>b(o,s+y))else
if(o.isEmpty){
val r=i.eval(s)
if(r.toString==e){
println(s.replaceAll("[-*+/]"," "))
true}else false}else
n.exists(x=>b(o.tail,s+o(0)+x))
}
b(o)||{println("NO SOLUTION");true}

Answer 4

Python 2.7, 192 190 184 181 chars

Getting rid of itertools.product saved 3 characters.

s=raw_input().split()
j=' '.join
s[-1]='=='+s[-1]
n=len(s)
x=[j(i)for i in map(str,range(10**(n-1),10**n))if'0'not in i and eval(j(map(j,zip(i,s))))]
print x and x[0]or"NO SOLUTION"