The New Sudoku Players' Forum

[coloin]

I was reasessing a way to describe B1B2B3 similar but ? different to Red Eds in an effort to combine a horizontal and a vertical "shute. However I am getting an idea that the way Red Ed compressed his equivilents that they will not be meaningful when crossed with another in a B1B2B3/B1B4B7 pattern. Maybe they are valid - afterall they all have the same number of completions therefore they are equivilent ??????

I have looked at the 17 and I got stuck at first. It is really difficult representing the shutes - and not make a mistake.

It does envolve transposing and reflecting and more transposing.

My initial analysis of Gfroyle's 17

639 241 785
284 765 193
517 983 624

123 857 946
796 432 851
458 619 237

342 178 569
861 594 372
975 326 418

goes to

123 468 957
456 917 832
789 352 146

842 xxx xxx
931 xxx xxx
675 xxx xxx

264 xxx xxx
518 xxx xxx
397 xxx xxx

Horizontal shute of Gfroyle's 17 grid

123 468 957
456 917 832
789 352 146 What gang member is this ?

Vertical shute of Gfroyle's 17 - made horizontal

123 698 457
456 273 819
789 415 263 ? what gang member is this

I keep getting different numbers - one time it appeared they were from the same gang. If this is true that is a bit of a coincidence !!!!!!!!!!!!!!!!

Red Ed will give us the definitive Im sure. I looked up Frazers 36288 long list of all completions - but still found it difficult to see what member they were. I could easily have made an error in rearranging etc.

The point of this, of course, is to find "tight" grids. Perhaps a grid with a low number of completions at the B1B2B3B4B7 stage. Maybe similar grids crossed with one another are tighter - that might make sense.

I will reasess a perhaps better way to represent B1B2B3 - it may not be relevant now - but it would perhaps be easier !.

[coloin]

The 44 that Red Ed published are indeed representative of what happens perpendicularly - therefore crossing the members will give us information - possibly useful !

I have done a SIMPLE crossover study on the B1B2B3B4B7 boxes in the 17 grid from Gfroyle. I gave up on working out which two of the gang of 44 it was derived from. It was too difficult.

639 241 785
284 765 193
517 983 624

123 857 946
796 432 851
458 619 237

342 178 569
861 594 372
975 326 418

Now given my previous posts about what clues are necessary
ie the ones marked x - if all the 54 xs are valid then the original valid sudoku self completes by logic. [The os are unfilled]

ooo xxx xxx
ooo xxx xxx
ooo xxx xxx

xxx xxx ooo
xxx xxx ooo
xxx xxx ooo

xxx ooo xxx
xxx ooo xxx
xxx ooo xxx

[actually you an get it down to 48 xs if you have 6x8 clues]

This is the grid semicompleted [Box one is irrelevant]
639 241 785
284 765 193
517 983 624

123 xxx ooo
796 xxx ooo
458 xxx ooo

342 ooo xxx
861 ooo xxx
975 ooo xxx

You need to work out the number of ways to fill Box 5 and Box 9.

Now how many of these two will fit together - it cant be many.

-There are always only 5 numbers which come up when you work this out for each box. Which is it for this grid ?

"given boxes B2 and B4 without B1 there are 384, 392, 400, 432 or 448 solutions for B5 in the ratios 27:54:162:1:36 giving my average of 403.2. "

It must be something to do with Red Eds data
In B2B4 there are 8 different equivalent ways to complete the first column - from column 4 -

In B2 the equivilent of

689
127
354 occurs 25 times out of 44.


There are rather more for B3B7 - which makes me think this is the more important variable.

If we can find a grid which has a low count of many of the crossover junctions then this will be a tight grid.

[Pat]

Code: Select all


5 . 2  . . .  4 . . 
. . .  7 1 .  . . 3 
. . .  . . .  . . . 

. . .  . . 4  6 . . 
. 7 .  2 . .  . . . 
. 1 .  . . .  . . . 

6 . .  . . 2  . . . 
. . .  . 3 .  . 1 . 
4 . .  . . .  . . .



is interesting, because it has only 16 clues. It CANNOT be uniquely solvable, because it is missing both 8 and 9, and so they can always be exchanged in any final solution.

But, this turns out to be the only problem - the puzzle has exactly TWO solutions...

so gfroyle has found the elusive 16,
at least the way Hammerite suggests.
congratulations! i'll bet a 15 can be found the same way.
- Pat

Clearly if there are 7 clues in the grid, then at most 7 of the 9 symbols will appear in the initial grid. Then at least 2 of the symbols do not appear in the initial grid. Clearly in any solution of the grid, the grid produced by the transposition of the 2 non-appearing symbols is also a solution. However, can it really be called a different solution? The two symbols are, by virtue of not being in the grid, invented by us, the solvers, and so if all that changes is that we transpose them, while keeping their respective locations the same, we may decide that the two solutions are in fact equivalent.

[udosuk]

Unfortunate what we want is probably a 16-clue valid sudoku grid that can only yield a single solution grid... or prove of it's impossibility. But that was really a remarkable result too... especially if it's the unique one (barring transformation). I had a lot of fun solving it.

[sciguy47]

I figure there is a way to acually find out the minimum number of clues to a valid Sudoku.

Starting with a blank grid, place a single number onto the grid. This action will reduce the number of compatible solution grids by a calculable amount. Add another number, and you decrease the number of valid solution still further. If you place the numbers such that they invalidate as many solutions as possible, you can repeat this until you have only 1 solution, which contains the minimum # of clues.

[gfroyle]

If you place the numbers such that they invalidate as many solutions as possible, you can repeat this until you have only 1 solution, which contains the minimum # of clues.

This is known as a "greedy algorithm" in that you always make the move that seems to make as much progress towards the goal as possible.

Unfortunately, it is well known that greedy algorithms only work in a very limited range of situations, and this is certainly not one of them.

In general, the grid with the minimum number of clues may look quite "bad" right up to the very end, when a final carefully chosen clue drops the number of possibilities from lots down to just one...

[coloin]

Yes - I think that is right G - It is the last clue which does all the damage in reducing the number of solutions. But the effect of that last clue is dependant on all the preceeding others.


You can have multiple solutions right up to the penultimate clue and on insertion of the last clue - the completions work around the board - just keeping going- resulting in one unique solution.

Analysing furthur the Boxes 12347 [G no 2 17 grid - rearanged !]

123 468 957
456 917 832
789 352 146

842 xxx xxx
931 xxx xxx
675 xxx xxx

264 xxx xxx
518 xxx xxx
397 xxx xxx

- there are 2804 solutions
- a grid picked at random gave 2611 solutions
- average overall is 2693 solutions

So assessing the grid this way contributes little.

I dont think looking for a form of tight grid is going to be easy as each box in the sudoku grid effectivly is a box 5 and interacts with 4 other pairs of boxes. The determinents are predictable in one plane - but unpredictable in the other plane - at rightangles.So to analyse whether a grid is "tight" or not is fairly difficult.
The determinents at right angles are one of 5 numbers [ 384, 392, 400, 432 or 448 solutions - apparently it is "quite easy to show this." - although I have difficulty doing so ! [The average ratios apparently are 27:54:162:1:36].

So each B5 box would have 4 calculatable values for the perpendicular eg B2B4 interactions [therefore 36 per grid] [Each box can be box-swapped to box 5]

A grid with a higher ratio of 384s is bound to be a grid with more constraints.

How about we analyse Gs 17 grid and compare the relative frequencies - [as above - if these are indeed the average].

If this is the case and the 17 grid comes out specifically with significantly lower amount of 384s - then knowing what is important - we might be able to find a slightly "better" grid to work on.

[frazer]

In response to coloin, it takes a little thought to persuade yourself that there are 5 classes of constraints; then a computer determines all of the values 384,...,448. Let's assume that we are trying to count the number of ways to complete

??? ***
??? ***
??? ***
123
456
789

where we are given all the *, and want the ?. The situations are:

(1) The three rows of * have the same numbers as the three columns (in some order); for example, 147/258/369, or 825/417/693 [432 ways to fill in the ?].
(2) One of the three rows has the same numbers as a column, but the other two have just two; e.g., 147/259/368 [384 ways].
(3) All three rows have two numbers from a column; e.g., 148/259/367 [392 ways].
(4) Two rows have two numbers from a column, but the other has just one; e.g., 143/256/789 [400 ways].
(5) All three rows have one number from each column; e.g., 123/456/789 [448 ways].

It takes a little thought to convince yourself that there are no other possibilities. Of the 18 pairs of blocks in Gordon's grid, we have:

B1vB5: (4), B1vB6: (4), B1vB8: (4), B1vB9: (4), B2vB4: (4), B2vB6: (4), B2vB7: (2), B2vB9: (4), B3vB4: (5), B3vB5: (4), B3vB7: (4), B3vB8: (4), B4vB8: (3), B4vB9: (4), B5vB7: (5), B5vB9: (4), B6vB7: (4), B6vB8: (3).

Rather than 27:54:162:1:36 for 384,...,448, we have 1:2:13:0:2, averaging 403.56, a little higher than overall average 403.2!

[coloin]

Thank you for that - very well explained.

My theory appeared hopeful - but has failed miserably in practice. Gfroyle's 17 grid is a very average grid by this account.

But it is very far from average - you can fill out a series of 17 numbers [at least 29] from G's grid and superimpose them over each of the 6*10^21 sudoku grids and it only fits this one grid.

The average number of solutions from 17 numbers is well over 50000.

Can anyone explain this situation ?

[dukuso]

we could calculate the minimum number of clues
which must be in each chunk .
I assume it's 4 ? That was the minimum with Gordon's 450
puzzles, which I downloaded.
Or has anyone ever seen a sudoku with only 3 clues
in one 3*9-chunk ?

There are only 416 classes of chunks, 44 essentially different,
with 96 to 1728 chunks in each class to be separated by
the 4 clues, so that looks doable....

[coloin]

I think there are a very large number of ways to populate a grid with 16 numbers.
I am trying to get an idea of the possibilities

Yes it looks like a minimum of 4 in each chunk/chute - but I dont see how breaking it down to 416 or 44 helps.[yet]

It also looks like we more likly to get a result if we go for a common formation using 8 numbers in 8 boxes - maximum 3 in a box eg 322222210.
Of course thats to come up with an easy logical solution like Gfroyles17s - perhaps I am thinking of a 16 solution which superficially looks to have many solutions, but turns out to be an "almost impossible" sudoku by definition but in fact has only one solution by guess logic. I have no idea whether this should conform to a Gfroyle 32222210 formation pattern or somthing obscure like 522221110.

Eg the number of ways to get 16 hints from one valid sudoku is 81!/65! = 7*10^29 - and thats only from one grid - admittedly each of these supposedly has over 200,000[guess] solutions - so it is no wonder we havnt found a 16 which has only one solution.

But we do have a grid which has 29 unique 17 clue formations - these formations dont superimpose over any other sudoku.

I am working through an estimate of the number of ways to fill in 16 clues with the constraints above ie 8 numbers, max 3 ? to a box,[ ? minimum 4 to a chute].

If we do find a 16 grid which is unique - it turns out to have one solution - we might have found the hardest sudoku EVER.

I cant help feelin that we are only going to get the answer by cataloging the N grids and looking at them all in quest for a unique 16 clue formation hidden in only one of the grids.

Once we have done this we can all give up and go on to something else !

Regards

[dukuso]

I just want to give an example, where we can easily prove that
18 clues are needed. I don't know if this has already been
mentioned.
It's the most canonical sudoku-grid
A(i,j)=1+(3*((i-1)%3)+(i-1)/3+j)%9) (hope I got it right)

123456789
456789123
789123456
234567891
567891234
891234567
345678912
678912345
912345678

used by Yato+Seta in the proof that sudoku is NP-complete
by reducing it to QCP.

In this grid each chunk clearly needs 6 clues for a unique solution
e.g. you can replace

1..4..7..
4..7..1..
7..1..4..

by any latin square in 1,4,7 for a valid sudoku. So these 9 cells
must contain at least 2 clues for a unique solution.
But the whole grid is partitioned into 9 such 3*3 latin squares.


Guenter.

[coloin]

Yes - one would need to generate those 18 clues at some stage to define the grid.

The point I am making is that if you find a formation of 17 [or 16] clues within your canonical sudoku-grid - which are unique to that grid [unlikly I admit] - then you have defined the grid in less than 18 - no other grid will fit.

We have a grid - Gfroyles 17 - which has got many unique formations of 17 clues - and there are very many more formations than N [Bertram] .

On the task of looking at all grids - we probably would "only" need to analyse all of Red Ed's unique grids - thats certainly more doable !

[gfroyle]

.
Or has anyone ever seen a sudoku with only 3 clues
in one 3*9-chunk ?

Code: Select all

6 5 0  0 0 0  0 0 0 
0 0 0  0 0 9  0 0 0 
0 0 0  0 0 0  0 0 0 

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

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


Yes... easy to find, but obviously not what you were looking for!

The problem with this problem is that there is a great deal of hidden interaction between the parts of the puzzle which basically makes it almost impossible to do this kind of "reduction" - any time you try to say something about the minimum number of clues required in some part of the puzzle it doesn't work because you can always replace that information by adding additional clues somewhere ELSE.

I think that this hidden interaction is what makes the game itself enjoyable for players...

Cheers

gordon

[Moschopulus]

I just want to give an example, where we can easily prove that
18 clues are needed. I don't know if this has already been
mentioned.
It's the most canonical sudoku-grid
A(i,j)=1+(3*((i-1)%3)+(i-1)/3+j)%9) (hope I got it right)

.

Are these 18 clues sufficient to guarantee a unique solution?