Re^3: Golfing cryptosums

To each his own.

Your analysis helps me realize that even as a kid, I was always more interested in the relationship between things than in the one and only solution to things. To me it hardly matters whether there are 0, 1, or many solutions to a problem. In the case of cryptosums, I'm fascinated by the fact that the mere arrangement and repetition of symbols provides enough information to deduce (a) whether or not a mapping between those symbols and the set of digits exists and (b) whether or not that mapping is unique.

How did you come up with those figures? According to this article, determining whether or not a solution even exists for a particular puzzle is NP-complete (if we allow for bases other than 10). Other than limiting the problem space to 10! possible mappings, how does limiting the problem to base 10 help one determine the potential number of puzzles with solutions, let alone the number of puzzles with unique solutions? Can you determine the number of problems without knowing exactly which particular puzzles will have solutions? Or did you use brute force to count the number of solutions for each puzzle?

Best, beth

Update: clarified question.

Comment on Re^3: Golfing cryptosums

Replies are listed 'Best First'.
Re^4: Golfing cryptosums by Anonymous Monk on Aug 11, 2009 at 08:32 UTC
Instead of constructing an equation at random and then converting it into a puzzle, one can also just construct a random puzzle (but don't let yourself use more than 10 different letters). Here are your odds of success with that route: Digits Number of puzzles 1 31,200 with unique solutions 37,102 with no solutions 406,250 with 4..32 solutions 474,551 total puzzles 2 10,795,200 with unique solutions 1,990,652,352 with no solutions 6,339,278,400 with 3..476 solutions 8,340,725,952 total puzzles 3 33,433,717,226 with unique solutions 6,746,392,175,276 with no solutions 139,816,773,439,850 with 2..1200 solutions 146,596,599,332,352 total puzzles 4 1,974,825,396,897,600 with unique solutions 240,014,957,704,387,2?? with no solutions 1,147,855,057,502,310,0?? with 2..3840 solutions 1,389,844,840,603,594,8?? total puzzles 2,576,581,829,865,418,742 total random letter choices 1,186,736,989,261,824,0?? with over 10 different letters Digs Uniq None Dupl Max 1 6.57% 7.82% 85.61% 32 2 0.13% 23.87% 76.00% 476 3 0.02% 4.60% 95.38% 1200 4 0.14% 17.27% 82.59% 3840 [download] And I suspect the odds just get worse after this. (And note that the numbers have gotten too complicated for both Perl and me toward the end there so don't use these for life-and-death calculations.)	[reply] [d/l]

Replies are listed 'Best First'.

Re^4: Golfing cryptosums
by Anonymous Monk on Aug 11, 2009 at 08:32 UTC

Instead of constructing an equation at random and then converting it into a puzzle, one can also just construct a random puzzle (but don't let yourself use more than 10 different letters). Here are your odds of success with that route:

Digits       Number of puzzles
  1                     31,200 with unique solutions
                        37,102 with no solutions
                       406,250 with 4..32 solutions
                       474,551 total puzzles

  2                 10,795,200 with unique solutions
                 1,990,652,352 with no solutions
                 6,339,278,400 with 3..476 solutions
                 8,340,725,952 total puzzles

  3             33,433,717,226 with unique solutions
             6,746,392,175,276 with no solutions
           139,816,773,439,850 with 2..1200 solutions
           146,596,599,332,352 total puzzles


  4      1,974,825,396,897,600 with unique solutions
       240,014,957,704,387,2?? with no solutions
     1,147,855,057,502,310,0?? with 2..3840 solutions
     1,389,844,840,603,594,8?? total puzzles

     2,576,581,829,865,418,742 total random letter choices
     1,186,736,989,261,824,0?? with over 10 different letters

Digs   Uniq     None     Dupl    Max
  1    6.57%    7.82%   85.61%    32
  2    0.13%   23.87%   76.00%   476
  3    0.02%    4.60%   95.38%  1200
  4    0.14%   17.27%   82.59%  3840
[download]

And I suspect the odds just get worse after this. (And note that the numbers have gotten too complicated for both Perl and me toward the end there so don't use these for life-and-death calculations.)

[reply]
[d/l]