17-clue and 18-clue Sudoku update

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

Postby RW » Fri Sep 14, 2007 2:05 pm

gfroyle wrote:How do you make it rate a whole bunch of puzzles? I downloaded it and could only see how to use it interactively, rather than in "batch mode"...

Nicolas Juillerat wrote:Included my old testing routines in the .jar file. There is now an
unsupported way of analysing many Sudokus at once:
java -cp SudokuExplainer.jar diuf.sudoku.test.Tester sudoku.txt result.txt
where "sudoku.txt" is a file with Sudokus, one line of 81 digits per puzzle;
and "result.txt" is the file in which analysis results are saved.


For this you of course also need to download the SudokuExplainer.jar file.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby gfroyle » Sat Sep 15, 2007 12:45 pm

Can anyone explain the following strangeness...

Here is puzzle #125 in its "original" form and minlex form..

Code: Select all
000000021800040000000000060090200000700000400000501000015000000000030900602000000
000000001000000023004005000000006400010000000370000000000370000008200900500010000


Here is SudokuExplainer's analysis of the original puzzle

Code: Select all
Difficulty rating: 7.1
This Sudoku can be solved using the following logical methods:
62 x Hidden Single
1 x Direct Hidden Pair
6 x Pointing
1 x Hidden Pair
2 x Swordfish
1 x Bidirectional Cycle
1 x Forcing Chain


and here is the analysis of the minlex puzzle..

Code: Select all
Difficulty rating: 7.1
This Sudoku can be solved using the following logical methods:
63 x Hidden Single
1 x Direct Hidden Pair
6 x Pointing
1 x Hidden Pair
2 x Swordfish
1 x Bidirectional Cycle
3 x Forcing Chain



Why does replacing the puzzle with an isomorph take 2 extra forcing chains? [At least the rating is the same!]

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby JPF » Sat Sep 15, 2007 1:07 pm

gfroyle wrote:Why does replacing the puzzle with an isomorph take 2 extra forcing chains? [At least the rating is the same!]

I will leave the experts to answer your question:)

I recently found ratings 8.5 and 8.9 for 2 equivalent puzzles.

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby gsf » Mon Sep 17, 2007 3:22 pm

JPF wrote:
gfroyle wrote:Why does replacing the puzzle with an isomorph take 2 extra forcing chains? [At least the rating is the same!]

I will leave the experts to answer your question:)

I recently found ratings 8.5 and 8.9 for 2 equivalent puzzles.

the SE algorithm was not designed to take isomorphs into account
dukosu's suexrat uses a tree search to rate and is prone to local minima/maxima
it works around this (imperfectly) by re-running on random isomorphs of the same puzzle and reporting the average rating

my solver's -q1 rating attacks the problem by using a singles only tree search (like suexrat)
but it orders the tree search by degree (e.g., bivalue/bilocation cells first, then trivalue/trilocation, etc.)
and counts all propositions for each of the cells of each degree
and continues until the collected propositions yield a solution
there is still an inherent ordering bias in the singles logic, but that tends to affect the last three digits
of 5 digit ratings, so taking the first two digits as n.m should be consistent across isomorphs of the same puzzle

a test on 10 random copies of the easter monster produced a consistent 99408
it took < 6min for all ten copies

on this puzzle
Code: Select all
600000002090400050001000700050084000000020000000305040200000600030009080007000001

the rating for the puzzle and 9 random isomorphs was consistently 6[01]*** and took 8s @1.9Ghz (ok, second digit affected here)
SE would have take 10*10hr = ~4day to do the same

the -q1 rating for |G|=47308 takes 1m20s @3.2Ghz

tree search profiles of -q1 rating searches are failrly consistent across random isomorphs
so it looks like most of the rating number slop is due to the ordering bias in the singles logic
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Lars Petter Endresen » Thu Oct 11, 2007 6:40 pm

Hello all,

First I generated 10 random 19s. Then I did {+3-3}{+1-2]{+2-2}{+1-2}, which gave 174901 19s, 11209 18s, 431205 18s and 1501 17s. But of all these 17s only 3 were new. Finally I did a {+2-2} and found another new one. I will not speculate how many 17s are left, but it seems that it is now much harder to find 17s after all the new ones from anon17. Possibly we may need yet another quantum leap in methods before we can find many more 17s.

Best Regards,

Lars Petter Endresen
Lars Petter Endresen
 
Posts: 7
Joined: 03 June 2007
Location: NORWAY

Postby coloin » Tue Oct 16, 2007 8:33 pm

Lars Petter Endresen wrote:Possibly we may need yet another quantum leap in methods before we can find many more 17s.

Well I think anon17 made two quantum leaps ! - which is why he/she is waiting in the wings to publish a furthur batch !

Leap 1 - He/she was able to generate 18s 60 times faster than before - by optimizing the {-2+2} operand.

Leap 2 - He/she identifies 17s from non-minimal 18s - this is not new, but it is very fast. The leap being the sheer number [and therefore variety] of 18s being generated.

I keep thinking there must be an easier way to reduce the possibilities of each 17 made.....ie "standardize" for the [9!] * [ 2*6^8] isomorphs of each puzzle....but no one has done so up to now.

C
coloin
 
Posts: 1633
Joined: 05 May 2005

Postby gsf » Mon Nov 26, 2007 7:19 pm

gfroyle wrote:I have a very rough prototype of an "automated checking and submission" service..

http://people.csse.uwa.edu.au/gordon/sudokuid.php


looks like mysql developed a problem over the weekend
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Fri Nov 30, 2007 8:46 pm

:idea:

Heres an optimization on the {-2+2} [and beyond]

I did a simple experiment

a random 18 with 6 mutable clues

Code: Select all
..............1..53..7...4......51.6.2...6..89..........74...9..1.....7..6.......

176 puzzles found with a {-2+2]

6 17-clue subpuzzles from the above puzzle [mutable clues removed]
Code: Select all
.................53..7...4......51.6.2...6..89..........74...9..1.....7..6.......
..............1...3..7...4......51.6.2...6..89..........74...9..1.....7..6.......
..............1..53......4......51.6.2...6..89..........74...9..1.....7..6.......
..............1..53..7...4......51.6.....6..89..........74...9..1.....7..6.......
..............1..53..7...4......51.6.2...6..89...........4...9..1.....7..6.......
..............1..53..7...4......51.6.2...6..89..........74...9........7..6.......


176 puzzles found with a {-1+2} in one third of the time

It might be a fluke........but I think its obvious now !

If this effect is consistant it might be good. It probably doesnt matter if we miss the odd 18......

It wont work for untouchable puzzles of course.

But it would appear to speed up 18 production with {-2+2}

It might be a selective way to do a {-0+3} on selected 17s with 3 mutable clues !!!!
Edit I tried a few of these - and I think it is unlikely to give us new puzzles.

Of course in this example of a 17-puzzle the 4 ar r7c8 isnt really mutable
Code: Select all
+---+---+---+
|...|.31|...|
|6..|...|5..|
|.1.|...|...|
+---+---+---+
|...|5..|2..|
|.83|...|...|
|...|7..|...|
+---+---+---+
|5.7|...|.4.|
|...|.8.|.3.|
|2..|6..|...|
+---+---+---+

And in this 17-puzzle thge 9 @r2c6 isnt really mutable
Code: Select all
+---+---+---+
|...|...|...|
|...|..9|...|
|7..|.3.|..6|
+---+---+---+
|2..|8..|...|
|...|..1|9..|
|..5|...|..4|
+---+---+---+
|.14|...|...|
|...|36.|..2|
|.9.|...|.7.|
+---+---+---+


The reason I mention these two examples is that in the generation of 18s with a {-1+1} the isomorph checking process clogs up the speed at arounnd 100k puzzles.

These two types of pseudo-mutable clues would be the major culprit. In a {-1+1} I cant see other isomorphs produced very often.

C
coloin
 
Posts: 1633
Joined: 05 May 2005

Postby gsf » Fri Jan 11, 2008 8:13 pm

well plugging along at a feeble pace I finally surpassed havard
but I'm guessing its because he's taken off for a while
is anon17 still at it?
here's the latest tally
the times are average time between new entries
Code: Select all
                anon17  5418  1m51s
          Gordon Royle   433  8h32m
                   gsf   356 11h03m
          H�vard Graff   355  1h57m
         Kohei Noshita   241 20h12m
                   JPF   220  6h19m
  Lars Petter Endresen   203  8h52m
                coloin   114  1d04h
            Jim Wilson    55 15h16m
          Kevin Burley    44 10h21m
                    RW    17  9h52m
             Anonymous    13  6d14h
       Mauricio Chac�n    11  5d19h
        Colin Colville     4  1d18h
                 ravel     1      -
       Helene Foliguet     1      -
                 total  7486 41m44s
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gsf » Thu Jan 31, 2008 5:50 pm

around 2008-01-30 the sudokuid site went blank
anyone else having problems?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Thu Jan 31, 2008 7:01 pm

gsf wrote:anyone else having problems?

It was working eallier today....I am having problems making new 17s though. How are you and Kohei Noshita managing to do it ?

Any 18s that I make are not close to the remaining 17s which undoubtably are out there !

I have played with the idea of fixing clues - but this has not been successful in getting new 17s........it might be a better way to try to get a broader sample of 18s though.

Maybe the site is down because anon17 has found them all !

C
coloin
 
Posts: 1633
Joined: 05 May 2005

Postby gsf » Thu Jan 31, 2008 7:36 pm

coloin wrote:
gsf wrote:anyone else having problems?

It was working eallier today....I am having problems making new 17s though. How are you and Kohei Noshita managing to do it ?

Any 18s that I make are not close to the remaining 17s which undoubtably are out there !

wget(1) shows http error 500 -- internal server error

I use these options to my solver to generate <= 22 clue minimal puzzles
Code: Select all
-gp -m1 -e 'C<=22||M>2' -q1

and then do another pass with these options to generate 17's
Code: Select all
18 clues: -go{-1+1}x4{-2+1}
19 clues: -go{-2+1}x1{-1+1}x4{-2+1}
20 clues: -go{-2+1}x2{-1+1}x4{-2+1}
21 clues: -go{-2+1}x3{-1+1}x4{-2+1}
22 clues: -go{-2+1}x4{-1+1}x4{-2+1}


the pickings are slim
and some 22s generate thousands of registered 17s
I have 6 ~2Ghz machines generating ~1 / day total

I'm not sure (and I don't know how to contact Kohei) but I think he(?) may picking up something
I'm missing from my submissions
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Thu Jan 31, 2008 8:17 pm

gsf wrote:I have 6 ~2Ghz machines generating ~1 / day total

That explains it !

However, perhaps to shave off some repetitions.....it is only worthwhile subjecting the new puzzles found from repeat {-1+1} to a {-2+1} .

I might have mentioned before , but I suspect using a "wandering" {-2+2} on ? 19s might be a quicker way to generate new/different 19s.

You only have to make 18s from these 19s at the same rate as you can do a {-2+1} on an 18.

This way [possibly] you are checking a more random selection of 18s.

Edit - which i might add is what you must be doing

Certainly endless 18s generated by {-1+1}xn will not tend to make new 17s .

C
coloin
 
Posts: 1633
Joined: 05 May 2005

Postby coloin » Mon Feb 04, 2008 2:10 am

I think I can make this exercise a whole lot simpler.

If you take a random 18-puzzle, performing a full {-2+2} takes about 300 seconds producing around 250 more minimal 18s. ~ 1 per second.

This is around the same speed or faster than we can do a {-2+1} on an 18 to look for a 17.

If we can start with a 18 and successivly {-2+2} on each puzzle, with an effective way to not pick the recently added clues, it would be impossible not to get a very random selection of 18s. This way I believe we will get the last remaining 17s.


We can fix 5 clues and hill-climb the variable other 13 clues [actually reduced to 11 if you keep the 2 recently added clues].

11*10 / 2 = 55 ways only

In the case below this gave me 60 18s in 90 seconds.

Every puzzle has these 5 equivalent clues somewhere within......
Code: Select all
+---+---+---+         +---+---+---+
|13.|...|..8|         |1..|...|...|
|...|6..|...|         |...|...|...|
|...|.9.|...|         |...|...|...|
+---+---+---+         +---+---+---+
|.2.|5..|.4.|         |...|5..|...|
|.7.|...|...|         |...|...|...|
|...|...|65.|         |...|...|6..|
+---+---+---+         +---+---+---+
|...|..8|..7|         |...|..8|...|
|5..|.3.|...|         |...|...|...|
|6.4|...|..9|         |...|...|..9|
+---+---+---+         +---+---+---+


Randomly pick one of the new 18s and repeat [keep the 5 constant clues and the 2 new clues].

gsf wrote:I think he(?) may picking up something
I'm missing from my submissions

The ony way I can see to do that is to do a {-0+3} on the common 14-clue subpuzzles from your new submissions. I dont know if its possible to have an easy look-up-table on this one. I suppose if there is 2 17s with a common 14-clue subpuzzle there might be a 3rd one.
C
coloin
 
Posts: 1633
Joined: 05 May 2005

Postby coloin » Fri Feb 29, 2008 11:59 pm

Finally I found a new 17-puzzle. [#47663] posted here

My attempts to generate truly random 18-puzzles didnt find me any new puzzles...worse, it didnt find me any of the 100 most recently discovered "remote" puzzles, which shows how poor my attempt was.

My recent discovery, - was either lucky or an indication that there are many more 17-puzzles out there.

I took ten 18s from a recently discovered puzzle [#47661] and performed about 6x{-1+1}. Two 17-puzzles emerged - the original and a "new" 17-puzzle. It had 11 common clues, but found rather too easily, considering I handn't got near a new one for the past 2 months !

Perhaps this is how Kohei Noshita is doing it ?

No doubt gsf's method of making 18s and finding new 17s is working......although the remoteness of the remaining puzzles means that any search which gets amongst the non-remote 18s wont give us new puzzles.

The notion that all minimal puzzles are in a multi-dimension "space" , linked by number of clues , common clues, grid solutions and of course isomorphs is too incomprehensible - but nevertheless exists.

The notion that all these [47664]x17-clue and [10^9]x18-clue [minimal and non-minimal] puzzles [along with their each of their 10^11 isomorphs] are integrated somehow is only slightly less incomprensible.

C
coloin
 
Posts: 1633
Joined: 05 May 2005

PreviousNext

Return to General