The New Sudoku Players' Forum

[kjellfp]

Dr Brandon Zeidler's argument, if correct, would work for the nxn case. His argument would give a formula for the minimum number of clues.

He only gives a lower bound, never a claim about the actual limit. In the 2x2-case and 3x3-case, this coincides with the actual minimal number of clues (provided 17 is the minimum for 3x3), but there's no reason this should hold all the way up. This is often common, that when a bound B(N) is the actual limit for small values of N, the same formula gives bounds only, not the answer, for higher N.

If 85 is the minimal number of clues found, and Dr Zeidler's method gives 44 as a bound, there are several possible explainations to this:

- 44 is the minimum, but no example has been found yet
- The minimum is greater than 44.
- Zeidler's method only holds up to 3x3-grids
- Zeidler's method is wrong

Personally, I find the second statement to be the most reliable.

I'm only waiting for a simpler explaination of Zeidler's method, or an independent confirmation from someone who understands this matter. I'm originally a mathematician myself, but have almost no knowledge about communication theory. Actually, this thread alone has encouraged me to read and learn about it.

[Moschopulus]

Thanks for your correction, I edited the previous rubbish.

I would attempt to explain the argument if I could. I don't understand what Dmin is. I asked for clarification but have not received any yet.


The starting point is to consider the set of all vectors of length 81 whose entries are digits 1-9. There are 9^81 such vectors.

In this subject the distance between two vectors is the number of places they are different (called Hamming distance).

The set of all valid sudoku grids is a subset of approx 6.67e21 vectors. Often one is interested in knowing the minimum of all the distances between elements in a subset like this. In our case of sudoku grids, the minimum distance is 4 (because of size 4 unavoidable sets). Sometimes people denote the minimum distance by Dmin.

Nothing new so far.

This minimum Hamming distance appears in the Singleton bound, which is being applied in Dr Zeidler's post. At this point I am confused because Dr Zeidler says that Dmin + Cmin = 81. That is why I asked for clarification about Dmin. Dr Zeidler seems to use Dmin to be something else. I'm not even sure if he is considering the set of all sudoku grids or not, I'm just guessing. Perhaps there is a different Singleton bound to the one I know.

--------------------------

I think it is nice to think of sudoku as an erasure problem. Suppose you have a vector (a sudoku grid say) and you erase some entries. Can you recover the original vector? Well, if you knew that your original vector belonged to a certain subset of vectors, and if you knew that any two vectors in the subset differed in at least 65 (say) entries, and if you erased fewer than 65 entries, then YES, you could recover the original. There is only one vector in that subset that you could have started with.

Dr Zeidler seems to be applying this to the subset of all valid sudoku grids (I'm not sure about this, I'm only guessing). If the set of all grids had minimum distance 65, we would be very happy. Unfortunately the set of all grids has minimum distance 4.

[coloin]

It's a good idea to check the method on the 2x2 case!

Well... if you take Dr Z literally......which I was

It is not surprising that very few of these permuations would have a unique solution without filling in more of the squares. There are probably at least a few permutations that are uniquely determined by *only* these 3*9=27 squares, but this isn't that important, so long as there is at least one solution.

There are only 288 fillings where "there is at least one solution"
Therefore I think 288 is more correct than 4!^2........

I was beginning to think Dr. Z was spoofing...

I think that you are doing him an injustice!

I disagree - I have generously but naively given him more credit than many.......which is OK in my book

[Wolfgang]

I really dont understand your hope that communication theory would be able to help essentially for sudoku problems. I still think that it is simply not applicable for them. Note: the number of solutions of sudokus with filled diagonal boxes varies somehow between 100000 and 300000 solutions. [Reformulated:] Only the number of possible fillings went into the "proof". This is nothing but useless information and no theory in the world can conclude something of worth from it.

[PatmaxDaddy]

If Dr Z comes back he will explain.......

I hope Dr Brandon Zeidler replies to our questions about his proof.

Perhaps Dr Z would come back if the general tone in this thread were a tad more gracious. He may be on to something, or he may not (I have no idea), but he has started a good discussion. Even if his proof turns out to be misguided, it may still teach something, and it's not like we are overflowing with ideas on how to prove the 17-clue conjecture. My bet is that he does know something about his field, and perhaps a more civil critique would be very constructive. I understand that people feel free to flame away on the Internet, but personally I've never cared for it.

[Edit: I didn't mean these remarks to be directed at coloin or Moschopulus, I quoted them to provide context.]

[Wolfgang]

This proof is rubbish and its as probable as the 17 clue minimum, that the author knew that. So what ?

[LarryLACa]

I assume everyone knows this is the wild, wild west of open web blogs. Trolls with daggers are known to exist. As for me, I polish my armer daily, smile at the added colour , and grant them all the attention they deserve.

Larry,
temporarily off track in Kansas

BTW: Nice work DrZ, I'm learning

[Pat]

In the 4x4 case--- There were posts a while back looking for the minimum number of clues in 16x16 sudoku, and a puzzle with 85 clues was already hard enough to find. I don't believe one was found with fewer than 80 clues. (What is the lowest known?)

for box-size 4x4,
dukuso (2005.Sep.2)
showed 2 examples with 83 clues

http://www.setbb.com/phpbb/viewtopic.php?p=1458&mforum=sudoku#1458

perhaps the increased interest will prompt him to renew the search?

~ Pat

[dukuso]

I checked my old files and there should be at least
3 16*16s with 82 clues in them.

[gsf]

I checked my old files and there should be at least
3 16*16s with 82 clues in them.

here's a minimal 81 via sudocoup (with unique turned on this time)
its easy (to solve) and fell out in the first 10 of a batch of 100

Code: Select all

67.9|....|...8|..D.
..1A|F.82|....|B.3.
.E.B|...7|.9..|1...
8.2C|..63|1...|..94
----+----+----+----
.D7.|8...|6..9|..1.
.6..|.F..|...7|84..
32..|.1..|....|.5..
.48.|....|...5|3..2
----+----+----+----
1...|.7..|4.2.|.C..
..G.|563.|.8..|....
.3..|24.1|..7.|5...
9..5|....|....|....
----+----+----+----
7...|.548|.21.|...3
.5..|....|..4.|G...
....|....|3...|F62.
....|A.1.|..6.|..7.

6739|1E54|BCG8|A2DF
5G1A|F982|76D4|BE3C
4EDB|CGA7|F932|1856
8F2C|DB63|1A5E|7G94
----+----+----+----
AD7F|8325|64C9|EB1G
B651|EFGD|23A7|84C9
329E|417C|8FBG|65AD
C48G|9AB6|D1E5|37F2
----+----+----+----
1AF6|B7DE|4523|9CG8
2CG7|563F|A89B|D14E
D3E8|2491|CG76|5FBA
9B45|G8CA|EDF1|2367
----+----+----+----
79BD|6548|G21F|CAE3
E562|3CFB|974A|GD81
G1A4|7DE9|3B8C|F625
F8C3|A21G|5E6D|497B


[dukuso]

what's sudocoup ?

[gsf]

what's sudocoup ?

aha, been away for a while
announced on the programmer's forum
http://www.setbb.com/sudoku/viewtopic.php?t=612&highlight=&mforum=sudoku
and here
http://forum.enjoysudoku.com/viewtopic.php?t=3009&highlight=

sudocoup is my answer to sudoku+DLX is great

[gsf]

I checked my old files and there should be at least
3 16*16s with 82 clues in them.

clue distribution for a collection of 10K minimal 16x16's 11/sec/Ghz generation rate
I didn't canonicalize so there could be dups

Code: Select all

   1 77
   2 78
  11 79
  62 80
 200 81
 521 82
 985 83
1622 84
2062 85
1836 86
1357 87
 773 88
 385 89
 140 90
  36 91
   5 92
   2 93


[sudosa]

regarding the 'proof' let me say 2 words: though I have no proof that this is not one, it most certainly is not. theorems such as the ones used have a lot of technical assumptions. his 'proof' can probably be made into one showing that the average number of minimums necessary is at least 17... Dr Zeidler could at least now answer to gfroyle's remarks before we search for the possibility that his 'proof' be made into one. I would even challenge him regarding his understanding of mathematical accuracy in contrast to his ability of seeing applications..anyway he's made it into deep waters, so let's see him swim!

[Smythe Dakota]

What about maxima, instead of minima? (Please excuse me if this information is already buried in the extensive responses which I only skimmed quickly.)

Define a set of clues as a "basis" if (1) it generates a unique solution, and (2) no proper subset of it generates a unique solution.

1. Do all bases for the same (solved) puzzle have the same number of clues?

2. For which integers n (n=0 through n=81) do there exist at least one puzzle/basis where the basis has size n?

Bill Smythe