Hm, i found all of them in the list.
The line numbers of the 15 above are
141, 2247, 3514, 5232, 5913, 12884, 14683, 15658, 17087, 18102, 18766, 24382, 26355, 26753, 28348
[Added:]
If you have gsf's program and unix tools you can find new ones this way:
Canonicalize the list:
sudoku -qFN -f'%#0c' sudoku17.txt > sudoku17.can
Canonicalize the puzzles:
sudoku -qFN -f'%#0c' puzzles.txt > puzzles.can
[Edit:]
Eliminate equivalents:
sort puzzles.can | uniq > uniqs.can
Find duplicates:
grep -f uniqs.can sudoku17.can > dups.txt
Get those from uniqs not in dups.txt:
grep -v -f dups.txt uniqs.can
I am sure, gsf knows it better ...
Sudoku space
by coloin » Tue May 08, 2007 10:22 am
So...........none are new....
well that is perhaps a relief !
Thanks for the coding - using it
There were no new 17s in these generated
and no new ones in harvards new list.... confirming that ravel is correct.
Perhaps it is not surprizing that we are not finding new 17s......the search for near distance puzzles will highlight puzzles with mutable clues and have a similar pattern. Gfroyle, gsf and papy have done this search 1off/1on exaustivly........
Perhaps we need to restrict our search and only compare untouchable 17s, - with no mutable clues ?
That would reduce things a bit - but might indicate the region to search deeper......with a 2off/2on search.
C
well that is perhaps a relief !
Thanks for the coding - using it
There were no new 17s in these generated
- Code: Select all
.......91.3.2.................6..23.1..4.....7........4..57........1.8...6....3..
.....9..1.3.2.......8.........6..23.1..4.....7........4...7........1.8...6....3..
.......81.3.2.....9...........6..23.1..4.....7........4...7........1.8...6....3..
........1.3.2.8...9...........6..23.1..4.....7........4...7........1.8...6....3..
.......8193.2.................6..23.1..4.....7........4...7........1.8...6....3..
.....5..1.3.2.......8.........6..23.1..4.....7........4...7........1.8...6....3..
.......81.3.2.....5...........6..23.1..4.....7........4...7........1.8...6....3..
........1.3.2.8...5...........6..23.1..4.....7........4...7........1.8...6....3..
.......51.3.2.................6..23.1..4.....7........4..97........1.8...6....3..
.......8153.2.................6..23.1..4.....7........4...7........1.8...6....3..
........1.3.25....9...........6..23.1..4.....7........4...7........1.8...6....3..
........1.3.2.....9...........6..23.1..4.....7....5...4...7........1.8...6....3..
.......91.3.2.................6..23.1..4.....7........4...7........1.8...6...53..
.......51.3.2.................6..23.1..4.....7........4...7........1.8...6...93..
........1.3.29....5...........6..23.1..4.....7........4...7........1.8...6....3..
........1.3.2.....5...........6..23.1..4.....7....9...4...7........1.8...6....3..
5.......1.3.2.........9.......6..23.1..4.....7........4...7........1.8...6....3..
........1.3.2............6....6..23.1..4.....7........4..97........1.8...6....3..
........1.3.2............6....6..23.1..4.....7........4..57........1.8...6....3..
9.......1.3.2.........5.......6..23.1..4.....7........4...7........1.8...6....3..
and no new ones in harvards new list.... confirming that ravel is correct.
Perhaps it is not surprizing that we are not finding new 17s......the search for near distance puzzles will highlight puzzles with mutable clues and have a similar pattern. Gfroyle, gsf and papy have done this search 1off/1on exaustivly........
Perhaps we need to restrict our search and only compare untouchable 17s, - with no mutable clues ?
That would reduce things a bit - but might indicate the region to search deeper......with a 2off/2on search.
C
- coloin
- Posts: 2507
- Joined: 05 May 2005
- Location: Devon
by gsf » Tue May 08, 2007 1:35 pm
ravel wrote:Hm, i found all of them in the list.
The line numbers of the 15 above are
141, 2247, 3514, 5232, 5913, 12884, 14683, 15658, 17087, 18102, 18766, 24382, 26355, 26753, 28348
I am sure, gsf knows it better ...
I think earlier reports of new 17's may have tripped over the switch in my solver to row-order minlex canonical form
I had an old sudoku17.can that produced the same results of 15 new
but updating sudoku17.can to row-order minlex now produces ravel's results above
and ... not better, but alternative
I have the 36628 17's (I hope that's all of them) in a file with space separated fields
- Code: Select all
canonical puzzle ordinal
sorted on the canonical field, 0 for non-clue cells, where ordinal is the line number
from Gordon's original list, incremented for new additions
put new 17's in a separate file in %#0c form, sorted, and then
- Code: Select all
join -v1 new.dat sudoku17.can
to list lines (puzzles) from new.dat not in sudoku17.can
to update the catalog resort and sequentially number the new entries listed by join
with the same 3 fields as sudoku17.can and then merge back with sudoku17.can
- gsf
- 2014 Supporter
- Posts: 7306
- Joined: 21 September 2005
- Location: NJ USA
by ronk » Tue May 08, 2007 4:35 pm
gsf wrote:ravel wrote:Hm, i found all of them in the list.
The line numbers of the 15 above are
141, 2247, 3514, 5232, 5913, 12884, 14683, 15658, 17087, 18102, 18766, 24382, 26355, 26753, 28348
I am sure, gsf knows it better ...
I think earlier reports of new 17's may have tripped over the switch in my solver to row-order minlex canonical form
I had an old sudoku17.can that produced the same results of 15 new
but updating sudoku17.can to row-order minlex now produces ravel's results above
That appears to be what happened. After rebuilding 'sudoku17.can', all the "new 17s" are now found.
I was unaware that row-order canonicalization became the new default.
- ronk
- 2012 Supporter
- Posts: 4764
- Joined: 02 November 2005
- Location: Southeastern USA
by gsf » Tue May 08, 2007 4:59 pm
ronk wrote:I was unaware that row-order canonicalization became the new default.
that happened after others on another thread showed how row-order could be computed
within epsilon time of box-order
I would have started out with row-order had the light come on quicker ...
- gsf
- 2014 Supporter
- Posts: 7306
- Joined: 21 September 2005
- Location: NJ USA
by coloin » Mon May 14, 2007 3:43 pm
Well we sort of got side tracked by the 17puzzle issue !
Having said that ravel's formula works well !
Distance = x plus 2y
x =clues in same position but wrong clue
y= clues which dont coincide
It would get a bit complicated if we started assigning box concordance !
In relation to the 17puzzle search......I am hoping that every 17puzzle has another puzzle within 6 [3off/3on] of another 17.
Although possibly there will be remote puzzles which dont ! [We will see]
So what is the average max concordance betwee 2 17puzzles
Can I stick my neck out and say EVERY 17 clue puzzle has these [equiv.] clues somewhere in the puzzle
Someone prove me wrong !
C
Having said that ravel's formula works well !
Distance = x plus 2y
x =clues in same position but wrong clue
y= clues which dont coincide
It would get a bit complicated if we started assigning box concordance !
In relation to the 17puzzle search......I am hoping that every 17puzzle has another puzzle within 6 [3off/3on] of another 17.
Although possibly there will be remote puzzles which dont ! [We will see]
So what is the average max concordance betwee 2 17puzzles
Can I stick my neck out and say EVERY 17 clue puzzle has these [equiv.] clues somewhere in the puzzle
- Code: Select all
+---+---+---+
|1..|...|...|
|...|2..|...|
|...|...|3..|
+---+---+---+
|.4.|...|...|
|...|.5.|...|
|...|...|...|
+---+---+---+
|..6|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
Someone prove me wrong !
C
- coloin
- Posts: 2507
- Joined: 05 May 2005
- Location: Devon
by Havard » Mon May 14, 2007 8:50 pm
coloin wrote:Can I stick my neck out and say EVERY 17 clue puzzle has these [equiv.] clues somewhere in the puzzle
- Code: Select all
+---+---+---+
|1..|...|...|
|...|2..|...|
|...|...|3..|
+---+---+---+
|.4.|...|...|
|...|.5.|...|
|...|...|...|
+---+---+---+
|..6|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
Someone prove me wrong !
C
So if someone did a complete search for 17's with this pattern, it would yield all known (and unknown) 17's? interesting.........
Havard
- Havard
- Posts: 378
- Joined: 25 December 2005
by tinfoil » Mon May 14, 2007 10:04 pm
Havard wrote:coloin wrote:Can I stick my neck out and say EVERY 17 clue puzzle has these [equiv.] clues somewhere in the puzzle
- Code: Select all
+---+---+---+
|1..|...|...|
|...|2..|...|
|...|...|3..|
+---+---+---+
|.4.|...|...|
|...|.5.|...|
|...|...|...|
+---+---+---+
|..6|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
Someone prove me wrong !
C
So if someone did a complete search for 17's with this pattern, it would yield all known (and unknown) 17's? interesting.........
Havard
I think you can stick your neck out and say that EVERY proper puzzle can have this pattern!
- tinfoil
- Posts: 16
- Joined: 06 June 2005
by Mauricio » Tue May 15, 2007 2:01 am
tinfoil wrote:I think you can stick your neck out and say that EVERY proper puzzle can have this pattern!
That is not correct, counterexample:
- Code: Select all
. 1 7|4 2 6|9 5 3
. 2 9|1 8 3|6 4 7
. 3 6|9 7 5|8 1 2
-----+-----+-----
. 4 3|2 6 9|7 8 5
. 5 2|7 1 8|4 3 6
. 6 8|3 5 4|2 9 1
-----+-----+-----
. 7 1|. . .|. . .
. 8 4|. . .|. . .
. 9 5|. . .|. . .
And a somewhat more extreme examples:
- Code: Select all
. . .|7 1 5|4 8 2
. . .|6 4 9|3 1 7
. . .|3 2 8|9 6 5
-----+-----+-----
. 4 9|1 6 2|7 5 3
. 5 3|4 9 7|8 2 6
. 6 7|8 5 3|1 4 9
-----+-----+-----
. 7 2|. . .|. . .
. 8 1|. . .|. . .
. 9 5|. . .|. . .
- Code: Select all
. . .|8 9 5|1 2 3
. . .|7 1 2|4 5 6
. . .|4 6 3|7 8 9
-----+-----+-----
. . .|6 3 9|5 1 8
. . .|1 7 8|3 4 2
. . .|5 2 4|6 9 7
-----+-----+-----
. 2 3|. . .|. . .
. 4 1|. . .|. . .
. 5 7|. . .|. . .
- Mauricio
- Posts: 1175
- Joined: 22 March 2006
by ravel » Tue May 15, 2007 12:45 pm
Checked the first 1000 of Gordons old list. About 10% of the puzzles (106) did not have.coloin wrote:Can I stick my neck out and say EVERY 17 clue puzzle has these [equiv.] clues somewhere in the puzzle
These are the first 10:
- Code: Select all
.......12..8.3...........4.12.5..........47...6.......5.7...3.....62.......1.....
.......124...9...........5..7.2.....6.....4.....1.8....18..........3.7..5.2......
.......13.4.....8.2...6....6.9...4.....8........3......3.1..5......4.7.6.........
.......13.4.....8.2...6....9.6...4.....8........3......3.1..5......4.7.6.........
.......13.4.....9.2...7....6.7...4.....3........9......3.1..5......6.8.7.........
.......13.4.....9.2...7....7.6...4.....3........9......3.1..5......6.8.7.........
.......14....2....5.........1.8.4...7.....5.....1.........5.73...42......3....6..
.......16...7.8..........5.5.12.....3.....8..6.........4....2......53....8..1....
.......187...4...........3.42....7.......1......3.....5...7.2..6.18......4.......
.......21.9.7.................514...63............2......6..93...1.4....2.....8..
- ravel
- Posts: 998
- Joined: 21 February 2006
by coloin » Tue May 15, 2007 12:50 pm
I am glad I have stimulated you all into action
Welcome back tinfoil !!!!!!!
The only puzzles which will tend not to have the 6/9 template are indeed the puzzles that Mauricio suggested
There are no 17s with 4 empty boxes - so that is ruled out
But most puzzles will have the 6/9 pattern at least.
except that there are several variations in the pattern- so it might not hold !
But I am not sure it is going to be all that useful
I found a 17 which had many many 6/9 templates, involving 16/17 clues
Thanks ravel
In your first puzzle ..what is this?
Note I said "equiv."
whats the max stats on random puzzles !
C
Welcome back tinfoil !!!!!!!
The only puzzles which will tend not to have the 6/9 template are indeed the puzzles that Mauricio suggested
- Code: Select all
+---+---+---+
|...|895|123|
|...|712|456|
|...|463|789|
+---+---+---+
|...|639|518|
|...|178|342|
|...|524|697|
+---+---+---+
|623|...|...|
|941|...|...|
|857|...|...|
+---+---+---+
There are no 17s with 4 empty boxes - so that is ruled out
But most puzzles will have the 6/9 pattern at least.
except that there are several variations in the pattern- so it might not hold !
- Code: Select all
xxx xxo xxo
xxo xxo oxx
xoo xxo xox
But I am not sure it is going to be all that useful
I found a 17 which had many many 6/9 templates, involving 16/17 clues
Thanks ravel
In your first puzzle ..what is this?
Note I said "equiv."
- Code: Select all
+---+---+---+
|...|...|..2|
|..8|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|7..|
|.6.|...|...|
+---+---+---+
|5..|...|...|
|...|...|...|
|...|1..|...|
+---+---+---+
whats the max stats on random puzzles !
C
- coloin
- Posts: 2507
- Joined: 05 May 2005
- Location: Devon
by ravel » Tue May 15, 2007 2:58 pm
This one is not equivalent to the one you posted above:coloin wrote:In your first puzzle ..what is this?
Note I said "equiv."
- Code: Select all
+---+---+---+
|...|...|..2|
|..8|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|7..|
|.6.|...|...|
+---+---+---+
|5..|...|...|
|...|...|...|
|...|1..|...|
+---+---+---+
- Code: Select all
+---+---+---+
|1..|...|...|
|...|2..|...|
|...|...|3..|
+---+---+---+
|.4.|...|...|
|...|.5.|...|
|...|...|...|
+---+---+---+
|..6|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
- ravel
- Posts: 998
- Joined: 21 February 2006
by coloin » Tue May 15, 2007 3:05 pm
You are absolutely right !
These were the maximum rook pattern templates I found in these random 17s [accuracy debatable]
I will have to think about the number of ways they can occur
EDIT
[9-1, 8-1, ,7-2, 6-?, 5-1]
6/9 boxes ONLY 1
The track we are going down - that havard aluded to, is to reduce the number of possible 14-clue templates somehow though I have my doubts now if this is going to work.
C
- Code: Select all
.2.....7.6...1..........68.....9.5...7.8...........1..1.53........7...4.9........ 6/9
....4.87..61..................6...312...7....4.........5.1.8...7.....2.....3..... 7/9
.1......9...3..8........6......124..7.3......5........8..6.........4..2....7...5. 7/9
...5.1....9....8...6.......4.1..........7..9........3.8.....1.5...2..4.....36.... 8/9
......8.17..2........5.6......7...5..1....3...8.......5......2..4..8....6...3.... 6/9
.2.....46...3.1..........7.5.....3......6.8...7..4....1.....5.....9...2.3........ 6/9
7..4.....6......9........1..12...8.....6.3......9.....39....7......2...5......4.. 7/9
53....1......27............4.7...8.....1.....2.........6.3...5...3.98...........2 7/9
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3. 7/9
3.6.7...........518.........1.4.5...7.....6.....2......2.....4.....8.3.....5..... 7/9
......8.17..2........5.6......7...5..1....3...8.......5......2..3..8....6...4.... 7/9
.......71.2.8........4.3...7...6..5....2..3..9........6...7.....8....4......5.... 7/9
....14....3....2...7..........9...3.6.1.............8.2.....1.4....5.6.....7.8... 7/9
6.2.5.........4.3..........43...8....1....2........7..5..27...........81...6..... 7/9
.524.........7.1..............8.2...3.....6...9.5.....1.6.3...........897........ 7/9
6.2.5.........3.4..........43...8....1....2........7..5..27...........81...6..... 7/9
.923.........8.1...........1.7.4...........658.........6.5.2...4.....7.....9..... 7/9
....75....1..2.....4...3...5.....3.2...8...1.......6.....1..48.2........7........ 6/9
64.....3....7.1....9.......2.....8.7.3..6..........5......4..9.7..8.....3........ 7/9
......8.16..2........7.5......6...2..1....3...8.......2......7..3..8....5...4.... 7/9
.98.1....2......6.............3.2.5..84.........6.........4.8.93..5...........1.. 6/9
6.....8.3.4.7.................5.4.7.3..2.....1.6.......2.....5.....8.6......1.... 6/9
.8..4....3......1........2...5...4.69..1..8..2...........3.9....6....5.....2..... 7/9
.91.6....4......7.............4.2.5..39.........7.........3.6.92..5...........1.. 6/9
52...6.........7.13...........4..8..6......5...........418.........3..2...87..... 6/9
4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4...... 6/9
.19....5.4..2..................91.......5..6.7.....3.....3..4.7.61............2.. 6/9
.71..8...5......2...............68.14...3..........7.....45..3..16.........2..... 6/9
48.3............71.2.......7.5....6....2..8.............1.76...3.....4......5.... 6/9
These were the maximum rook pattern templates I found in these random 17s [accuracy debatable]
I will have to think about the number of ways they can occur
EDIT
[9-1, 8-1, ,7-2, 6-?, 5-1]
6/9 boxes ONLY 1
- Code: Select all
xxo xxx
xxo plus 1 clue xxo
oox oox all of the 4 spaces are equivalent
The track we are going down - that havard aluded to, is to reduce the number of possible 14-clue templates somehow though I have my doubts now if this is going to work.
C
Last edited by coloin on Fri Mar 14, 2008 5:05 am, edited 2 times in total.
- coloin
- Posts: 2507
- Joined: 05 May 2005
- Location: Devon
by coloin » Tue May 15, 2007 4:23 pm
Ive got it
Each 17 puzzle has a maximum value for its attacking rook template. Thereby classifying them.
If its a 9 there are 8 more clues to add, except that with the 6^8 symmetry there will be many reductions to be made, and perhaps several individual classes of 13 or 14 clues.
If its an 8 there are 9 more clues too add - which is a lot , but perhaps there will be many reductions.
If its a 7 then there are 10 more clues to add, but these clues when added arnt allowed to be in a position where an 8/9 template would be produced !!!!
Similarly and perhaps more markedly, if its a 6 [which ever type it happens to be] adding 11 more clues appears a big ask, but no clue can be added which results in the formation of a 7 clue template,
If we find a 17puzzle with a only a 5 well...I dont know where the clues will go !
Ah ha, so how does this affect our estimations ?
[possibly a load of rubbish ?]
C
Each 17 puzzle has a maximum value for its attacking rook template. Thereby classifying them.
If its a 9 there are 8 more clues to add, except that with the 6^8 symmetry there will be many reductions to be made, and perhaps several individual classes of 13 or 14 clues.
If its an 8 there are 9 more clues too add - which is a lot , but perhaps there will be many reductions.
If its a 7 then there are 10 more clues to add, but these clues when added arnt allowed to be in a position where an 8/9 template would be produced !!!!
Similarly and perhaps more markedly, if its a 6 [which ever type it happens to be] adding 11 more clues appears a big ask, but no clue can be added which results in the formation of a 7 clue template,
If we find a 17puzzle with a only a 5
well...I dont know where the clues will go !Ah ha, so how does this affect our estimations ?
[possibly a load of rubbish ?]
C
- coloin
- Posts: 2507
- Joined: 05 May 2005
- Location: Devon
