Sudoku space

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

Postby ravel » Tue May 08, 2007 9:46 am

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 ...
Last edited by ravel on Tue May 08, 2007 6:40 am, edited 2 times in total.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby 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
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: 2365
Joined: 05 May 2005
Location: Devon

Postby 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

Postby 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

Postby 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

Postby tarek » Mon May 14, 2007 2:48 pm

ah.....

Was there any progress in describing an algorithm for distance measurement ?

tarek
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby 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:!:
Code: Select all
+---+---+---+
|1..|...|...|
|...|2..|...|
|...|...|3..|
+---+---+---+
|.4.|...|...|
|...|.5.|...|
|...|...|...|
+---+---+---+
|..6|...|...|
|...|...|...|
|...|...|...|
+---+---+---+

Someone prove me wrong !
C
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby 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.........:D

Havard
Havard
 
Posts: 378
Joined: 25 December 2005

Postby 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.........:D

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

Postby 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

Postby ravel » Tue May 15, 2007 12:45 pm

coloin wrote:Can I stick my neck out and say EVERY 17 clue puzzle has these [equiv.] clues somewhere in the puzzle:!:
Checked the first 1000 of Gordons old list. About 10% of the puzzles (106) did not have.

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

Postby 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
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: 2365
Joined: 05 May 2005
Location: Devon

Postby ravel » Tue May 15, 2007 2:58 pm

coloin wrote:In your first puzzle ..what is this?
Note I said "equiv."
Code: Select all
+---+---+---+
|...|...|..2|
|..8|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|7..|
|.6.|...|...|
+---+---+---+
|5..|...|...|
|...|...|...|
|...|1..|...|
+---+---+---+

This one is not equivalent to the one you posted above:
Code: Select all
+---+---+---+
|1..|...|...|
|...|2..|...|
|...|...|3..|
+---+---+---+
|.4.|...|...|
|...|.5.|...|
|...|...|...|
+---+---+---+
|..6|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
Note that here you have a clue with 2 more givens in the same band and stack, but not in the other.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby coloin » Tue May 15, 2007 3:05 pm

You are absolutely right !:D

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: 2365
Joined: 05 May 2005
Location: Devon

Postby coloin » Tue May 15, 2007 4:23 pm

Ive got it:idea:

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: 2365
Joined: 05 May 2005
Location: Devon

PreviousNext

Return to General