There are several optimisations that can be performed on the brute force algorithm on the most obvious search space, for finding strings like this.

The solution to the problem contains 10 digits, and each digit contains a number from to 9. This means the most obvious search space is the set of all strings 0000000000 to 9999999999, or 10,000,000,000 search items. This space can be drastically reduced with some logic applied to the problem in advance.

First, as has been pointed out by m_turner, the sum of all the digits must be 10 (in Eindhoven notation, using N-Wing's symbols, (+ : 0 ≤ `i` < 10 : `d`_{i}) = 10). So, if values are chosen for digits `d`_{9} to `d`_{1}, there is only one possible valid value for `d`_{0} = 10 - (+ : 0 < `i` < 10 : `d`_{i}). This reduces the search space by a factor of 10. (If the computed value for `d`_{0} is negative, then the chosen values for `d`_{9} to `d`_{1} are invalid. Indeed, if the computed value is 0, then you don't have a valid string either.)

Second, as has been pointed out by N-Wing, the sum of all the digits `d`_{i} multiplied by their position in the string `i` must be 10, i.e. (+ : 0 ≤ `i` < 10 : (`i` * `d`_{i})) = 10. Since 0 * `x` = `x` for all `x`, this expression is equivalent to (+ : 0 < `i` < 10 : (`i` * `d`_{i})) = 10. `d`_{1} can be isolated from the equation, `d`_{1} = 10 - (+ : 1 < `i` < 10 : (`i` * `d`_{i})). This reduces the search space by another factor of 10. (Again, if the computed value for `d`_{1} is negative, then the previously chosen values for the string cannot make a valid solution.)

Applying the same formula in the above paragraph in a different way, we have that for each `i`, (`i` * `d`_{i}) ≤ 10. This leads to the third optimisation (also suggested by N-Wing): instead of checking every digit `d`_{i} with values 0 to 9, check `d`_{i} with values 0 to floor(10 / `i`). `d`_{9} cannot be 2 or greater, because then (9 * `d`_{9}) > 10 so (+ : 1 < `i` < 10 : (`i` * `d`_{i})) > 10. Similarly, `d`_{8}, `d`_{7}, and `d`_{6} cannot be 2 or greater. `d`_{5} and `d`_{4} cannot be 3 or higher, `d`_{3} cannot be 4 or higher, and `d`_{2} cannot be 6 or higher. This reduces the search space to 2 * 2 * 2 * 2 * 3 * 3 * 4 * 6, or 2^{7} * 3^{3} = 128 * 27 = 3456.

This final optimisation can be pursued even more aggressively, in that, for example, at most one of `d`_{9}, `d`_{8}, `d`_{7}, and `d`_{6} can be 1 (because if `d`_{7} and `d`_{6} were both one, 7 * `d`_{7} + 6 * `d`_{6} = 7 * 1 + 6 * 1 = 7 + 6 = 13 > 10). This reduces the search space to 40.

The following is a Lua program for showing all these types of strings in any specified base.

-- To run, type:
-- lua -f *Problem.lua* *B*
-- where *Problem.lua* is the name of this file
-- and *B* is the base
Problem = {}
Problem.Show = function()
write ("Solution:")
local i = Problem.B
while (i > 0) do
i = (i - 1)
write (" " .. Problem.A[i])
end
write ("\n")
end
Problem.Check = function()
local Test, i, success = {}, Problem.B, 0
while (i > 0) do
i = (i - 1)
Test[i] = 0
end
i = Problem.B
while (i > 0) do
i = (i - 1)
local x = Problem.A[i]
Test[x] = (Test[x] + 1)
end
i = Problem.B
while ((i > 0) and (success ~= nil)) do
i = (i - 1)
if (Test[i] ~= Problem.A[i]) then
success = nil
end
end
Problem.Checked = (Problem.Checked + 1)
return (success)
end
Problem.Solve1 = function(n, Total0, Total1)
if (n < 2) then
Problem.A[1] = (Problem.B - Total1)
if (Problem.A[1] >= 0) then
Total0 = (Total0 + Problem.A[1])
Problem.A[0] = (Problem.B - Total0)
if (Problem.A[0] > 0) then
if (Problem.Check() ~= nil) then
Problem.Show()
end
end
end
else
Problem.A[n] = 0
repeat
Problem.Solve1((n - 1), Total0, Total1)
Problem.A[n] = (Problem.A[n] + 1)
Total0 = (Total0 + 1)
Total1 = (Total1 + n)
until ((Total0 >= N) or (Total1 > N))
end
end
Problem.Solve = function(b)
Problem.A = {}
Problem.B = b
Problem.Checked = 0
Problem.Solve1((b - 1), 0, 0)
end
B = tonumber(arg[1])
if ((arg.n ~= 1) or (type(B) ~= "number") or (B <= 0)) then
write ("I need a base, B (and nothing more)\n")
else
Problem.Solve(B)
write ("Size of search space : " .. Problem.Checked .. "\n")
end

One final tweak would be to implement N-Wing's final point; fix `d`_{b - 1} (Problem.A[b - 1]) to 0.