17? 16? 15? 14?

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

17? 16? 15? 14?

Postby Papy » Mon Jan 01, 2007 3:53 pm

Happy new year every one!
In 2007 I"m sure that you hope to get very diificult problems
What is the hard's puzzle? This one?
Code: Select all
 
    _________
    ____8____
    ____2____
    ____1____
    _317_2645
    ____4____
    ____3____
    ____6____
    ____7____


At this time I fund only ONE SOLUTION using a non recursif Brute Force.The soft doesn't found other. Perhaps a bug.We have perhaps more solutions
So before to publish y generator I wait the opinion of ocean,ruud,gsf,cooli n and every player

Papy

Please send me solution or why your solve detect multi soluions. I compare with mine and remove it(if I can)
Papy
 
Posts: 131
Joined: 15 August 2006

Re: 17? 16? 15? 14?

Postby udosuk » Mon Jan 01, 2007 4:17 pm

Papy wrote:Happy new year every one!
In 2007 I"m sure that you hope to get very diificult problems
What is the hard's puzzle? This one?
Code: Select all
 
    _________
    ____8____
    ____2____
    ____1____
    _317_2645
    ____4____
    ____3____
    ____6____
    ____7____


At this time I fund only ONE SOLUTION using a non recursif Brute Force.The soft doesn't found other. Perhaps a bug.We have perhaps more solutions
So before to publish y generator I wait the opinion of ocean,ruud,gsf,cooli n and every player

Papy

Please send me solution or why your solve detect multi soluions. I compare with mine and remove it(if I can)

Your puzzle has thousands/millions of solutions... Here are 3 of them:
Code: Select all
123456789
456987123
789123456
245618397
831792645
697345218
562831974
978264531
314579862

123456789
456987123
789123456
245618397
831792645
697345218
562834971
974561832
318279564

987654321
652381974
413927856
794516283
831792645
526843719
279435168
148269537
365178492
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Pi » Mon Jan 01, 2007 6:51 pm

As this puzzle has only 14 clue numbers it was almost inevitable that the number of clues would be huge.

To my knowledge anyway (as i hven't been on the forum in months) there are no knows puzzles with less than 17 clues with unique solutions
Pi
 
Posts: 389
Joined: 27 May 2005

Postby StrmCkr » Tue Jan 02, 2007 11:44 am

closest
ive seen is 16 clues with 2 solutions.

and mathmatics of limits confirms that 17 is the minimul number of needed clues to solve.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 626
Joined: 05 September 2006

Postby re'born » Wed Jan 03, 2007 12:20 am

StrmCkr wrote:and mathmatics of limits confirms that 17 is the minimul number of needed clues to solve.


StrmCkr,

Would you elaborate a little on this or provide a citation? I wasn't aware this result is now known and am extremely excited to see a proof.

Happy New Year.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby StrmCkr » Wed Jan 03, 2007 1:07 am

www3.sympatico.ca/georg.josephs/SudokuEigenfunctionCalculation.htm { broken link }

heres a link for the math. (well an easier way to show it.)

then have me attempt to write it all out on here.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 626
Joined: 05 September 2006

Postby udosuk » Wed Jan 03, 2007 2:38 am

I'm not a maths whiz... But that proof doesn't make much sense to me (I can't see it taking consideration of the "3x3 box restraints")... If it works, can we use it to calculate the minimum clues for X puzzles, non-consecutive ones or windokus?

Are you sure it wasn't one of those "October Fools' Day" hoaxes?
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby StrmCkr » Wed Jan 03, 2007 8:02 am

thats y i said it was the easiest to link a basic example that doesn't show constraits (im thinking that math example simple looks at total number of possiblities)

9!x8!x7!x6!x5!X4!x3!x2!x1! (none restraint application) with derivitives shows 16.xxx rounded = 17

and isn't this an incorect interpretation of the number of puzzles?
1.834933472 x10^21

where there is http://www.afjarvis.staff.shef.ac.uk/sudoku/bertram.html

i cannot valid that it wasn't a joke post either he simply asked for a link on it for an example. (i used a link for an article i found on the net rather then posting way too many pages of math by hand)

some of the solid numbers he / she uses in the artical i can't figure out where they got them from either..

but any way a
restrained application would have to be formed like this.

first
find the equation to show restraints

in reality its (where n is the number of placed variables to the order of 9)

where n = (1:9) i do it by placing individual numbers 1 at a time.

where n is placed 9 times.

to show the number of remaining positions where n can only be placed(didn't consider defining each place just represented it to a specific power)

lets say you place all nine of the ones on the board.

you'd mathmatically reduce expoentially spaces, as follows.

(placing numbers as singles)

N1^81
N2^(81 - 21) (21 = number of placements the 1st # removed)
N3^(81 - 36)
N4^(81 - 45)
N5^(81 - 58)
N6^(81 - 67)
N7^(81 - 72)
N8^(81 - 77)
N9^(81 - 80)

next start placing the "2"s 9 times. (heres where a demstration of minimal clues needed arives)

N10^(81 - 9)
N11^(81 - 28)
N12^(81 - 41)
N13^(81 - 48)
N14^(81 - 61)
n15^(81 - 70)
N16^(81 - 75)

right up to here you can freely place 16 numbers any where and not generate a single valid sudokus (as placement conflicts are not present)

but once you place the 17th number the grid's limits placements increasingly bye 1^n positions with each addinal placement

don't belive me here

try this easy example

place all the 1's as follows. start from the top place a one in box 1.
my math is shown. then in quad 2. repeat till you place all the 1's

now go and do the same for the 2's... keep track of my mathmatical representation.
continue untill you reach the 16's number placed. (checks its math) now move to the last postion indicated with an x. (x postion is actually invalid as (2's+1's in last grid renders x as an invalid postion)

Code: Select all
 *-----------*
 |12.|...|...|
 |...  |12.|...|
 |...  |... |12.|
 |---+---+---|
 |21.|... |...|
 |... |21.|...|
 |... |...  |21.|
 |---+---+---|
 |..1|..x|...|
 |..2|..1|...|
 |...|...|..1|
 *-----------*



N17^(81 - 78) is actually a false representation of valid positions. overlapping 2+1's limit this number bye +1 additional square.

for every number beyond 16 placed the math changes respecfully.

since this is the first positon where overlaps can render additional clues
pointless (17 is the minmual amount of clues needed)

after 16 clues are placed addition clues placement changes in respect to the invalid(position constraints)

a more actuall equation would be

N^(81 - invalid positions - (spacial invalid)

shown as follows for the 17th position.

n17^(81- 78-(1) where 1 = overlap)
n18^(81- 80)
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 626
Joined: 05 September 2006

Postby re'born » Wed Jan 03, 2007 3:35 pm

If I missed something obvious then it is because the author, Georg Werner Joseph, is an atrocious writer. From what I can tell, his article is pure nonsense. For instance, '1' is not a prime number. He takes derivatives, but neither explains what functions he is differentiating, or even what he means by derivative in a context without functions. Who knows what he means by lines such as "1.5 => 15 => P" or "1 => 1p => Hydrogen", but it certainly isn't anything mathematical. My absolute favorite is:


[(S{to j=3}[1/j])-(S{to j=2}[1/j])]=1.83-1.5 =0.033=> 33p => As => poison

This suggests that "3" or 3-space is poisoned (As).



While I believe that 17 is a minimum for the number of givens in a Sudoku, I do not believe that this author has a proof.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby coloin » Wed Jan 03, 2007 5:09 pm

Yes, being careful not to prejudge, I think we are on similar discussion as from Dr. Z Proof of Minimum Clue >= 17 !

In my opinion, as in the majority of our attempts at trying to fathom out the whys in sudoku grids and puzzles, is that it is all down to the huge number of puzzles out there.

We know precisely the large number of complete grids, and these grids have a large but varying number and distribution of unavoidable sets.

The average number of clues in a minimal puzzle is around 27. These clues combine to hit all the unavoidable sets. There is bound to be a more efficient way of hitting all the sets and this is indeed so - all grids can be represented by 20 clues.

The fact that a few grids can be represented by 17 clues reflects the diversity of the grids/unavoidable sets - obviously there has to be a minimum - but the reason for this is not necessarily quantifiable.

Conversly the opposite occurs when looking at the maximum number of clues in a minimal puzzle. The problem is is not in hitting all the unavoidable sets - although this still has to be achieved, but in ensuring that each "given" clue has at least one unavoidable set which it occupies uniquely [hence the clue is essential and the puzzle is minimal].

Code: Select all
clue number      occurance         hits all unavoidables     mean grid sols per clue   
21 clue          not many          with difficulty           1000
26 clue          many              quite easily              35
33 clue          not many          difficult not to          approaching 2


The other problem of finding and defining difficult puzzles is ongoing, the logical "less clues-increasing difficulty" does not apply directly, and similarly I feel this is related to the number of puzzles at each clue level.
There are about 100 times more puzzles at the 21 clue stage rather than the 20 clue stage - and this possibly reflects why the most difficult puzzles [that have been found] have around 21 clues......

C
coloin
 
Posts: 1632
Joined: 05 May 2005

Postby Red Ed » Wed Jan 03, 2007 7:41 pm

coloin, you are a master of restraint; check this out if you still don't want to prejudge:)

PDNFTT
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby coloin » Wed Jan 03, 2007 8:50 pm

Perhaps G.W. Joseph and Dr. Z. have had discussions over coffee on the topic !

I know lets work out a way to get the number 17.
Pick a number, take logs or integrate......that gives 16......
Well we can always add on 1 for the null hypothesis

Eureka

In response to StrmCkr - it is true that you get a constraint after the 17th the way he described it , but you can also get a constraint with less clues
Code: Select all
+---+---+---+
|12.|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|21.|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|..?|...|...|
|...|..2|..1|
|...|..1|..2|
+---+---+---+


You still havn't proved that the number of grid solutions with 16 clues is always = 0 or > 1........[i.e. never 1]

I still think "Que Sera, Sera" is the best explanation !

C
Last edited by coloin on Wed Jan 03, 2007 5:29 pm, edited 1 time in total.
coloin
 
Posts: 1632
Joined: 05 May 2005

17?

Postby Papy » Wed Jan 03, 2007 9:24 pm

It's just an informatien idea not a mathematician so my approch is different.

If you examine a grid every cell receive the same number of constraint
suppose that you have a griud like this

1 2 3 4 5 6 7 8 9 With that grid suppose that you want only to
2 ..................... determine the box of a cell(or the digit...). To
3 ..................... acces to EACH ofd he 81 celle yopu need 17
4 ..................... numbers (Just like on the sample). If you remove
5 ..................... one digit necessarry you loose cells!!!
6 ..................... For me it's very easy to understand: how can you
7 ..................... acces to a matrix if each entrance is not available.
8 .....................
9 .....................

The rule is that for a given matrix X and Y
the minmal number X + Y - 1

Sample: a 3*3 grid with only the digits 1,2,3. The minimal number
is 3+3-1=5

123
2
3 you gat 123 231 312 but with 4 clues multi solutions

And what about X sudoku with diagonals.?We can have only 14 (or 13?) clues. The demonstration is bad?


No but the probleme don't have the same difficulty when you set a diagonal cell you use a new information to select the digit it doesn't have to figure two times in the same diagonal.

If you add other contrains you can diminue the number of clues but it's not pure Sudoku.
Like I'am a programmer I am not interesting by it'exits? But only by Why it exist

My brain says: here is the demonstreation that I need 17 clues
not: Why is not possible to have 16 clues....
There is no problem with the miinimal number of digits: is't arithmetic!!!

Thanks Descartes
Papy
Papy
 
Posts: 131
Joined: 15 August 2006

Postby StrmCkr » Wed Jan 03, 2007 10:44 pm

hey thanks for pointing that one out,


but onfortuintly thats not a constraint, thats a single position remaining in the row (only valid postion remaining) based on reduction of positions.

Code: Select all
Eureka

In response to StrmCkr - it is true that you get a constraint after the 17th the way he described it , but you can also get a constraint with less clues
Code:
+---+---+---+
|12.|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|21.|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|..?|...|...|
|...|..2|..1|
|...|..1|..2|
+---+---+---+



i demenstrate a true conflict of placement not removed by existing placemetents. (violating the constraints of the puzzle.)

if you place 16 clues around the board sure postions arive that

atomatically render one box as containing values only once. but if you don't break up all 18 restraints or at least 17 of them (the last solves it self), then more then 1 soltuion remains.

breaking up 16 restraints leaves 4 paired numbers unsolvable. (where examples like you listed break up 1 more but no more.

leaveing 2 paired numbers around the board. ie. 2 soutions.




im showing a postion that creates 0 soultions. where if x is selected a conflict arrises = 0 soutions in the last placement.




[/quote]
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 626
Joined: 05 September 2006

Postby Papy » Thu Jan 04, 2007 1:08 pm

No I think that you make a mistake:

To define the digits on a cell you have more that one contraint
I take a sample with one contraint just for the sample

The problem is to get all the params and see what is their influances.

An other sample

Imagine a grid where in each cell you put the sum of row and colums
You must put number on each row and eachh colonne
R1 C1= 2 R2DC2=3....

C1 C2 C3 C4 C5
R1
R2
R3
R4
R5


To access at each 25 celle you need 5 ref top the olmn and five to the rows. Exact?
you can fill the grid
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
6 7 8 9 10

Now we scramble the grid to get

C3 C1 C4 C5 C2
R5
R4
R1
R3
R2
3

WE CAN COMPLET THE GRID WITH THE SUM
8 6 9 10 7
7 5 8 9 6

Easy.
Burt now forget the R1,R2 C1,C2

and I just give you the value of some cells

8 6 9 10 7
7
1
3
2

if i remove one value the solution exist BECAUSE YOU KNOW taht the rows and colmns are numeroted from 1 to 5

In the Sudoku we don't know what is the constrain
perhaps the number of the row are random? The colums are odd
if you don't have the value of a complet row and a complete colon you can not determine how is computed the cell and extract a rule
Papy
Papy
 
Posts: 131
Joined: 15 August 2006

Next

Return to General

cron