Solve a Matchstick puzzle
JavaScript (ES6), 297 286 279 267 bytes

Takes input in currying syntax (s)(k), where s is an array of digit characters and k is the number of moves (integer).

s=&gt;k=&gt;(B=(n,b=0)=&gt;n?B(n^n&amp;-n,b+1):b,b=[...p='u"[k,iy#}m'].map(c=&gt;c.charCodeAt()+2),r=[],g=(n,d='')=&gt;n?n&gt;0&amp;&amp;b.map((v,i)=&gt;g(n-B(v),d+i)):r.push(d))(s.reduce((s,c)=&gt;s+B(b[c]),M=0))&amp;&amp;b.map((_,j)=&gt;r.map(n=&gt;M=[...n+p].reduce((t,d,i)=&gt;t+B(b[d]^b[s[i-j]]),0)&gt;k*2|+n&lt;M?M:n))|M


Test cases



let f=

s=&gt;k=&gt;(B=(n,b=0)=&gt;n?B(n^n&amp;-n,b+1):b,b=[...p='u"[k,iy#}m'].map(c=&gt;c.charCodeAt()+2),r=[],g=(n,d='')=&gt;n?n&gt;0&amp;&amp;b.map((v,i)=&gt;g(n-B(v),d+i)):r.push(d))(s.reduce((s,c)=&gt;s+B(b[c]),M=0))&amp;&amp;b.map((_,j)=&gt;r.map(n=&gt;M=[...n+p].reduce((t,d,i)=&gt;t+B(b[d]^b[s[i-j]]),0)&gt;k*2|+n&lt;M?M:n))|M

console.log("0   / 1 -&gt; " + f([..."0"  ])(1)) // -&gt; 9
console.log("0   / 3 -&gt; " + f([..."0"  ])(3)) // -&gt; 77
console.log("0   / 4 -&gt; " + f([..."0"  ])(4)) // -&gt; 111
console.log("8   / 3 -&gt; " + f([..."8"  ])(3)) // -&gt; 74
console.log("220 / 1 -&gt; " + f([..."220"])(1)) // -&gt; 320
console.log("220 / 2 -&gt; " + f([..."220"])(2)) // -&gt; 520
console.log("220 / 3 -&gt; " + f([..."220"])(3)) // -&gt; 7227
console.log("220 / 4 -&gt; " + f([..."220"])(4)) // -&gt; 22111
console.log("220 / 5 -&gt; " + f([..."220"])(5)) // -&gt; 32111
console.log("747 / 1 -&gt; " + f([..."747"])(1)) // -&gt; 747
console.log("747 / 2 -&gt; " + f([..."747"])(2)) // -&gt; 7171
console.log("747 / 3 -&gt; " + f([..."747"])(3)) // -&gt; 7711






How?

Shape data and helper function


The array b describes the shapes of the digits as 7-bit integers, where each bit is a segment:



For instance, the shape of "7" is 0b0100101 = 37.
The helper function B() returns the number of 1's in the binary representation of a given number:

B = (n, b = 0) =&gt; n ? B(n ^ n &amp; -n, b + 1) : b



Step #1

We first count the number of matchsticks used in the input number:

s.reduce((s, c) =&gt; s + B(b[c]), 0)


Step #2

We pass this value to the recursive function g(), which populates a list r with all numbers that can be built with exactly this number of matchsticks:

g = (n, d = '') =&gt;
  n ?
    n &gt; 0 &amp;&amp;
    b.map((v, i) =&gt; g(n - B(v), d + i))
  :
    r.push(d)


For instance, g(5) will load [ '17', '2', '3', '5', '71' ] into r.

Step #3

We now have to select the highest number M in r which can actually be obtained from the input number, within the allowed number of moves k.

Because each number n in r uses exactly as many matchsticks as the input number s, the number of moves required to transform s into n equals half the number of segment differences between each of their digits.

The number of segment differences between two digits x and y is given by the number of 1's in the binary representation of b[x] XOR b[y].

Finally, it's important to note that we need to try several possible digit alignments, because the first digit of s is not necessarily mapped to the first digit of n. The shift between the digits is given by the variable j in the code.