A different sort of minimalization

Everything about Sudoku that doesn't fit in one of the other sections

A different sort of minimalization

Postby Smythe Dakota » Sun Mar 19, 2006 3:27 pm

There has been a lot of talk in these forums about maximizing and minimizing the number of clues. As I recall, the current conjectures are around 34 (maximum) and 13 (minimum), although I may be mis-remembering.

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
Smythe Dakota
 
Posts: 536
Joined: 11 February 2006

Postby Red Ed » Sun Mar 19, 2006 8:02 pm

There are eight 1322100000 in this list. I won't spoil your fun by pointing out which they are, though.

On the flipside, there are also five 0180000000.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby coloin » Sun Mar 19, 2006 8:12 pm

Max number of clues is now 35

Courtesy of Ocean
Code: Select all
+---+---+---+
|1.3|..6|78.|
|78.|12.|45.|
|4..|7..|1.3|
+---+---+---+
|2.1|.64|8..|
|.6.|.9.|..1|
|8..|2..|5..|
+---+---+---+
|3.2|645|...|
|64.|.7.|...|
|...|..2|...|
+---+---+---+

This gives 0102240000
coloin
 
Posts: 1662
Joined: 05 May 2005

Postby Smythe Dakota » Mon Mar 20, 2006 7:13 am

Is it possible to have a non-zero in the second-last digit, i.e. is it possible to have a (non-redundant) clue set where one digit appears 8 times?

Going further, is 1111111110 possible? (There would be 36 clues.)

Bill Smythe
Smythe Dakota
 
Posts: 536
Joined: 11 February 2006


Return to General