Not just a four fours puzzle

Question

In this variant of the Four fours puzzle your should use up to x x's (and no other number) and a defined set of operations to reach every number from 0 to 100. If x = 4 then you can use up to four 4s and this question becomes the classic four fours puzzle (except you can use up to four 4s rather than having to use exactly four of them). We assume 1 < x <= 9.

In this version, only the following operators are allowed:

• Addition (+), Subtraction (-), Multiplication (*), Division (/). Note this is real division, so that 5/2 = 2.5.
• Exponentiation (e.g. 4^4) as this would involve no extra symbols if written normally by hand.
• You can make new integers by concatenating xs. E.g. you can make the integers 4, 44, 444, 4444.

You may also use parentheses to group numbers simply in order to control the order of evaluation of the operators. You can't for example combine parentheses with concatenation as in (4/4)(4/4) = (1)(1) = 11.

No other symbols may be used and standard order of operations applies.

Your program should generate, given an x in the defined range and an n between 0 and 100 inclusive, a correct solution for that input if it exists. Otherwise your code must output something to indicate no such solution exists.

You must be able to run your submission to completion on your machine for any input values of x and n in the allowed range. This is code golf, so shortest solution wins.

This old related question uses more operators (and only 4s) and hence all numbers from 0 to 100 are solvable which won't be true for this challenge.

Input and output

Your code takes two integers x and n as input and should output a solution (or an indication there is no solution) in any human readable format you find convenient. Input 4 6 would mean "Using up to four 4s, make the number 6" for example. So if the input is 4 6 the output could be (4+4)/4+4.

Answer 1

Python 3, 265 bytes

def f(x,n):
 for e in g(x,x-(x>7)):
  try:
   if eval(e)==n:return e
  except:1
g=lambda x,d:{str(x)*-~i for i in range(d)}|{s%(a,b)for a in g(x,d-1)for b in g(x,d-a.count(str(x)))for s in'%s**%s (%s/%s) (%s+%s) (%s-%s) %s*%s %s/%s'.split()['**'in a+b:]}if d else{}

Try it online!

Works for all numbers in the reference linked by Engineer Toast.

Runs up to x=8 on tio, x=9 takes a couple of minutes on my machine.

---

The function g returns a set of all combinations with at most x number of x's. f then loops through them and returns the first which evaluates to the number n.

The number of possible values i found for each x are:

x  possible numbers
------
2  5
3  17
4  35
5  56
6  83
7  101
8  101
9  101

All the numbers above can be generated from (a+b), (a-b), (a+b), a*b, a/b, (a/b), and a^b. a+b and a-b do not give more numbers.

a^b is also only used once, as otherwise huge numbers are created (this is also verified in the reference document above)

---

An alternate version which short-circuits as soon as it finds a solution (not as golfed):

This is much faster as for x=7..9 all numbers can be created.

Python 3, 338 289 bytes

def f(x,n,d=-1):
 d=[d,x][d<0];X=str(x);r=set()
 for E in{X*-~i for i in range(d)}|{s%(a,b)for a in[0]*d and f(x,n,d-1)for b in f(x,n,d-a.count(X))for s in'%s**%s (%s/%s) (%s+%s) (%s-%s) %s*%s %s/%s'.split()['**'in a+b:]}:
  try:e=eval(E)
  except:e=-1
  if e==n:exit(E)
  r|={E}
 return r

Try it online!