I am interested in a different sort of minimalization. Of course, I am talking only about valid clue sets -- those which are complete (generate a unique solution) and non-redundant (if any clue is removed, there will now be multiple solutions).
Question 1. Is it possible for a valid clue set to have 0 occurrences of any digit (e.g. no 4's among the clues)?
Question 2. Is it possible for a valid clue set to have 0 occurrences of two (or more) digits (e.g. no 4's and no 7's)?
The answer to question 1 is yes. These occur all the time in the newspaper puzzles.
The answer to question 2 is no. If, for example, there are no 4's and no 7's, then, as soon as you find a solution, you can generate a second solution by replacing all the 4's with 7's and vice versa.
Question 3. Given that we are minimizing (in some sense) by having 0 occurrences of some digit, can we then minimize further by having just 1 occurrence of some other digit (e.g. no 4's and only one 7)?
The answer to question 3 is yes. I have seen these in newspapers.
Question 4. Can we have 0 occurrences of some digit, and just 1 occurrence of each of two (or more) other digits (e.g. no 4's, only one 7, and only one 9)?
Here's where my answers run out.
Define the Smythe number of a valid clue set as the 10-digit number formed as follows:
A. The leftmost digit is the number of digits (1-9) with 0 occurrences in the clue set.
B. The next digit is the number of digits (1-9) with 1 occurrence.
C. The third digit is the number of digits (1-9) with 2 occurrences.
V
V
V
I. The second-to-last digit is the number of digits (1-9) with 8 occurrences.
J. The rightmost digit is the number of digits (1-9) with 9 occurrences.
For example, for the following clue set (taken from another post in this forum):
- Code: Select all
+---+---+---+
|...|...|...|
|...|...|.12|
|..3|.45|...|
+---+---+---+
|...|6.1|.7.|
|..4|...|6..|
|..5|8..|...|
+---+---+---+
|...|.3.|4..|
|.1.|2..|...|
|.7.|...|...|
+---+---+---+
-- the Smythe number is 1152000000. There is 1 digit with no occurrences, 1 with one occurrence, 5 with two occurrences each, 2 with three occurrences each, and none with four or more occurrences.
I am interested, then, in maximizing the Smythe number (corresponding to minimizing, in some sense, the clue set).
I suppose one could also become interested in minimizing the Smythe number (maximizing the clue set).
Here are some elementary observations:
101. The sum of the digits of the Smythe number is always 9.
102. 0 times the first digit, plus 1 times the next digit, plus 2 times the third digit, plus .... plus 9 times the last digit, adds up to the number of clues in the clue set.
103. The first digit is always 0 or 1 (questions 1 and 2 above).
104. The last digit is always 0. (If there were nine occurrences of any digit, you could remove one and still have a unique solution to the puzzle.)
105. Given that the first digit is 1, can the second digit be 2 or more? (This is question 4, unanswered as of right now).
Who can maximize the Smythe number? I'm guessing that the above example, 1152000000, is about as good as it gets, as there are only 17 clues in the clue set.
Bill Smythe
