The New Sudoku Players' Forum

[coloin]

Deleted

[coloin]

Deleted

[Zotmeister]

I accept full responsibility for any torment this topic may have caused.

It was on Valentine's Day this year that I first posted "How many Number Places?" on the Dell Magazines' "Solvers Say..." forum. Since then, I learned far more about this puzzle than I thought there was to learn. That was before I learned of its massive popularity in the UK. That was before I had registered at Wikipedia. I've learned quite a bit in these three months, and I'm still learning more.

To see my original question possibly answered is a great joy. I registered at this forum for the specific purpose of saying thanks. My deepest gratitude goes out to everyone involved at every stage. Keep up the wonderful work! - ZM

[Guest]

With further thought I have additions to make.

If the minimum number of fillings is 18 then we need to work it out for figures for 19. I hope this is not the case as it increases the calculations.
I cant see "the times" knowing as much as we do - and I am hopeful that a 17 unique solution is there. 5x10^21 is a big number !

If it is 18 then every 19 grid will be solvable. [but uniquely]
Every 18 grid will have 1 or more solutions. [cant be zero as we hve filled the grid in from a valid sudoko grid]]ie not zero] [By definition]

That means every 19 grid will be uniqely soluble - we already know that as some 18 grids are unique - but if an 18 grid is unique then an extra number [in the right place] is not going to change it.


Add up the occurrances for each variation of numbers.
I cant see the prime being a problem.

NB
There will be constraints in rows and columns when you have more than 2 of any number.

If the minimum turns out to be 17 or 16 so much the better !


Are the constraints complicated ?
We dont have box constraints as there are always 6 boxes and we never have more than 6 of any number - they are in the boxes we dont use boxes 3 4 and 8. So thats easy then !

18
33222222
33322221
33333111
43322211
44322111
54321111
54411111
55311111
55221111
64221111
65211111
66111111

17
32222222
33322211
43322111
44222111
44411111
54221111
54311111
55211111
63311111
64211111
65111111


16
22222222
32222221
42222211
43222111
43321111
44311111
44221111
54211111
53311111
55111111
64111111
63211111


So can any one else follow this and add up the numbers?

Im sipping champagne

Regards

[coloin]

Deleted

[Guest]

yes

[coloin]

I dont know why Im not getting a unique solution with 18
It is possible with one grid - to do it in 18

What does this grid look like ?

What way were the numbers allocated ?

[Guest]

[quote="coloin"]Guest
" I have been working on the exact same method just half an hour ago !"

"I had just formed an L shape like yours - although I had a nagging feeling that a combination of these first 5 boxes might just result in a constraint giving an impossible grid. "

(I havn't shown you don't get impossible grids from these five boxes - only estimated that each will give 2687.3856 solutions some might give 0)

"I was stuck on the central box 5 as you are but there is a calculation and i knew you need to use an average figure - not sure why though .

"The breakdown of filling B5: given B1,B2,B4

9!*6084 * 48 * 48 have 384 solutions
9!*12204 * 48 * 48 have 392 solutions
9!*36756 * 48 * 48 have 400 solutions
9!*224 * 48 * 48 have 432 solutions
9!*8236 * 48 * 48 have 448 solutions ..."

Can you use show me why this doesnt help ? It certainly looks useful. "

It probably does help but not much. 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. The presence of B1 alters these ratios slightly (hopefully I will confim your figures on thursday). We can then count the posible ways of filling in boxes 1,2,3,4,5 and 7. Some of thse will offer no solutions for boxes 6,8 &9 so to get a final answer we would have to examine each case separately.

Another way of ariving at 403.2 The chances of B5 being compatable with B2 is 1/30. Similarly with B4. 9!/900 = 403.2

"The last box - where do you get the 9 out of 70 ? I thought 1/30"
for the last box we know the three numbers required for each column the requirements for each row must match. wlog are columns must be 1,2,3 4,5,6 7,8,9 so 1 can be required in any row. 2 must be required in a diffrent row i.e. 6 of the possible 8 places. 3 must be in the remaining row 3 of 7 available places. 4 can go in any row 5 in 4 of 5 places 6 in 2 of 4.
789 must now be in different rows so multiplying 144/1120 = 9/70.

my counts for the boxes are
9! 9!/30 9!/30/56 9!/30 9!/30/30 9!/30/30/56 9!/30/56 9!/30/30/56 and 9!/30/30/56/56.

You can fill the boxes in any order. given the number of boxes in line in each direction already filled in we get average numbers of

0 0 9!
0 1 12096
1 1 403.2
0 2 216
1 2 7.2
2 2 9/70

so if we do boxes B1 B5 and B9 first thats 9!^3
then B2 B6 and B7 each giving 403.2
then each of the remaining boxes at 9/70.
multiplying gives the same estimate as before. 9!^9/(30^8 * 56^4).

I have a complete analysis of the simpler 2by 2 array of 2 by 2 boxes.
basic problems (which have a unique solution but the solution is not unique if any clued cell is removed) clue between 4 and 6 cells and there are less than 30 of them (after symetry considerations). A particularly interesting case is that if you clue

AB --
C- --

-- D-
-- - E

in a consistant manner each has a unique solution (symetry reduces it to two cases). Since each solution has values in these cells this is the full set of solutions i.e. 288.
The large prime factor in Bertram's Number suggests there is no similar set of cells for the normal game.

Another wat to get the total would be to count the solutions for

123 ??? ???
456 1?? ???
789 ??? 1??

?1? ??? ???
??? ?1? ???
??? ??? ?1?

??1 ??? ???
??? ??1 ???
??? ??? ??1

(only about 3.6 * 10^9) and multiply bt 8! * 6^6

[Guest]

This thread seems to be unravelling somewhat, so I thought I'd clear up one part of it now: I have confirmed Bertram's calculation for the number of valid Sudoku grids.

I've actually done this in two different ways:

1. fix top-left 3x3 contents + fix position of 1s (as suggested above and ages ago by someone else). This leaves 2000+ "templates" for the positions of each of the digits 2 to 8, each of which can be represented as a 64-bit int. Grind through these recursively. Takes ages, but works, and simple enough that it's hard to argue with.

2. fix representative contents of top 3 rows (27 cells). This is essentially Frazer's method. I can get this down to 44 representatives (Frazer and Bertram had 71 but noticed there were only 44 different results coming out of those). For each representative, solve the rest of the grid:
(a) by just chucking down 64-bit templates
or, (b) by looping over representative contents of 3x3 boxes 4,7 + position of remaining 1s, then solving remainder with 32-bit templates [sorry, I know this isn't making sense]
Each representative takes a couple of minutes to count and the result is the same as Bertram's and method 1 above.

Bertram has added my code to his archive if anyone wants to check it.

Now we just have the minimal grid question remaining on this thread. I think that's going to be quite a lot harder.

[Guest]

Now we just have the minimal grid question remaining on this thread. I think that's going to be quite a lot harder.

The minimum grid that I have been able to find so far is 17. That is, 17 (unfortunately not symmetrical) clues define a unique grid. One example is:
**6 9** *7*
*** *1* **2
8** *** ***

*2* *** **4
*** *** **1
**5 **6 ***

*** *** *6*
*** **2 *5*
*1* *43 ***
seems to have only one valid solution. I have no proof that this is a minimum, and I would have guessed that 18 was the minimum until I found this one.

[scrose]

The minimum grid that I have been able to find so far is 17.

Your example has a unique solution, but it requires a guess (or nishio).

Code: Select all

 1 4 6 | 9 2 8 | 3 7 5       .. .. ... | . . . | .. ... ...
 5 . . | 6 1 7 | 8 4 2       .. 39 3.9 | . . . | .. ... ...
 8 7 2 | 4 3 5 | 9 1 6       .. .. ... | . . . | .. ... ...
-------+-------+-------     -----------+-------+------------
 7 2 1 | 3 5 9 | 6 8 4       .. .. ... | . . . | .. ... ...
 . 6 8 | 2 7 4 | 5 . 1       39 .. ... | . . . | .. .39 ...
 4 . 5 | 1 8 6 | . . .       .. 39 ... | . . . | 27 239 .79
-------+-------+-------     -----------+-------+------------
 2 5 . | 8 9 1 | 4 6 .       .. .. 37. | . . . | .. ... 37.
 . 8 4 | 7 6 2 | 1 5 .       39 .. ... | . . . | .. ... 3.9
 6 1 . | 5 4 3 | . . 8       .. .. .79 | . . . | 27 2.9 ...

updated: added grid and candidates

[Guest]

Has anyone taken a crack at the minimum-givens question in terms of graph coloring or chromatic polynomials?

I've spent the morning looking at the 2x2x2 version of Sudoku in an attempt to make sense of it, and I think I've got a solution for 2x2x2, namely 5. In a 2x2x2 game, this is possible to provide for all possible arrangements.

All possible arrangements in a 2x2x2 game can be divided into 2 seperate graphs, each with 8 vertices, where these 8 vertices are chosen by pairing together two "colors" (numbers). These partial graphs form single components when connected with edges along all dependencies.

For example

1 3 4 2
4 2 1 3
2 1 3 4
3 4 2 1

can been seen as

1 x x 2
x 2 1 x
2 1 x x
x x 2 1
and
x 3 4 x
4 x x 3
x x 3 4
3 4 x x

or even as

1 3 x x
x x 1 3
x 1 3 x
3 x x 1
and
x x 4 2
4 2 x x
2 x x 4
x 4 2 x

though not

1 x 4 x
4 x 1 x
x 1 x 4
x 4 x 1
and
x 3 x 2
x 2 x 3
2 x 3 x
3 x 2 x
Because this last case features two components per partial graph.

These partial arrangements, if connected with edges along all dependencies, with merely 1 given can be colored with 2 colors in only 1 way. (side note:Should any of these partial components feature a 3-cycle, there would be no possible solution since you only have 2 colors at this point.)

This says that once you have defined one of the partial components (that's next), the second one follows from only one coloring.

The minimal way to define the first of these cycles is with 4 points, two each in opposite quadrants. This is the minimum.

These 4 points, plus one to define the second partial component, gives a total of 5.

I believe I have a proof of why all arrangements can be shown like this, though I haven't exhausted all the possibilites (only 16, so it wouldn't be hard). If someone can provide an example otherwise I'd be interested in seeing it. Basically, due to the nature of Sudoku, you will always have two unique diagonal pairings, and this will always give you a way of making two single-component partial graphs.

So, 5.

Can anyone show that some special arrangement can be fully unique from less than 5?

Does anyone have ideas for starting to translate this to 3x3x3 Soduko?

Does anyone understand what I'm talking about?

I find this to be a really interesting information theory type of question, and I'm glad to have found such an active discussion group looking at this right now! Looking at 3x3x3 Sudoku this way is many many times harder I fear, but I'm going to try and find connections to the 2x2x2 case.

Good luck all,
Johan Ugander
Engineering Physics major, Lund, Sweden

[Guest]

Has anyone taken a crack at the minimum-givens question in terms of graph coloring or chromatic polynomials?

I've spent the morning looking at the 2x2x2 version of Sudoku in an attempt to make sense of it, and I think I've got a solution for 2x2x2, namely 5.

[snip]

1* 4*
** **

*2 3*
** **

has the unique solution of:

13 42
24 13

42 31
31 24

[Guest]

The minimum grid that I have been able to find so far is 17.

Your example has a unique solution, but it requires a guess (or nishio).

I have a theory (obviously unproven) that there is no such thing as a puzzle that truely requires guessing/trial and error/bifurcation or whatever else you want to call it.

There's simply not yet sufficient logical techniques, or ones that a human can employ due to finite brain capacity, that allow for a purely 'logical' (please insert YOUR definition of 'logical' here) solution given the present state of the puzzle community.

To take this discussion to its absurdity, you could argue that the very act of placing 'pencil-marks' is a form of trial and error, as you had to mentally ask yourself something like 'why can't I place a '1' in this cell?....oh yeah, there's a '1' in the cell to the left!'. Couldn't someone spoiling for a fight argue this is a limited form of T&E? {please note that I am NOT going to respond to responses of this previous statement on this thread, as I do not want to hijack it. But if you start a new thread, I'll be happy to participate ;) }.

[amanzimdwini]

I found Soduko last week (and this discussion yesterday) and would like to propose a way to brute-force counting all possible solutions (a) in a way I have not seen here yet, (b) that can be implemented fast and easily and (c) that seems to show the number of possible solutions to be quite a bit smaller than accepted to date (which makes me worried: where am I wrong?)

I appologize for the wording below, but am actually trying to be as clear as possible.

Instead of doing specific arrangements of numbers, consider the restrictions on the arrangement of ANY number in a valid Soduko grid. Each of the 9 squares in the grid can only be filled by any of the following blocks (where x is any number between 1 and 9)

x.. .x. ..x ... ... ... ... ... ...
... ... ... x.. .x. ..x ... ... ...
... ... ... ... ... ... x.. .x. ..x

which I will name, from left to right, a,b,c, ... i
(looks poor in the post: the "x" move from the top left to the bottom right position in the 9 different blocks - prop. fonts are not fun)

It is seen immediately that an arrangement of bocks like
a d g
b e h
c f i
(which I can shorthand into adgbehcfi) is a legal arrangement of any one number x.

[Just to make sure my naming convention is understood: if x were to represent the number 2, then "adgbehcfi" would represent

2.. ... ...
... 2.. ...
... ... 2..
.2. ... ...
... .2. ...
... ... .2.
..2 ... ...
... ..2 ...
... ... ..2

, which is clearly a legal solution for the number 2]

We also note that any number can only be arranged ao that a,b,c etc is only used ONCE - prove it to yourself if you want to.

While there are 9! possible permutations of "adgbehcfi", a simple program can show the number of "LEGAL" permuations to be only 8784 (a nice small number) - for example, abcdefghi is NOT a LEGAL arrangement, since the "x" would be three times in the topmost row.

Note that symmetries, reflections and inversions are all included in these legal arrangements! We can now enumerate these 8784 LEGAL permutations as l(i).

We note that we need to be able to combine 9 legal permutations (one for each number) into a valid Soduko grid.
Let's say that an arrangement l(1)&l(100)&l(283)&l(1345)&l(2455)&l(3777)&l(4653)&l(7655)&l(8273)
is a valid grid (I'll explain the constraints below). Since the symbol that is used in each legal permutation is as yet un-determined, this grid can be used in 9! different ways. (x=1 in the first grid, x=2 in the second, etc, or x=2 in the first grid, while x=1 in the second and so on - you get the picture)

In other words, once we can find the number of possible arrangements of 9 legal permutations, all we need to do is multiply it by 9! to get the number of all possible Soduko grids - although 9! of them they are, strictly speaking, trivial permutations of each other.

So how do we determine if an arrangement is possible? Easy: we have to ensure that no two "x" occupy the same space anywhere on the grid. For example, if, in a legal grid, the first permutation has a "c" in it's first place, then none of the following 8 permutations may have a "c" in the first place. If any permutation has a "d" in the second place, none of the other may have one there. And so on.

Simple in theory IF we did not have the restriction that only 8784 of the grids are "Legal" - that forces me to do it brute force.

Even that should be easy - no more than 8784^9 nested loops (actually quite a bit fewer).... but I am simply not good enough at implementing this counting in a fast way. I guess a simple bit-map would do the job fast and efficiently and am wondering if anyone out there can implement it for me.

thanks,
amanzimdwini