Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Who wants to find a new 17 given sudoku? And maybe a 16?
Goto page Previous  1, 2, 3, 4  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Sun May 24, 2009 4:46 pm    Post subject: Reply with quote

gsf wrote:
Lunatic wrote:
With the new 'special' version I got from Jean-Pierre (Create_New_BatchV7.exe), I got the search completely automatized.

this searches the gaps in the minlex ordered 17 catalog?


Yes. According to ChPicard: The idea is that a new one must be "between" two known 17 sudokus if they are all sorted in minlex form.

gsf wrote:
are there any back of the envelope calculations that estimate the work required for each (or any) gap?
(this next question is not sarcastic -- I've had plenty of false starts on long running programs, sudoku or not)


Not that I am aware off, maybe ChPicard can answer that question.

gsf wrote:
you've been running this for a week or so, I'm guessing with no hits, how do you know its working?


Well, I have the files since March 8, but found it annoying that I have to keep my attention on the progress, and have to retype the commands again and again for each big batch of sudokus to check. Anyway, after that I recieved a new executable without any need of user interaction, I started all over, and that's about a week ago. For now I tested 110 batches with 200000 sudokus each, and no hits.

I hope it works. Does anyone else, who is participating, had any hits ?
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
gsf

Joined: 18 Aug 2005
Posts: 408
:
Location: NJ USA

Items
PostPosted: Sun May 24, 2009 5:16 pm    Post subject: Reply with quote

Lunatic wrote:
For now I tested 110 batches with 200000 sudokus each, and no hits.

is there a relationship between gap and batch?
Back to top
View user's profile Send private message Visit poster's website
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Sun May 24, 2009 6:32 pm    Post subject: Reply with quote

EDIT: (in darkred)
A 'batch' of sudokus is just a file of sudoku data generated with Create_New_BatchV7.exe to be processed with one execution of BBSolver. I have no idea on how many 17 sudokus there are in the 'gap' between two puzzles. At the same time, Create_New_BatchV7.exe creates a file (CursorX.txt, where X is an increasing number) to keep in memory the cursor's position between two known sudokus for next time when another batch is created.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~


Last edited by Lunatic on Mon May 25, 2009 9:54 am; edited 1 time in total
Back to top
View user's profile Send private message Send e-mail Visit poster's website
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Mon May 25, 2009 7:55 am    Post subject: Reply with quote

The " gap" between the puzzles consists of min lex 17-templates and clues iterated over these templates.

If there are fewer templates "between" the puzzles - a search might be quicker in some cases.

Edit......On looking at the minlex 17-puzzles.....the gaps look impossibly large. Also [probably] only a few of the gaps will contain a new puzzle.

C
Back to top
View user's profile Send private message
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Mon Jun 01, 2009 10:40 pm    Post subject: Reply with quote

No sign of letting up, still gsf is getting 20 new 17s a day......hmmm.

I have persevered with fixing 8 clues..........and a new 17 [#48306] came out of a batch of 150 17s.... [with my single core]

Either lucky or something in it !

I have no doubt that making 18s with a knockdown process preferentially gets us into regions near non-remote 17s.

By generating 18s with a {-2+2}, but with 8 clues fixed, it perhaps gives a more random selection of 18s to do a final unfixed {-2+1}.

Next batch completes soon.......EDIT......300 17s, of which none were new....none of the last 400 "new" puzzles were even found.

So the {-2+2} isnt an improvement on getting the remote 18s.

C
Back to top
View user's profile Send private message
humble_programmer

Joined: 27 Jun 2006
Posts: 69
:
Location: Colorado Springs, USA

Items
PostPosted: Fri Jun 12, 2009 5:28 pm    Post subject: Reply with quote

gsf wrote:
sudoku 2009-05-10 (US mother's day commemorative edition) just posted


The most recent version on your web site appears to be 2009-05-05...
_________________
Cheers!
Humble Programmer
,,,^..^,,,
www.humble-programmer.com
Back to top
View user's profile Send private message Visit poster's website
gsf

Joined: 18 Aug 2005
Posts: 408
:
Location: NJ USA

Items
PostPosted: Sat Jun 13, 2009 2:08 am    Post subject: Reply with quote

humble_programmer wrote:
gsf wrote:
sudoku 2009-05-10 (US mother's day commemorative edition) just posted

The most recent version on your web site appears to be 2009-05-05...

ast-sudoku.2009-05-10.tgz just posted
this contains the source for the 2009-05-10 sudoku.exe already posted
hope to see some entries in gordon's catalog
Back to top
View user's profile Send private message Visit poster's website
gsf

Joined: 18 Aug 2005
Posts: 408
:
Location: NJ USA

Items
PostPosted: Thu Aug 06, 2009 6:12 am    Post subject: Reply with quote

the minlex gaps in the 17s catalog can be organized by common prefixes when the entries are sorted

consecutive entries will contain a common prefix of one or more clues followed by the remaining positions

a gap search fills in the remaining positions to make 17 clues and then checks if the 17 is valid

a complete gap search checks all (minlex) combinations of (17 - sizeof(prefix)) clue past the prefix for valid 17s

once a complete search is done on a gap it never has to be searched again

here is a table of (17-sizeof(prefix)) vs # of gaps
e.g., 5 2077 means there are 2077 gaps that have a common prefix of 12=(17-5) clues
the table does not take into account that a larger gap may contain smaller gaps
Code:
# |G|=48780 minlex gaps # 2009-08-06+05:10:11-0000 #
 1   749
 2  1083
 3  1491
 4  1657
 5  2077
 6  3135
 7  4020
 8  5191
 9  8721
10 10170
11  7193
12  2596
13   517
14   121
15    44
16     9
17     5

I ran my solver over the smaller gaps
gaps <=3 typically take seconds to to a complete search
gap=4 take minutes, gap=5 hours, gap=6 days (haven't finished one of those yet)

if we pick a max gap size we are willing to completely search
then the covered smaller gaps can be identified and eliminated before searching

gap size 6 from the table above seems doable in a year or so -- this results in the following gap table
Code:
1   331
2   548
3   836
4   920
5  1330
6  2565

after a few hours I have a search that is just about done with the 3's (1s 2s already done, no new 17s)

larger gaps seem intractable at the moment -- maybe there are some combinatorial insights that will prune the search space

you can use the 2009-07-17 version of my solver to search a gap
Code:
-go{+5}@

will clear the last 5 clues in each input puzzle and the do a +5 on search on the trailing 0's (positions with no clues)
i.e., it will check all combinations of 5 clues in all the rightmost minlex positions that contain no clues
Back to top
View user's profile Send private message Visit poster's website
ChPicard

Joined: 12 Mar 2008
Posts: 82
:
Location: Montreal, Canada

Items
PostPosted: Fri Aug 07, 2009 10:28 pm    Post subject: Command line Reply with quote

Code:
-go{+5}@



Hello

Could you give the complete line command?

Is it something like?

sudoku grids.txt>validgrids.txt -go{+5}@

Thank you
Back to top
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 408
:
Location: NJ USA

Items
PostPosted: Sat Aug 08, 2009 4:19 am    Post subject: Re: Command line Reply with quote

ChPicard wrote:
Code:
-go{+5}@

Could you give the complete line command?

Is it something like?

sudoku grids.txt>validgrids.txt -go{+5}@

Thank you

sure, either of these will do
Code:
sudoku -go{+5}@ grids.txt > valgrids.txt
sudoku -o valgrids.txt -go{+5}@ grids.txt

I'd like to hear how this compares to what you and others have been doing

btw, the 6 gap one guestimated in a previous post to take ~days took 1.5 days
Code:
sudoku -go{+6}@ 000000000000000001000023000000400020005000360007100000010050000840000000030060090

it only produced 2 17s, the input one and this one
Code:
000000000000000001000023000000400020005000360007100000010005000840000000030002090
Back to top
View user's profile Send private message Visit poster's website
ChPicard

Joined: 12 Mar 2008
Posts: 82
:
Location: Montreal, Canada

Items
PostPosted: Sat Aug 08, 2009 9:22 am    Post subject: Re: Command line Reply with quote

Code:
sudoku -go{+5}@ grids.txt > valgrids.txt
sudoku -o valgrids.txt -go{+5}@ grids.txt


Hello Glenn

Is there an option to remove one given and check all combinations of clues in all the rightmost minlex positions. I want to try with the 22 millions 18 given sudokus from Royle's database.

Thank you
Back to top
View user's profile Send private message
ChPicard

Joined: 12 Mar 2008
Posts: 82
:
Location: Montreal, Canada

Items
PostPosted: Sat Aug 08, 2009 10:28 am    Post subject: Gap between 2 consecutive 17 given sudokus in minlex form Reply with quote

Code:
# |G|=48780 minlex gaps # 2009-08-06+05:10:11-0000 #
 1   749
 2  1083
 3  1491
 4  1657
 5  2077
 6  3135
 7  4020
 8  5191
 9  8721
10 10170
11  7193
12  2596
13   517
14   121
15    44
16     9
17     5


I like your idea Glenn. Is it possible to evaluate the number of possible grids (valid or not) between two consecutive 17 given sudokus in the minlex form and then to create equivalent batches for searching, say 500 millions grids to verify in a computer day?

Jean-Pierre Sangin
Back to top
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 408
:
Location: NJ USA

Items
PostPosted: Mon Aug 10, 2009 4:36 am    Post subject: Re: Command line Reply with quote

ChPicard wrote:
Code:
sudoku -go{+5}@ grids.txt > valgrids.txt
sudoku -o valgrids.txt -go{+5}@ grids.txt


Hello Glenn

Is there an option to remove one given and check all combinations of clues in all the rightmost minlex positions. I want to try with the 22 millions 18 given sudokus from Royle's database.

Thank you

I'm pretty sure at least a one off test has been done on the 22M 18s

-go{+1}@ will remove the rightmost clue and check all of the right most 0's with every combination of 1 clue

you can use one pass of -go{-1} to remove all combinations of 1 clue
and then another pass to do some minlex checks
Back to top
View user's profile Send private message Visit poster's website
gsf

Joined: 18 Aug 2005
Posts: 408
:
Location: NJ USA

Items
PostPosted: Mon Aug 10, 2009 4:41 am    Post subject: Re: Gap between 2 consecutive 17 given sudokus in minlex for Reply with quote

ChPicard wrote:
Code:
# |G|=48780 minlex gaps # 2009-08-06+05:10:11-0000 #
 1   749
 2  1083
 3  1491
 4  1657
 5  2077
 6  3135
 7  4020
 8  5191
 9  8721
10 10170
11  7193
12  2596
13   517
14   121
15    44
16     9
17     5


I like your idea Glenn. Is it possible to evaluate the number of possible grids (valid or not) between two consecutive 17 given sudokus in the minlex form and then to create equivalent batches for searching, say 500 millions grids to verify in a computer day?

Jean-Pierre Sangin

don;t know how to count or estimate the # minlex grids between two minlex grids

the -go{+N}@ option generates the "batch" on the fly and generates all possible grids in the selected gap

right now most of the gaps (size >= 7) seem out of our reach
Back to top
View user's profile Send private message Visit poster's website
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Fri Aug 21, 2009 7:45 pm    Post subject: Reply with quote

Search still ongoing I see ....

gsf wrote:
don;t know how to count or estimate the # minlex grids between two minlex grids


Isnt it the number of minlex templates between the minlex puzzles that is perhaps important ?

Aside from that......maybe an idea would be to sub-devide our puzzles and do a selective search between them. It might make a bigger search possible. If it can be programmed easily.

those with 8 clues
those with 9 clues

[EDIT] I tried this - put the minlex puzzle or the puzzle from the minlex grid solution didnt really throw up small enough gaps.

or more problematic but Idea

incorporate into the searching program the features of a repeating minirow. [minlex band 1 > 30/416]

Those minlex puzzles without a repeating minirow [initial bands 31-416] . The gap could be searched with a "do not try to make a puzzle with a repeating minirow" function.

C
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Goto page Previous  1, 2, 3, 4  Next
Page 3 of 4

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron