here are the bands with more than 4 4-unavoidable-sets
read vertically by minicolumns, so the first row is always 123456789
5,146258379413582697725831964
5,146258379413587692725831964
5,148256379412583697724831965
5,148256379413582697725831964
5,149256378412587693721834965
5,149258376412587693725834961
5,149256378417583692724865931
5,146258379412583697731825964
5,148259376412583697734821965
5,146258379412583697735864921
5,149256378413587692735861924
6,148256379413587692724831965
6,149256378413587692725831964
6,149256378413587692724865931
6,146258379412587693735821964
6,146258379413582697731825964
6,146259378413587692731825964
6,148256379412583697735821964
6,148256379412597683734865921
7,148256379417583692734821965
interesting the other (9,2) unavoidable set .
I can't think of any others.
And yes, you can always extend one given band to a sudokugrid
with all 3 bands equivalent to it.
Minimum number of clues
by dukuso » Fri Aug 12, 2005 9:00 am
Most of Gordon's 17-clue sudokus have the property that exists
one digit such that all nine clues for that digit could be filled
in immediately without filling any other digit.
I took the 450 17-clue sudokus from Gordon's webpage.
I deleted one clue and permuted the digits to get 450*17*9!
16-clue puzzles with multiple solutions.
I filtered those where exist 9 cells containing digit 1
which appear in each solution, I filled in these ones as
forced clues.
That gave 2480*8! puzzles with 22 clues.
I randomly changed the values of the non-1-clues.
I filtered those with two 2s where the 9 twos were forced and
filled in the 9 2s. Now I had about 10000
puzzles with 29 clues, 9 of which were ones and nine twos.
I randomly changed the values of the non-1,2-clues.
I filtered those with two 3s where the 9 threes were forced and
filled in the 9 3s. Now I had about 10000
puzzles with 36 clues, 9 of which were ones,nine twos and nine threes.
I couldn't proceed with the 4s now, since I could not find
any puzzle in that list where the 4s were forced and only
two 4s appeared as clues.
I tried to change the values of the 4s,5s,6s,7s,8s,9s randomly,
but not their positions.
Then I solved the puzzles and counted the solutions.
I always got a minimum of 13 solutions for solvable puzzles
with several random attempts.
Seems that 13 is the minimum with this method starting
from the 450 puzzles. I will try other 17-puzzles too with
this method, when someone sends them.
Now, I did the same with the same 17-clue-sudokus, but not deleting
one clue as before.
This gave indeed a few new 17-clue-sudokus (16 at least, but probably
not more than 50) not in Gordon's 450-list .
Then I tried it with random 17-cell puzzles, but failed.
(too slow,too few partial solutions, too impatient)
It might be possible to proof (or get empirical evidence) that there
is no 16-clue-sudoku with this property.
(we might generalize later by dropping conditions (4),..,(3))
(1) 3 of the clues are ones, 2 twos, 2 threes; leaving 9 for the digits >3
(2) all ones are forced, even when changing the values of the
non-one-clues, but not their positions
(3) all twos are forced after filling in the ones, even when
changing the values of the >2-clues, but not their positions
(4) all threes are forced after filling in the ones and twos, even when
changing the values of the >3-clues, but not their positions
Guenter.
one digit such that all nine clues for that digit could be filled
in immediately without filling any other digit.
I took the 450 17-clue sudokus from Gordon's webpage.
I deleted one clue and permuted the digits to get 450*17*9!
16-clue puzzles with multiple solutions.
I filtered those where exist 9 cells containing digit 1
which appear in each solution, I filled in these ones as
forced clues.
That gave 2480*8! puzzles with 22 clues.
I randomly changed the values of the non-1-clues.
I filtered those with two 2s where the 9 twos were forced and
filled in the 9 2s. Now I had about 10000
puzzles with 29 clues, 9 of which were ones and nine twos.
I randomly changed the values of the non-1,2-clues.
I filtered those with two 3s where the 9 threes were forced and
filled in the 9 3s. Now I had about 10000
puzzles with 36 clues, 9 of which were ones,nine twos and nine threes.
I couldn't proceed with the 4s now, since I could not find
any puzzle in that list where the 4s were forced and only
two 4s appeared as clues.
I tried to change the values of the 4s,5s,6s,7s,8s,9s randomly,
but not their positions.
Then I solved the puzzles and counted the solutions.
I always got a minimum of 13 solutions for solvable puzzles
with several random attempts.
Seems that 13 is the minimum with this method starting
from the 450 puzzles. I will try other 17-puzzles too with
this method, when someone sends them.
Now, I did the same with the same 17-clue-sudokus, but not deleting
one clue as before.
This gave indeed a few new 17-clue-sudokus (16 at least, but probably
not more than 50) not in Gordon's 450-list .
Then I tried it with random 17-cell puzzles, but failed.
(too slow,too few partial solutions, too impatient)
It might be possible to proof (or get empirical evidence) that there
is no 16-clue-sudoku with this property.
(we might generalize later by dropping conditions (4),..,(3))
(1) 3 of the clues are ones, 2 twos, 2 threes; leaving 9 for the digits >3
(2) all ones are forced, even when changing the values of the
non-one-clues, but not their positions
(3) all twos are forced after filling in the ones, even when
changing the values of the >2-clues, but not their positions
(4) all threes are forced after filling in the ones and twos, even when
changing the values of the >3-clues, but not their positions
Guenter.
- dukuso
- Posts: 479
- Joined: 25 June 2005
by coloin » Sun Aug 14, 2005 12:36 pm
That is a very serious attempt - still no 16
I have analysed several grids to see if there is a pattern in the number of solutions
The choice of this pattern is arbitrary
B12347 - 6280 solutions,minimum is 1960. average 2693.
B123456 - [120,156,168,180,192,228,276,288 solutions and other totals]
B12345 - [1224,1260 solutions and other totals]
B1245 - [2802 different B1245 sudokugrids with 1035 different solutions. minimum is 197280 maximum is 562176 average around 315000]
I chose to analyse the 4 box B1245 pattern - there are 9 in each complete valid sudoku grid.
Gfroyle 2 of strangly familiar 29 [there are 29 17ers in this grid]
245232 sol.
245952 sol.
246816 sol.
285696 sol.
291744 sol.
297072 sol.
309744 sol.
314784 sol.
337536 sol.
Gfroyle 16er [there are two 16ers in this grid - but not unique]
245232 sol.
245952 sol.
246816 sol.
285696 sol.
291744 sol.
297072 sol.
309744 sol.
314784 sol.
337536 sol.
Gfroyle no 20 of his 17 hint sudoku patterns[It has 2 numbers in each box - different from the rest]
246096 sol.
244080 sol.
304704 sol.
312192 sol.
311760 sol.
368064 sol.
340416 sol.
390528 sol.
406080 sol.
Gfroyle no 50 of his 17 hint sudoku patterns
288000 sol.
281088 sol.
299952 sol.
295344 sol.
339264 sol.
319392 sol.
333792 sol
344160 sol.
341280 sol.
Random 1
279936 sol.
298368 sol.
301968 sol.
314640 sol.
334944 sol.
326592 sol.
366048 sol.
376272 sol.
Random 2
248112 sol.
250560 sol.
277344 sol.
310464 sol.
331200 sol.
327456 sol.
311328 sol.
328896 sol.
332496 sol.
Random 3
270144 sol.
299808 sol.
299520 sol.
300960 sol.
305280 sol
321840 sol.
336672 sol.
355968 sol.
365760 sol.
Random 4
245232 sol.
250416 sol.
299520 sol.
292176 sol.
301680 sol.
303696 sol.
328896 sol.
336672 sol.
316224 sol.
Random 5
199440 sol.
243936 sol.
246240 sol.
279648 sol.
304416 sol.
302256 sol.
312624 sol.
409248 sol.
452736 sol.
Sudokusolver logic grid 1 [first one that came up on opening program]
244224 sol.
246960 sol.
248256 sol.
250416 sol.
289152 sol.
302688 sol.
311040 sol.
314208 sol.
344304 sol.
Sudokusolver logic grid 2
201024 sol.
250848 sol.
299520 sol.
295200 sol.
315216 sol.
310032 sol.
360576 sol.
365472 sol.
388656 sol.
Canonical [has many 19ers but no 18er]
562176 sol.
562176 sol.
562176 sol.
562176 sol.
562176 sol.
562176 sol.
562176 sol.
562176 sol.
562176 sol.
The supposition is that a grid which has a better chance of a 16 will come from a grid which has a lower number of solutions in it.
Whether this is valid or not - i dont know - but it seems to hold up to some extent.
- the first two grids by Gfroyle the 2/29 17er grid and the 16er grid have 3 low numbers with 8 out of 9 below average counts - they have the same solution counts!
- the other two Gfroyle grids are unspectacular - maybe not surprising.
- the 5 random grids would appear to support the theory - although one does have two low counts and one has three low counts along with two very high counts.
-one of the grids thrown up by the sudokusolver logic site completly disproves the theory - unless it is by chance a special grid. It has 4 low solution numbers. I copy it out for reference.
In trying to manufacture these grids it has to be pointed that the valid grid gets determined after 2 or at most 3 combinations. My early work suggests that if you pick low solution numbers - then you end up with high solution numbers in the other combinations.
Perhaps the theory doesnt hold any water at all - re both Gfroyles grids having identical solutions scuppers most of the credibility - ? explanation.
I will try to come up with a complete grid with even lower amounts of solutions.
Here is sudokusolver logic grid 1
832 591 674
496 387 251
571 264 983
185 746 392
267 953 418
943 812 765
714 638 529
329 175 846
658 429 137
I think there are too many [6] pairs in this to be of any use in having a 16
Thanks to Guenter for his excellent program.
Colin
I have analysed several grids to see if there is a pattern in the number of solutions
The choice of this pattern is arbitrary
B12347 - 6280 solutions,minimum is 1960. average 2693.
B123456 - [120,156,168,180,192,228,276,288 solutions and other totals]
B12345 - [1224,1260 solutions and other totals]
B1245 - [2802 different B1245 sudokugrids with 1035 different solutions. minimum is 197280 maximum is 562176 average around 315000]
I chose to analyse the 4 box B1245 pattern - there are 9 in each complete valid sudoku grid.
Gfroyle 2 of strangly familiar 29 [there are 29 17ers in this grid]
245232 sol.
245952 sol.
246816 sol.
285696 sol.
291744 sol.
297072 sol.
309744 sol.
314784 sol.
337536 sol.
Gfroyle 16er [there are two 16ers in this grid - but not unique]
245232 sol.
245952 sol.
246816 sol.
285696 sol.
291744 sol.
297072 sol.
309744 sol.
314784 sol.
337536 sol.
Gfroyle no 20 of his 17 hint sudoku patterns[It has 2 numbers in each box - different from the rest]
246096 sol.
244080 sol.
304704 sol.
312192 sol.
311760 sol.
368064 sol.
340416 sol.
390528 sol.
406080 sol.
Gfroyle no 50 of his 17 hint sudoku patterns
288000 sol.
281088 sol.
299952 sol.
295344 sol.
339264 sol.
319392 sol.
333792 sol
344160 sol.
341280 sol.
Random 1
279936 sol.
298368 sol.
301968 sol.
314640 sol.
334944 sol.
326592 sol.
366048 sol.
376272 sol.
Random 2
248112 sol.
250560 sol.
277344 sol.
310464 sol.
331200 sol.
327456 sol.
311328 sol.
328896 sol.
332496 sol.
Random 3
270144 sol.
299808 sol.
299520 sol.
300960 sol.
305280 sol
321840 sol.
336672 sol.
355968 sol.
365760 sol.
Random 4
245232 sol.
250416 sol.
299520 sol.
292176 sol.
301680 sol.
303696 sol.
328896 sol.
336672 sol.
316224 sol.
Random 5
199440 sol.
243936 sol.
246240 sol.
279648 sol.
304416 sol.
302256 sol.
312624 sol.
409248 sol.
452736 sol.
Sudokusolver logic grid 1 [first one that came up on opening program]
244224 sol.
246960 sol.
248256 sol.
250416 sol.
289152 sol.
302688 sol.
311040 sol.
314208 sol.
344304 sol.
Sudokusolver logic grid 2
201024 sol.
250848 sol.
299520 sol.
295200 sol.
315216 sol.
310032 sol.
360576 sol.
365472 sol.
388656 sol.
Canonical [has many 19ers but no 18er]
562176 sol.
562176 sol.
562176 sol.
562176 sol.
562176 sol.
562176 sol.
562176 sol.
562176 sol.
562176 sol.
The supposition is that a grid which has a better chance of a 16 will come from a grid which has a lower number of solutions in it.
Whether this is valid or not - i dont know - but it seems to hold up to some extent.
- the first two grids by Gfroyle the 2/29 17er grid and the 16er grid have 3 low numbers with 8 out of 9 below average counts - they have the same solution counts!
- the other two Gfroyle grids are unspectacular - maybe not surprising.
- the 5 random grids would appear to support the theory - although one does have two low counts and one has three low counts along with two very high counts.
-one of the grids thrown up by the sudokusolver logic site completly disproves the theory - unless it is by chance a special grid. It has 4 low solution numbers. I copy it out for reference.
In trying to manufacture these grids it has to be pointed that the valid grid gets determined after 2 or at most 3 combinations. My early work suggests that if you pick low solution numbers - then you end up with high solution numbers in the other combinations.
Perhaps the theory doesnt hold any water at all - re both Gfroyles grids having identical solutions scuppers most of the credibility - ? explanation.
I will try to come up with a complete grid with even lower amounts of solutions.
Here is sudokusolver logic grid 1
832 591 674
496 387 251
571 264 983
185 746 392
267 953 418
943 812 765
714 638 529
329 175 846
658 429 137
I think there are too many [6] pairs in this to be of any use in having a 16
Thanks to Guenter for his excellent program.
Colin
- coloin
- Posts: 2504
- Joined: 05 May 2005
- Location: Devon
by coloin » Sun Aug 14, 2005 7:20 pm
Using the grid from the previous posting
832 591 674
496 387 251
571 264 983
185 746 392
267 953 418
943 812 765
714 638 529
329 175 846
658 429 137
The pairs are represented
xxx 5x1 67x
xxx xxx 25x
5x1 x64 xxx
185 x46 xxx
xxx xxx xxx
xxx xxx 76x
xxx xxx 52x
xxx 1x5 xxx
x58 xxx xxx
this grid has "only" 14044 solutions
If you can possibly find a minimum combination of OTHER clues which are only in our grid but not in any of the 14044 solutions - these numbers will be significant ?
The 3 in B9 reduces it to 1231 solutions
The 4 in B1 reduces it to 142 solutions
the 2 in B4 reduces it to 12 solutions
the 3 in B7 reduces it to our grid
We will have these 4 clues plus a selection of 5 to determine the pairs
That leaves 7 to play with !
Can you use this to prove or disprove that there is not a 16 in this grid ?
Edit
a bit of a pity - there are two more pairs I have just spotted -
- the 2/6 in B1/B3
- the 5/8 in B8/B9
which reduces the solution rate from 14044 to 722 solutions
3 clues reduce this to our grid
3 in B7 to 51 solutions
6 in B7 to 11 solutions
9 in B1 to our grid
This is less satisfactory but as the pairs were linked - there are less of the pairs needed.
xx2 5x1 67x
xx6 xxx 25x
5x1 x64 xxx
185 x46 xxx
xxx xxx xxx
xxx xxx 76x
xxx xx8 52x
xxx 1x5 8xx
x58 xxx xxx
Add in the 3 in B7, 6 in B7 and the 9 in B1.
The pairs can reduce to 3 clues:
An example
xxx xxx xxx
x9x xxx xxx
xxx xxx xxx
xxx xx6 xxx
xxx xxx xxx
xxx xxx xxx
xxx xxx 5xx
3xx xxx xxx
65x xxx xxx
or
xxx xxx xxx
x9x xxx xxx
xxx xxx xxx
xxx x4x xxx
xxx xxx xxx
xxx xxx xxx
xxx xxx xxx
3xx 1xx xxx
6x8 xxx xxx
3 clues from the pairs [varations on a theme [4*7*16]]
3 clues from the clues inserted above - the 9,3and 6
10 clues to be added - determined from the grid - to give or not to give a 16
Can you use this to prove or disprove that there is not a 16 in this grid ?
Do we assume that we wont want to use the unused paired numbers in the chain ? - Is this too many to manage ?
[less than approx. 4*7*16*6^7*5^3 = 15676416000 ways to fill out 16 clues]
Have I gone a step to far again ?
Colin
832 591 674
496 387 251
571 264 983
185 746 392
267 953 418
943 812 765
714 638 529
329 175 846
658 429 137
The pairs are represented
xxx 5x1 67x
xxx xxx 25x
5x1 x64 xxx
185 x46 xxx
xxx xxx xxx
xxx xxx 76x
xxx xxx 52x
xxx 1x5 xxx
x58 xxx xxx
this grid has "only" 14044 solutions
If you can possibly find a minimum combination of OTHER clues which are only in our grid but not in any of the 14044 solutions - these numbers will be significant ?
The 3 in B9 reduces it to 1231 solutions
The 4 in B1 reduces it to 142 solutions
the 2 in B4 reduces it to 12 solutions
the 3 in B7 reduces it to our grid
We will have these 4 clues plus a selection of 5 to determine the pairs
That leaves 7 to play with !
Can you use this to prove or disprove that there is not a 16 in this grid ?
Edit
a bit of a pity - there are two more pairs I have just spotted -
- the 2/6 in B1/B3
- the 5/8 in B8/B9
which reduces the solution rate from 14044 to 722 solutions
3 clues reduce this to our grid
3 in B7 to 51 solutions
6 in B7 to 11 solutions
9 in B1 to our grid
This is less satisfactory but as the pairs were linked - there are less of the pairs needed.
xx2 5x1 67x
xx6 xxx 25x
5x1 x64 xxx
185 x46 xxx
xxx xxx xxx
xxx xxx 76x
xxx xx8 52x
xxx 1x5 8xx
x58 xxx xxx
Add in the 3 in B7, 6 in B7 and the 9 in B1.
The pairs can reduce to 3 clues:
An example
xxx xxx xxx
x9x xxx xxx
xxx xxx xxx
xxx xx6 xxx
xxx xxx xxx
xxx xxx xxx
xxx xxx 5xx
3xx xxx xxx
65x xxx xxx
or
xxx xxx xxx
x9x xxx xxx
xxx xxx xxx
xxx x4x xxx
xxx xxx xxx
xxx xxx xxx
xxx xxx xxx
3xx 1xx xxx
6x8 xxx xxx
3 clues from the pairs [varations on a theme [4*7*16]]
3 clues from the clues inserted above - the 9,3and 6
10 clues to be added - determined from the grid - to give or not to give a 16
Can you use this to prove or disprove that there is not a 16 in this grid ?
Do we assume that we wont want to use the unused paired numbers in the chain ? - Is this too many to manage ?
[less than approx. 4*7*16*6^7*5^3 = 15676416000 ways to fill out 16 clues]
Have I gone a step to far again ?
Colin
- coloin
- Posts: 2504
- Joined: 05 May 2005
- Location: Devon
7500 17-clue Sudokus
by gfroyle » Mon Aug 15, 2005 2:51 am
By popular request (well, by one request) the list of known 17-clue Sudokus is available for download at
http://www.csse.uwa.edu.au/~gordon/sudoku17
There are currently about 7600 of them in the list... but still no 16s.
Enjoy..
Gordon
http://www.csse.uwa.edu.au/~gordon/sudoku17
There are currently about 7600 of them in the list... but still no 16s.
Enjoy..
Gordon
- gfroyle
- Posts: 214
- Joined: 21 June 2005
by dukuso » Mon Aug 15, 2005 6:45 am
thanks to Gordon for the list !
Seems that you are still searching, and the list is growing.
Coloin's posts take some more time to digest and respond...
Can you already give a quick estimate, whether you consider
your B12347-B5689 partition more promising than the
B123-B456789 ?
Seems that you are still searching, and the list is growing.
Coloin's posts take some more time to digest and respond...
Can you already give a quick estimate, whether you consider
your B12347-B5689 partition more promising than the
B123-B456789 ?
- dukuso
- Posts: 479
- Joined: 25 June 2005
by coloin » Mon Aug 15, 2005 8:08 am
dukuso wrote:Can you already give a quick estimate, whether you consider
your B12347-B5689 partition more promising than the
B123-B456789 ?
I mentioned above [I am sure you can expand on these more precisley] in an attempt to answer this fom a previous query.
"The choice of this pattern is arbitrary
B12347 - 6280 solutions,minimum is 1960. average 2693.
B123456 - [120,156,168,180,192,228,276,288 solutions and other totals]
B12345 - [1224,1260 solutions and other totals]
B1245 - [2802 different B1245 sudokugrids with 1035 different solutions. minimum is 197280 maximum is 562176 average around 315000] "
We dont know for sure if grids with lower totals are more likely to yield a result. Also scope for manipulation is limited especially in the B1245 [same as B5689]. A gut feeling is that if the partitions are "closer" together in terms of numerical value we will get more valid results.
Having said that - if all we are doing is possibly finding a suitable grid by identifing low solution combinations within the grid then it probably doesnt matter much.
The B12347 werent helpful at all with Gfroyles 17 grid - which is I cant understand.
The few B123456 that I did - looked to be able to differentiate Gfroyles from a random - but the low numbers looked crude.
I have not looked seriously at B12345/B1234 combination.
Maybe this is not the way - if its not I dont know what is !
If my previous post turns up a few 17s then perhaps we are closer
Colin
- coloin
- Posts: 2504
- Joined: 05 May 2005
- Location: Devon
by dukuso » Mon Aug 15, 2005 9:14 am
I've been making new 17s , using Gordon's list of 7600
with the method described some posts earlier.
I can get about 100 per hour, quite possible that this can be extended
to 200 or more.
But they all have the property that 2 digits can be filled with all
18 occurrances immediately by simple logic and they are limited
by the "capacity" of Gordon's 17s - I don't think I can make more
than 1000 in total.
with the method described some posts earlier.
I can get about 100 per hour, quite possible that this can be extended
to 200 or more.
But they all have the property that 2 digits can be filled with all
18 occurrances immediately by simple logic and they are limited
by the "capacity" of Gordon's 17s - I don't think I can make more
than 1000 in total.
- dukuso
- Posts: 479
- Joined: 25 June 2005
by Moschopulus » Mon Aug 15, 2005 10:05 am
dukuso wrote:I've been making new 17s .......
How do you know that they are "new" ?
Do you test for equivalence with the entire list?
How do you test for equivalence? (you wrote a program?)
How long does it take?
- Moschopulus
- Posts: 256
- Joined: 16 July 2005
by dukuso » Mon Aug 15, 2005 2:21 pm
well, you can test whether 2 grids are equivalent using "Nauty".
Make a graph with vertices 81cells+9rows+9columns+9blocks+9symbols
etc. assumedly nobody except Gordon understands...
I usually just only test the gangster-class of the 6 bands as invariants.
In this case, with all clues on the same cells I just label the clues
1,2,..,9 - 1st occurring clue is 1 , etc.
e.g.
000010020340000000500400000000500600020100000070000000800000500000076000000020009
But I was indeed too optimistic with my number of new 17s.
Out of my 330, only about 25 were new. So this method
is currently too slow.
--------------------------------------
I was trying to find a sudoku with 17 clues, where
(1)all 1s are forced, depending only on the positions of the non-1 clues,
not their values
when the 9 ones are filled in
(2) all 2s are forced, depending only on the positions of the non{1,2}
clues, not their positions
....
with Gordon's old list I could only come upto the 3s, now I can come
upto the 5s :
210803540460250301035410200041632075000145032523000014050721483102304050304500120
210603540480250301035410200041832065000145032523000014050721493102304050304500120
210950340470203501035410200041732095000145032523000014050621483102304050304500120
091345762034021500052000314420530001360714825510200430103450200040802153205103040
091345872034021500052000314420530001370814625510200430103450200040602153205103040
071345692034021500052000314420530001390714825510200430103450200040602153205103040
561984230340250001020130540000013425052040163413025000034501982100402350205300014
find the clues to remove until you are left with 17 !
sudoku-retro-analysis
Make a graph with vertices 81cells+9rows+9columns+9blocks+9symbols
etc. assumedly nobody except Gordon understands...
I usually just only test the gangster-class of the 6 bands as invariants.
In this case, with all clues on the same cells I just label the clues
1,2,..,9 - 1st occurring clue is 1 , etc.
e.g.
000010020340000000500400000000500600020100000070000000800000500000076000000020009
But I was indeed too optimistic with my number of new 17s.
Out of my 330, only about 25 were new. So this method
is currently too slow.
--------------------------------------
I was trying to find a sudoku with 17 clues, where
(1)all 1s are forced, depending only on the positions of the non-1 clues,
not their values
when the 9 ones are filled in
(2) all 2s are forced, depending only on the positions of the non{1,2}
clues, not their positions
....
with Gordon's old list I could only come upto the 3s, now I can come
upto the 5s :
210803540460250301035410200041632075000145032523000014050721483102304050304500120
210603540480250301035410200041832065000145032523000014050721493102304050304500120
210950340470203501035410200041732095000145032523000014050621483102304050304500120
091345762034021500052000314420530001360714825510200430103450200040802153205103040
091345872034021500052000314420530001370814625510200430103450200040602153205103040
071345692034021500052000314420530001390714825510200430103450200040602153205103040
561984230340250001020130540000013425052040163413025000034501982100402350205300014
find the clues to remove until you are left with 17 !
sudoku-retro-analysis
- dukuso
- Posts: 479
- Joined: 25 June 2005
by Moschopulus » Tue Aug 16, 2005 12:21 am
dukuso wrote:well, you can test whether 2 grids are equivalent using "Nauty".
Make a graph with vertices 81cells+9rows+9columns+9blocks+9symbols
etc. assumedly nobody except Gordon understands...
I usually just only test the gangster-class of the 6 bands as invariants.
Don't assume that. So there are 117 vertices. When are two vertices adjacent?
Since 416^6=5182746699759616, which is greater than the number of grids up to equivalence, it is possible that each grid has its own 416-gangster 6-tuple. Do you know if this is true? Are there non-equivalent grids with the same 6-tuple?
- Moschopulus
- Posts: 256
- Joined: 16 July 2005
equivalence
by gfroyle » Tue Aug 16, 2005 4:09 am
Don't assume that. So there are 117 vertices. When are two vertices adjacent?
I check equivalence by forming the following graph.
81 vertices representing the 81 positions.
One vertex for each row, joined to the 9 positions in its row
One vertex for each col, joined to the 9 positions in its col.
One vertex for each horizontal block, joined to the three row vertices in that block.
One vertex for each vertical block, joined to the three column vertices in that block.
One vertex representing "horizontal" joined to the three vertices representing horizontal blocks.
One vertex representing "vertical" joined to the three vertices representing vertical blocks.
One base vertex joined to the two "direction" vertices [actually, this is superfluous now I think about it!]
9 vertices representing symbols, each joined to a position vertex if that position contains that symbol.
If two different puzzles give isomorphic graphs, then they are equivalent, otherwise not. Isomorphism can be checked using "nauty" in a fraction of a second..
The graph as described has more stuff than stricty needed for pure equivalence (this can be done just with the 81-vertex Sudoku graph plus 9 "symbol" vertices) but rather it is used to form a "canonical" version of each puzzle which is what I store.
Then candidate new Sudokus are canonically labelled and simply compared against the existing stored ones...
Gordon
- gfroyle
- Posts: 214
- Joined: 21 June 2005
by dukuso » Tue Aug 16, 2005 4:14 am
Moschopulus wrote:dukuso wrote:well, you can test whether 2 grids are equivalent using "Nauty".
Make a graph with vertices 81cells+9rows+9columns+9blocks+9symbols
etc. assumedly nobody except Gordon understands...
I usually just only test the gangster-class of the 6 bands as invariants.
Don't assume that. So there are 117 vertices. When are two vertices adjacent?
Since 416^6=5182746699759616, which is greater than the number of grids up to equivalence, it is possible that each grid has its own 416-gangster 6-tuple. Do you know if this is true? Are there non-equivalent grids with the same 6-tuple?
I didn't even check the 416-class, only the 44-class.
7524 from 7611 were different.
Only 80-90% of 3-tuples are possible, I can't say about 6-tuples.
Non-equivalent grids with same (416-)6-tuple ? I haven't thought
about it. Maybe someone can find an example. They must be rare.
I used this graph for a sudoku-grid:
81 vertices r_i,c_j for the cells
9 vertices r_i for the rows
9 vertices c_i for the columns
9 vertices b_i for the blocks
p vertices s_i for the symbols
(r_i,c_j , s_k) is an edge, iff symbol s_k is in cell r_i,c_j
cells,rows,columns,blocks have an edge, iff they intersect
this should ensure, that the grids are equivalent, iff their graphs are isomorphic
7543 non-isomorphic graphs for Gordon's 7611 (solved)grids
7561 from 7941 when I add my 330 generated sudokus,
but some grids have more than 1 different sudoku.
- dukuso
- Posts: 479
- Joined: 25 June 2005
by dukuso » Tue Aug 16, 2005 4:20 am
I think I'll give up searching for a 16-clue-sudoku.
I examined Gordon's list and this looks rather
discouraging.
I.e. when you remove one of the 17 clues and count the number
of solutions, then you get 10-20 counts for each of the smaller
values, except 1,3 and 5 !
That looks as if there is some theoretical obstacle which hinders
him from finding these.
Guenter.
number of solutioncounts c for 16-clue-puzzles
generated by deleting a clue from
one of Gordon's 17-sudokus for c=1,2,..98 :
0 18 0 43 0 33 9 26 0 36
2 38 24 23 18 39 40 28 11 62
25 32 8 27 25 47 16 25 19 34
12 35 27 38 27 34 16 46 19 42
23 29 21 55 25 58 22 38 18 28
16 48 50 48 22 34 29 40 57 30
26 43 36 44 29 25 30 35 19 42
28 45 24 21 10 43 38 51 26 16
36 35 23 33 24 29 19 36 36 49
22 46 27 54 35 38 27 38
I examined Gordon's list and this looks rather
discouraging.
I.e. when you remove one of the 17 clues and count the number
of solutions, then you get 10-20 counts for each of the smaller
values, except 1,3 and 5 !
That looks as if there is some theoretical obstacle which hinders
him from finding these.
Guenter.
number of solutioncounts c for 16-clue-puzzles
generated by deleting a clue from
one of Gordon's 17-sudokus for c=1,2,..98 :
0 18 0 43 0 33 9 26 0 36
2 38 24 23 18 39 40 28 11 62
25 32 8 27 25 47 16 25 19 34
12 35 27 38 27 34 16 46 19 42
23 29 21 55 25 58 22 38 18 28
16 48 50 48 22 34 29 40 57 30
26 43 36 44 29 25 30 35 19 42
28 45 24 21 10 43 38 51 26 16
36 35 23 33 24 29 19 36 36 49
22 46 27 54 35 38 27 38
Last edited by dukuso on Tue Aug 16, 2005 1:05 am, edited 1 time in total.
- dukuso
- Posts: 479
- Joined: 25 June 2005
