2100010006 (idea)

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 : d_i) = 10). So, if values are chosen for digits d₉ to d₁, there is only one possible valid value for d₀ = 10 - (+ : 0 < i < 10 : d_i). This reduces the search space by a factor of 10. (If the computed value for d₀ is negative, then the chosen values for d₉ to d₁ 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₁ can be isolated from the equation, d₁ = 10 - (+ : 1 < i < 10 : (i * d_i)). This reduces the search space by another factor of 10. (Again, if the computed value for d₁ 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₉ cannot be 2 or greater, because then (9 * d₉) > 10 so (+ : 1 < i < 10 : (i * d_i)) > 10. Similarly, d₈, d₇, and d₆ cannot be 2 or greater. d₅ and d₄ cannot be 3 or higher, d₃ cannot be 4 or higher, and d₂ cannot be 6 or higher. This reduces the search space to 2 * 2 * 2 * 2 * 3 * 3 * 4 * 6, or 2⁷ * 3³ = 128 * 27 = 3456.

This final optimisation can be pursued even more aggressively, in that, for example, at most one of d₉, d₈, d₇, and d₆ can be 1 (because if d₇ and d₆ were both one, 7 * d₇ + 6 * d₆ = 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.