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 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
ChPicard

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

Items
PostPosted: Sat Mar 07, 2009 9:44 am    Post subject: Who wants to find a new 17 given sudoku? And maybe a 16? Reply with quote

Hi everybody

Yesterday I found the number 48014 in the Gordon Royle's database, my fourth one.

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

I am not fast like Glenn Fowler or Kohei Noshita but
together : YES WE CAN.

The idea is that a new one must be "between" two known sudokus if they are all sorted in minlex form.

So I wrote an application which create a big batch of sudokus to test. I find the good ones thanks to a slightly modify version of the Bit_Based Sudoku Solver by Brian Turner:
http://www.setbb.com/phpbb/viewtopic.php?t=1668&mforum=sudoku

A file is also created to keep in memory the cursor's position between two known sudokus for next time when an another batch is created.

And finally, I verify if the good ones are in the Royle's database.

Who wants to find a new 17 given sudoku? And maybe a 16?

Send me a private message, and I will send you the tools for this quest.

My sources are available too.

Good luck everybody.

Jean-Pierre Sangin from Montreal, Canada.
Back to top
View user's profile Send private message
gsf

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

Items
PostPosted: Sat Mar 07, 2009 4:14 pm    Post subject: Re: Who wants to find a new 17 given sudoku? And maybe a 16? Reply with quote

ChPicard wrote:
Hi everybody
Yesterday I found the number 48014 in the Gordon Royle's database, my fourth one.

nice job
a seti-like search might increase the pace of discovery
Back to top
View user's profile Send private message Visit poster's website
zhouyundong

Joined: 22 Nov 2008
Posts: 43
:

Items
PostPosted: Tue Mar 24, 2009 1:51 pm    Post subject: Reply with quote

hi,ChipCard
I am intresting to 17 sodoku gerenator.
can you send me the source code?
my email is lao_zhouxi9@163.com
Back to top
View user's profile Send private message Send e-mail
ChPicard

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

Items
PostPosted: Fri May 01, 2009 9:40 am    Post subject: A seti-like search might increase the pace of discovery Reply with quote

gsf wrote:
ChPicard wrote:
Hi everybody
Yesterday I found the number 48014 in the Gordon Royle's database, my fourth one.

nice job
a seti-like search might increase the pace of discovery



Hi Glenn

The search for new 17 given sudokus seems without end. You find several new each week. I suppose you own many computers but overall a good software. Everybody here knows YOU are the wizard of sudoku programming.

My question now:

Could we participate with you? It is sure that if somebody finds THE 16 GIVEN SUDOKU (if it exists), you will be credited for the discovery.


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

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

Items
PostPosted: Fri May 01, 2009 2:31 pm    Post subject: Re: A seti-like search might increase the pace of discovery Reply with quote

ChPicard wrote:
gsf wrote:
ChPicard wrote:
Hi everybody
Yesterday I found the number 48014 in the Gordon Royle's database, my fourth one.

nice job
a seti-like search might increase the pace of discovery

The search for new 17 given sudokus seems without end. You find several new each week. I suppose you own many computers but overall a good software. Everybody here knows YOU are the wizard of sudoku programming.

My question now:

Could we participate with you?

first, credit goes to the discoverer

at this point most feel that there won't be a 16
so besides the very slim chance there is a 16
I'm interested in seeing if we can narrow down on the total number of 17s up to isomorphism

I don't own the machines but there are several multi-core pentiums at my disposal that would otherwise be idle
typically I have 8 doing a random search
the search space is sparse enough that the searches are independent
(meaning there is little probability for two random searches to produce the same 17)

I use my solver in a two stage pipeline for each random search
the first stage generates hardish puzzles with clue counts in the lower 20s
hardish basically means the diagonal pattern that is prevalent in the hardest puzzles

the reason for seeding with hard puzzles is that most searching up to this point
has probably been done with unfiltered random starting puzzles
filtering different seed puzzles might tickle different parts of the search space

the first phase generates the seed puzzles for the second phase:
Code:
sudoku -gp -m1 -e "C<=22||M>0" -q2 -f"%v # %T %5r %(C)x %q %(CSM)#c#/q"

use the --man option to decipher the options (that's a puzzle in itself!)

the second phase uses the first phase as input and does one of a few different actions based on #clues

clues < 17
Code:
double and triple check the results

clues == 17
Code:
check against the 17s catalog

clues == 18
Code:
sudoku -ze3000000 -go{-1+1}x4{-2+1} -f%#0v

clues < 23
Code:
sudoku -ze3000000 -go{-2+1}xN{-1+1}x4{-2+1} -f%#0v

where N=clues-18

clues == 23
Code:
sudoku -ze3000000 -go{-3+1}{-2+1}x4{-1+1}x4{-2+1} -f%#0v

clues >= 24
Code:
skip


to check the 17s catalog I keep a local copy in canonicalized -f%c form
canonicalize each generated 17, and check if its in the catalog
if not then its entered via gordon's site

all of this is glued together with shell scripts on unix (linux)
so its all hands free
but it shouldn't be a problem running one of these manually

with 8 ~2Ghz pentiums this process hits a few per week

I encourage others to use up spare cycles
you can start with my solver or maybe sprinkle in your own code
my solver has a bazillion options so it can be experimented with
maybe you can come up with option combinations that will tickle another part of the search space


Last edited by gsf on Sat May 09, 2009 6:20 am; edited 1 time in total
Back to top
View user's profile Send private message Visit poster's website
humble_programmer

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

Items
PostPosted: Fri May 01, 2009 7:59 pm    Post subject: Reply with quote

I'm using the "2008-11-04 BASE" release of ast-sudoku, and neither it nor I recognize the -ze parameter. Care to enlighten the ignorant?
_________________
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: 411
:
Location: NJ USA

Items
PostPosted: Fri May 01, 2009 8:10 pm    Post subject: Reply with quote

humble_programmer wrote:
I'm using the "2008-11-04 BASE" release of ast-sudoku, and neither it nor I recognize the -ze parameter. Care to enlighten the ignorant?

aha
I'll be posting an ast src update later today
it will include ast-sudoku

since I'm running out of option letters -z will be a catchall
from the earth day sudoku
Code:
  -zX  Miscellaneous options (only -I is free!).  X may be:
        8  Octdoku: all clues with value 9 present and not subject to minimization.
        b  Set the process priority to "nice" ("background").
        eN Exit with a diagnostic when any dictionary entry count exceeds N.

so -ze limits the memory consumption
it doesn't know how much is available
so the value will differ from system to system and also depend on dynamic usage by other processes
Back to top
View user's profile Send private message Visit poster's website
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Sat May 09, 2009 1:26 am    Post subject: Reply with quote

Thanks for the insight into how these very remote new 17s are being found.

Obviously, it is working - because you are finding new puzzles !

We find 17s from 18s.

working the other way..........

common 17s have ~ 200-500-1000 associated 18s
remote 17s have ~ only 100 associated 18s

However, back of the envelope estimates here :

Number of 18s : ? 1 billion
Number of 17s : ~ 48000
Number of 17s not yet found ? 1000

18s which are not {-2+1} to an 17 = 976,000,000
18s which are {-2+1} to a 17 = 500 x 48000 = 24,000,000
18s which are {-2+1} to a new as yet unfound 17 = 100 x 1000 = 10,000

ratio to old to new is 2400 to 1 which is about right ?

ratio of useless 18s to 18s we want to find is 100,000 to 1

THis might indicate that the best way to find the rest of these 17s is to generate random 18s.

Your {-1+1} at the end of your sequence doesnt really do this efficienty perhaps.

I have long been thinking that a roving {-2+2} on 18s would be a good way to get into the remote areas ?

A roving {-2+2} takes about the same time as a {-2+1} so the process can run in parallell.

A roving {-1+1} plus a non-minimality check would defintely be extremly quick !!!!!!!!!!!!

Just a thought, perhaps your technique and the roving one could be compared.

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

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Sun May 10, 2009 11:32 am    Post subject: Reply with quote

Well, before anyone tries to program a roving {-1+1} or a {-2+2}......I did a bit of human roving to see how would work.

Simply doing a repeditive {-1+1} on a random 18.......has a rather curious effect. It seems that many of the clues tend to be "fixed" and only a certain of the clues change !

For example I did a selective x7{-1+1}
to get from this puzzle
Code:
................12...345........1......26...1.35.....9....7.3.82........6.1......
to this puzzle
...............412...385........1......2.9.61.38..........7.3..2.1......9........

which with remorphing probably 2 more clues are similar.

this is selective - if you did a random {1+1} you get nowhere near this separation.....
Code:
................12...345........1......26...1.35.....9....7.3.82........6.1......
with 10 random {-1+1}to
................12...345........1...7..26...1.35....9.....8.3..2........6.1......

usually only 2 or 3 clues are mutable/tranferable each puzzle

The {-2+2} case takes a lot longer and it is easy to get into remote 18s which dont go anywhere.......

Which leads me to think the way these 18s are interconnected is very complex !

gsfs method would appear to be successful in finding true random 18s, with a little bit of {-1+1} and a final {-2+1} ultimately givving rise to the occaisional new puzzle.
Back to top
View user's profile Send private message
gsf

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

Items
PostPosted: Sun May 10, 2009 3:01 pm    Post subject: Reply with quote

sudoku 2009-05-10 (US mother's day commemorative edition) just posted
it has a minor change to allow representing the 17 search strategy mentioned above with one -go... option
Code:
-go{-3+1}:23{-2+1}:18{-1+1}x4{-2+1}

:n applies the preceding op 0 or more times until the #clues is <= n
so {-3+1}:23 gets the seed puzzles near 23 clues
{-2+1}:18 gets them down to 18 clues
{-1+1}x4 explores the 18's a bit
and the final {-2+1} attempts to get 17's from the 18's


Last edited by gsf on Tue May 12, 2009 10:37 pm; edited 1 time in total
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: Tue May 12, 2009 7:37 pm    Post subject: Reply with quote

@ CHPicard

Hallo Jean-Pierre,

I have a question about Create_New_BatchV5.exe

Isn't it possible to make this program accepting options ?
For now, we have to type in the name of the Cursor-file and the amount of sudokus we want to generate, AND after that we have to confirm our input once more.

If Create_New_BatchV5.exe would accept options we could simply type the following at the prompt (example):

Create_New_BatchV5 Cursor1.txt 200000

Confirmation should be skipped then.

The benefit of this would be that it will be easier to automatize the proces by using batch files.

For now, i have written some batch files to automatize the proces, but i still have to fill in the filename, the amount and confirmation each loop for Create_New_BatchV5.exe

*************************************************************
EDIT

With the new 'special' version i got from Jean-Pierre (Create_New_BatchV7.exe), i got the search completely automatized. After some 'test runs', these are the resulting 3 batch files i use:


The first one is called QuestFor17.bat
Code:
@echo off
echo ************************
echo * Quest for 17 Sudokus *
echo ************************
echo.
if exist StartQuest.dat goto QUESTBUSY
echo Start Quest >StartQuest.dat
echo Start HaltQuestFor17.bat to interrupt the Quest
echo Press any key to start...
pause>NUL
:STARTLOOP
for %%i in (Cursor*.txt) do call GenerateAndCheck %%i
if not exist HaltQuest.dat goto STARTLOOP
del HaltQuest.dat
del StartQuest.dat
goto ENDQUEST
:QUESTBUSY
echo Quest for 17 is allready running.
echo Press any key to close...
pause>NUL
:ENDQUEST


The second one is called GenerateAndCheck.bat
Code:
@echo off
cls
echo *********************************
echo   Current file is %1
echo *********************************
echo.
set tempname1=%1
set tempname1=%tempname1:Cursor=%
set tempname1=%tempname1:.txt=%
Create_New_BatchV7 %tempname1% 200000
set tempname1=%1
set tempname1=%tempname1:Cursor=-IGRIDSCursor%
set tempname2=%1
set tempname2=%tempname2:Cursor=-OGOODCursor%
echo.
echo BBSolver is busy checking generated grids
BBSolver -P %tempname1% %tempname2%
echo.
echo BBSolver has finished checking grids
echo.
copy %1 .\Done\%1
if exist .\Done\%1 del %1
set tempname1=%tempname1:-IG=G%
set tempname2=%tempname2:-OG=G%
if exist %tempname2% del %tempname1%
copy %tempname2% .\Good\%tempname2%
if exist .\Good\%tempname2% del %tempname2%
set tempname1=
set tempname2=


The third one is called HaltQuestFor17.bat
Code:
@echo off
if not exist StartQuest.dat goto NOTRUNNING
echo Halt Quest >HaltQuest.dat
echo The Quest for 17 sudokus will be halted when checking of the current file is completed.
goto ENDHALT
:NOTRUNNING
echo The Quest for 17 sudokus is not running.
echo Run QuestFor17.bat to start the Quest.
:ENDHALT
echo Press any key...
pause>NUL


END OF EDIT
*************************************************************


All are to be placed in the same folder where your files are located.
Two subfolders are to be created in that folder: 'Done' and 'Good'
The cursor files that are done are moved to the subfolder 'Done'
The results (GOODCursor files) are moved to the subfolder 'Good'
The sources (GRIDSCursor files) are deleted after succesful processing.

The Quest is started by running QuestFor17.bat
The Quest is interrupted by running HaltQuestFor17.bat

Remark: Only the last Cursor file generated by Create_New_BatchV7 may remain in the main folder when starting QuestFor17.bat (Normally, when working with those batch files, this will be the case).
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~


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

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

Items
PostPosted: Tue May 12, 2009 7:56 pm    Post subject: Special edition for you Reply with quote

Quote:
@ CHPicard

Hallo Jean-Pierre,

I have a question about Create_New_BatchV5.exe

Isn't it possible to make this program accepting options ?
For now, we have to type in the name of the Cursor-file and the amount of sudokus we want to generate, AND after that we have to confirm our input once more.

If Create_New_BatchV5.exe would accept options we could simply type the following at the prompt (example):

Create_New_BatchV5 Cursor1.txt 200000

Confirmation should be skipped then.

The benefit of this would be that it will be easier to automatize the proces by using Batch files.



Hi Lunatic

If you want, I can send you a special edition. Always 200 000 grids, no confirmation and only the number X in the files CursorX.txt.

Do you agree?

If you want the source, it is in Pascal.
Back to top
View user's profile Send private message
Lunatic

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

Items
PostPosted: Tue May 12, 2009 8:46 pm    Post subject: Re: Special edition for you Reply with quote

ChPicard wrote:
If you want, I can send you a special edition. Always 200 000 grids, no confirmation and only the number X in the files CursorX.txt.

Do you agree?


So, for example, Cursor12.txt....

Create_New_BatchV5 12

....would be enough ?

That would be very nice Very Happy
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
ChPicard

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

Items
PostPosted: Fri May 15, 2009 9:57 pm    Post subject: 20 new in a row by gsf Reply with quote

Hi

Sorry but the method described by Glenn Fowler is the best. I give up. He found 20 new 17 given sudokus in a row this week.

Congratulations

Glenn, did you improve again your method or is it a pure chance?

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

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Fri May 15, 2009 10:27 pm    Post subject: Reply with quote

In many respects the whole thing,17-puzzles and finding new 17-puzzles is pure chance.

However , experiments I have done would indicate that from the 18-puzzle stage, an improvement might be :

go{-1+1}x4{-2+1}

to - omit the 1,2 and 3 generation 18s and only do the {-2+1} on the 4th generation 18s.........

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 1, 2, 3, 4  Next
Page 1 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