The New Sudoku Players' Forum

[cmorpurgo]

You are right that you can sometimes specify 77 clues (all but 4) and have multiple (2, in fact) solutions; but 78+ clues always specify the solution uniquely. That multiple solutions need at least 4 gaps comes from the fact that, to have some freedom of choice for the values in all the gaps, you can't have any row/col/box with just a single gap in it.

On the other hand, you are wrong to suggest that, in any grid, you can always find 4 squares to delete in order to get two solutions. Here's a grid that won't let you do that:

Code: Select all

  { 1, 2, 3, 4, 5, 6, 7, 8, 9 },   /* no 4-sets */
  { 4, 5, 6, 7, 8, 9, 1, 2, 3 },
  { 7, 8, 9, 1, 2, 3, 4, 5, 6 },
  { 2, 3, 1, 5, 6, 4, 8, 9, 7 },
  { 5, 6, 4, 8, 9, 7, 2, 3, 1 },
  { 8, 9, 7, 2, 3, 1, 5, 6, 4 },
  { 3, 1, 2, 6, 4, 5, 9, 7, 8 },
  { 6, 4, 5, 9, 7, 8, 3, 1, 2 },
  { 9, 7, 8, 3, 1, 2, 6, 4, 5 }

Ok...we need to write to Wikipedia and tell them thet they say something wrong....http://en.wikipedia.org/wiki/Sudoku
they claim for "any variant" you can do that. Now, how did you come up with that particular grid? Also, what is then the minimum number of cancellations that will guarantee you at least two solutions for any grid?

Carlo

[Guest]

All I need is the answer to this one..

[Red Ed]

Ok...we need to write to Wikipedia and tell them thet they say something wrong....http://en.wikipedia.org/wiki/Sudoku
they claim for "any variant" you can do that.

I think Wikipedia's saying that the size of the puzzle, 9x9 or 16x16 or whatever, doesn't matter; you can still construct a grid for which the removal of some special set of 4 clues gives 2 solutions.

Now, how did you come up with that particular grid? Also, what is then the minimum number of cancellations that will guarantee you at least two solutions for any grid?

It's easy to code up something to search for a grid with no exchangeable sets of size 4 ("4-set", in short). I think I also tried creating a grid with no 4-sets and no 6-sets, but it didn't succeed before I got fed up and stopped the process. Interesting question, though.

[dukuso]

only 10 from the 416 bands are without unavoidable
of size<7. It's possible to do an exhaustive search, but it
would take me some time. One of the 23919 t-invariant
grids has all 6 bands from the 10, but there are 10 unavoidables
of size 6 nevertheless, they spread over band-borders.
Statistically it seems unlikely that there is such a grid

[LarryLACa]

... but the equivalence relation leading to the 44 gangsters is given by permuting any minicolumn independently of the others (together with column permutations within boxes, box permutation, and symbol permutation). So bands with the same ID belong to the same equivalence class.

I can see that we are using the withiin-minicolumn permutations. I don't understand why this works. The Sudoku solutions equivalence classes are defined by the 9! 2 6^8 symmetries. (no more/no less) I can't find a way to work from these to the represenatitive ID used for the within-minicolumn approach.

The example

Code: Select all

123 456 789  boxes--->123 123
456 789 123  2 & 3--->456 456
789 123 456  become:->789 789


belongs to the equiv. class identified by col tuples
{147}{258}{369}{147}{258}{369}
I don't understand why it's impossible than anyother equiv.class can't be buried in this ID permutation space. Maybe there are really 45 minimal equivalence classes (all with different N & Z numbers) and two of them just happen to fall wihtin the permutations space of
{147}{258}{369}{147}{258}{369}
I can see practically that this is not possible. All the results are consistent with the 44 gangsters.

That all the members of the Sudoku equiv.class fall wihin the permutation space is also clear. This is a sufficient constraint. I can't see why it's necessary that no solutions (from other equiv.classes) can't be in the space.

When Frazer/Bertram first showed the possible reductions of the top band, they were able to demonstrate a reduction to 71 equiv.classes, using allowed symmetries. What is the principal that allows us to use the 'packed' (Ed's usage) minicol id to sort down to the 44 essential ones?[When Ed confirmed the gang of 44 (and total count) he essentially counted through the 32688 band1 solutions for box2,3 and column permutations, storing counts under the mincolumn packed ID. After sorting and grouping, you get the gang of 44.]

Is that any clearer?

[Red Ed]

I still don't quite understand the question, so please bear with me while I ramble a bit in the hope of saying something illuminating.

There are two meanings of "equivalent" being used at the same time in this discussion:

1. Two examples of band 1 are counting-equivalent if they give rise to the same number of completions of the grid.

2. Two examples of band 1 are permutation-equivalent if you can get from one to the other by reordering the contents of minicols, reordering minicols within boxes, reordering boxes and/or relabelling digits.

It's clear(ish) that permutation equivalence implies counting equivalence. It just so happens that the converse is also true. I don't think anyone claims to understand why. [EDIT: what I really meant was: there's no proof, apart from grinding out the completion counts, that our set of ops in #2 above should succeed in capturing all aspects of counting equivalence, although the ops were chosen with the expectation that they were sufficient to do the job]

Finally, making that clear(ish) claim even clearer:

What is the principal that allows us to use the 'packed' (Ed's usage) minicol id to sort down to the 44 essential ones?

This is simply that, once band 1 is filled in, the only way it can affect completion of the grid is through column constraints. (Every other cell in the grid has to "look up" along a column to "see" the values in band 1.) So the only thing that matters in the band is the values in each minicolumn and not their order.

Hope something in that lot was of some use.

[frazer]

If I can add to Ed's point, Bertram and I realised even before running the program that our original reduction to 71 cases didn't use absolutely all the equivalences available. At that point, we only cared about reducing far enough that we could count in a reasonable time (and of course subsequent methods are much faster and better -- Ed, Guenter and Kjell and probably others have really pushed things further than we did). As Ed says, the only thing that matters as far as completing band 1 to a full grid is what numbers are in each minicolumn of band 1. If I can recall our method briefly, we reduce to 416 simply by using the permutations of rows and columns, together with relabelling; we then reduced to 174 using "counting-equivalences" (to use Ed's excellent terminology) coming from 2x2 rectangles, and then to 71 with more general 2xk rectangles. But there are counting-equivalences which don't come from any 2xk rectangle; I wrote one down once but can't find it at the moment... it is these additional ones which reduce us to 44.

So Larry's claim that we got down to 71 using allowed symmetries is probably not quite accurate; the 9! 2 6^8 symmetries (although there are rather fewer if you just use the top band, 9!x6^5) reduce you to 416. To get further, you need to use some version of the fact that counting-equivalences also come when all the minicolumns have the same numbers (we called this "duplication" in our article). Using the 9! 2 6^8 symmetries you might be able to specify a "representative ID" from within the 416, but you'll need more equivalences not coming from general symmetries to get down to the 44.

Finally, Ed's claim that counting-equivalence implies permutation-equivalence probably has no explanation. On the other hand, given the sizes of the numbers of completions (around 100000000 each), it would be quite a coincidence if two different band 1s had the same number of completions but weren't related by some permutation-equivalence...

[LarryLACa]

Thanks Ed/Frazer It had dawned on me (literally when waking up), that the problem was the 2 different types of 'equivalence' (as Ed stated)

I had been working from the 'classic' definition of symmetry equivalence: that members of an equivalence class can be permuted into each other by the allowed symmetries. (For Sudoku, the 9! * 2 * 6^8 symmetries.) Hence my problem in understanding the minicol permutation approach.

The dawning revealed that there is also a second type of equivalence:

..the only way it can affect completion of the grid is through column constraints.

If you group the top band configurations by the way they can affect the completion of the rest of the grid, you also get equivalence classes: Each member of the equiv.class will have the same (counting) set of completions because all contribute the same constraints to the lower bands.

By focusing on the band and not the direct Sudoku One-Rule constraints, we achieve an equivalent problem, but much easier to work with.

We can apply the same principle to the first stack (blks 147). The same gang of 44 will apply, just transposed and with a minor renumbering. Counting all the solutions is reduced to the 44^2 combinations of completing blocks 5689.

...Ed's claim that counting-equivalence implies permutation-equivalence probably has no explanation

Ed's explanation is very close to a proof - given the appropriate defintiion of equiv.class, namely counting-equivalent, which refocuses the problem on the constraints propagated outside the band. Of course to find 'real' (generating) members of the counting-equivalent classes you still need to enumerate through the Sudoku compatible permutations of the (top) band.

If I restate (Ed's) definition of the two type of equivalence slightly:

1. Two examples of band 1 are permutation-equivalent if you can get from one to the other by, (Larry: omit: reordering minicol contents), reordering minicols within boxes, reordering boxes and/or relabelling digits.

2. Two examples of band 1 are counting-equivalent if they give rise to the same number of completions of the grid, (Larry: add i.e. they can be reduced to a canonical representative by the permutation reorderings + reordering minicol contents.)

then the following is clear:

permutation equivalence implies counting equivalence. It just so happens that the converse is also true. . that [the] set of ops in [counting equivalence] should succeed in capturing all aspects of permutation equivalence,

Because we populate the counting-equivalence classes with all the permutation-equivalence members (deduced from the 9!*72*32688) they (the counting-equivalence) classes must capture all the permutation based combinations.

I think it is this pairing of the two equivalence types which provides the power to the T-Class band generation approach. We simplify the problem by using minicol content permutations and then at the appropriate points choose to use only Sudoku compatible members (gang of 44) when enumerating the solutions.

[Red Ed]

Now might be a good opportunity to notify people of changes happening on the Mathematics of Sudoku Wikipedia page.

Larry has added a lot of text and some nice pictures explaining the original enumeration method of Bertram and Frazer. It's not complete yet, but is certainly getting there. In the associated discussion page, I have outlined the newer method of Guenter and Kjell Fredrik.

Larry and I disagree, I think, on the proper purpose of the M.o.S. page. When I first set it up, I wanted the page to be a brief summary of the headline results, excluding detailed descriptions of any method. Larry appears keen to use this page to showcase various mathematical techniques on an attractive recreational problem. I can see the value of this, but would prefer detailed expositions of methods to go elsewhere, e.g. in a paper or a separate Wikipedia page.

If any of you have any opinions on this one way or the other, could you please add them to the M.o.S. discussion page. I don't mind if you side with Larry!

[Red Ed]

Ah, I just noticed this:

We can apply the same principle to the first stack (blks 147). The same gang of 44 will apply, just transposed and with a minor renumbering. Counting all the solutions is reduced to the 44^2 combinations of completing blocks 5689.

That's not right. Given a representative of band 1, one choice of B4/B7 is equivalent to another if you can get from one to the other by any combination of:

permuting values within minirows of B4 or B7
permuting the order of minirows within B4 or B7
swapping B4 and B7

You can't mess with B1 or do any symbol relabelling because this would, correspondingly, cause a change in B2/B3. And the grid completion (counting B5/6/8/9) depends on these boxes.

I've not bothered to work out how many classes this reduced set of transformations boils down to, but it's going to be a lot more than 44 ...

[LarryLACa]

Re:

We can apply the same principle to the first stack (blks 147). The same gang of 44 will apply, just transposed and with a minor renumbering. Counting all the solutions is reduced to the 44^2 combinations of completing blocks 5689.

vs:

Given a representative of band 1, one choice of B4/B7 is equivalent to another if you can get from one to the other by any combination of:

permuting values within minirows of B4 or B7
permuting the order of minirows within B4 or B7
swapping B4 and B7

You can't mess with B1 or do any symbol relabelling because this would, correspondingly, cause a change in B2/B3...

I realized I was being forward when I made the 44^2 assertion, but it seems to me to be true.
Part of the power of the 'counting equivalence' classes is that they do not require any relabeling in B1 to derive: Begin with the B1 labeling. Build the 9! 36288 band1 equivalence classes (with 72 members each) using

column permutations within B2, B3
B2,B3 block swaps

Identify these 36288 by their minicol counting equivalence ids, sort and group by the counting equivalence IDs and to get the 44 generating classes and sizes (each of which needs to be multiplied up by 72 later).
[Edit: chg /32688/36288/ typo. Also: I have misrepresented the consolidation to 44 gangsters here. Grouping by minicol counting equiv. ID only reduces the 36288 classes to 22266 (not much at all). Reduction to 44 requires application of B1 relabeling to construct alternate counting equivalent IDs for the same g44 class. See Ed's and Dukuso's reply below, and my 12/23 posts.]

I believe the same derivation can be applied to the first stack: the constraints of each stack1 row on the B5689 blocks depend only on the stack minirows. The counting equivalence of the stack permutations is not based on being able to permute between them but solely on their constraints for B5689. The equivalence is a 'taxonomical' association (grouping) based on similar constraints.

Given a fixed B1 numbering there are 56 * 6^6 valid permutations for band1. The same applies for stack1. There are 72 B4,B7 permutations for within band row swaps and the block (band) swap, which produce 36288 equivalence classes each of size 72. These 32688 permutations can be grouped by their minirow counting-equivalence IDs, to produce counting-equivalence classes. How could this produce anything other than 44 counting-equivalence classes?

What did I miss? I'm unearthing my compiler and will try this out eventually. If anyone can disuade me from this folly in the meantime, I'd be grateful.

[dukuso]

are you asking for the number of G-classes of B12347s ?
We had done this, see the archive.. (sorry, I don't have it handy)
I think it was 2865. Yes, search for 2865 in the archive


the 44*44 figure doesn't work because you can choose one of
the 3 blocks in B123 to build the B47 upon.
But the G-equivalence would allow permuting the blocks.

[LarryLACa]

Now might be a good opportunity to notify people of changes happening on the Mathematics of Sudoku Wikipedia page.

Larry has added a lot of text and some nice pictures explaining the original enumeration method of Bertram and Frazer. It's not complete yet, but is certainly getting there. In the associated discussion page, I have outlined the newer method of Guenter and Kjell Fredrik.

Larry and I disagree, I think, on the proper purpose of the M.o.S. page. When I first set it up, I wanted the page to be a brief summary of the headline results, excluding detailed descriptions of any method. ...

If any of you have any opinions on this one way or the other, could you please add them to the M.o.S. discussion page.

Any/All contributions/comments are most welcome at M.o.S. or M.o.S. discussion

I must confess, I have indeed hijacked the 'headline summary' usage for a more explanatory one. The Wikipedia article has a leading table of contents. If you want headline summary, it's not hard to find.

One of the shortcomings of this forum is that it's hard to see the current state of discussion, if you haven't been following along or find a particular issue, even with the search capabilities. I was hoping to use M.o.S. to provide a structured summary of our results and reasoning, hence my inclination to be verbose (there). The public article format also allows us to build out readable content (collaboaratively) as we go, instead of just knotting (Ariadne's) threads as we do here.

Dukuso, KJell, et.al. contributions (there) are always welcome. Wiki is always a work in progress.

[dukuso]

can't you do both,

a short summary without many proofs and examples, just the results

AND

a more extensive survey ?


on different pages with links to each other

[cole07]

how are you guys getting such large numbers?

I'm doing the math and it's not going to need a power...


9 8 7|6 5 4|3 2 1
_ _ _|_ _ _|_ _ 1
_ _ 1|_ _ 1|_ _ 1

_ _ _|_ _ _|_ _ 1
_ _ _|_ _ _|_ _ 1
_ _ 1|_ _ 1|_ _ 1

_ _ _|_ _ _|_ _ 1
_ _ _|_ _ _|_ _ 1
1 1 1|1 1 1|1 1 1

these is what I have so far... they are the numbers of options you have.
the 1's in the 3X3 are because you only have 1 option left after filling the other 8... and the 1's on the end of the 1X9 & 9X1 are because you only have 1 option left after filling each other 8.

that's 65 ways + each _ spot ... I'll get back on the final number
why do you think it's so big? Am I missing somthing