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 0 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 : di) = 10). So, if values are chosen for digits d9 to d1, there is only one possible valid value for d0 = 10 - (+ : 0 < i < 10 : di). This reduces the search space by a factor of 10. (If the computed value for d0 is negative, then the chosen values for d9 to d1 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 di multiplied by their position in the string i must be 10, i.e. (+ : 0 ≤ i < 10 : (i * di)) = 10. Since 0 * x = x for all x, this expression is equivalent to (+ : 0 < i < 10 : (i * di)) = 10. d1 can be isolated from the equation, d1 = 10 - (+ : 1 < i < 10 : (i * di)). This reduces the search space by another factor of 10. (Again, if the computed value for d1 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 * di) ≤ 10. This leads to the third optimisation (also suggested by N-Wing): instead of checking every digit di with values 0 to 9, check di with values 0 to floor(10 / i). d9 cannot be 2 or greater, because then (9 * d9) > 10 so (+ : 1 < i < 10 : (i * di)) > 10. Similarly, d8, d7, and d6 cannot be 2 or greater. d5 and d4 cannot be 3 or higher, d3 cannot be 4 or higher, and d2 cannot be 6 or higher. This reduces the search space to 2 * 2 * 2 * 2 * 3 * 3 * 4 * 6, or 27 * 33 = 128 * 27 = 3456.
This final optimisation can be pursued even more aggressively, in that, for example, at most one of d9, d8, d7, and d6 can be 1 (because if d7 and d6 were both one, 7 * d7 + 6 * d6 = 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 db - 1 (Problem.A[b - 1]) to 0.