| View previous topic :: View next topic |
| Author |
Message |
| ChPicard
| | Joined: 12 Mar 2008 | | Posts: 82 | | : | | Location: Montreal, Canada |
Items |
|
 Posted: Sat Mar 07, 2009 9:44 am Post subject: Who wants to find a new 17 given sudoku? And maybe a 16? |
 |
|
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 |
|
 |
| gsf
| | Joined: 18 Aug 2005 | | Posts: 408 | | : | | Location: NJ USA |
Items |
|
| Posted: Sat Mar 07, 2009 4:14 pm Post subject: Re: Who wants to find a new 17 given sudoku? And maybe a 16? |
|
|
| 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 |
|
|
| zhouyundong
| | Joined: 22 Nov 2008 | | Posts: 43 | | : | |
Items |
|
| Posted: Tue Mar 24, 2009 1:51 pm Post subject: |
|
|
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 |
|
|
| ChPicard
| | Joined: 12 Mar 2008 | | Posts: 82 | | : | | Location: Montreal, Canada |
Items |
|
| Posted: Fri May 01, 2009 9:40 am Post subject: A seti-like search might increase the pace of discovery |
|
|
| 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 |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 408 | | : | | Location: NJ USA |
Items |
|
| Posted: Fri May 01, 2009 2:31 pm Post subject: Re: A seti-like search might increase the pace of discovery |
|
|
| 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
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 |
|
|
| humble_programmer
 | | Joined: 27 Jun 2006 | | Posts: 69 | | : | | Location: Colorado Springs, USA |
Items |
|
| Posted: Fri May 01, 2009 7:59 pm Post subject: |
|
|
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 |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 408 | | : | | Location: NJ USA |
Items |
|
| Posted: Fri May 01, 2009 8:10 pm Post subject: |
|
|
| 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 |
|
|
| coloin
| | Joined: 05 May 2005 | | Posts: 97 | | : | |
Items |
|
| Posted: Sat May 09, 2009 1:26 am Post subject: |
|
|
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 |
|
|
| coloin
| | Joined: 05 May 2005 | | Posts: 97 | | : | |
Items |
|
| Posted: Sun May 10, 2009 11:32 am Post subject: |
|
|
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 |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 408 | | : | | Location: NJ USA |
Items |
|
| Posted: Sun May 10, 2009 3:01 pm Post subject: |
|
|
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 |
|
|
| Lunatic
 | | Joined: 11 Mar 2007 | | Posts: 166 | | : | | Location: Ghent - Belgium |
Items |
|
| Posted: Tue May 12, 2009 7:37 pm Post subject: |
|
|
@ 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 |
|
|
| ChPicard
| | Joined: 12 Mar 2008 | | Posts: 82 | | : | | Location: Montreal, Canada |
Items |
|
| Posted: Tue May 12, 2009 7:56 pm Post subject: Special edition for you |
|
|
| 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 |
|
|
| Lunatic
| | Joined: 11 Mar 2007 | | Posts: 166 | | : | | Location: Ghent - Belgium |
Items |
|
| Posted: Tue May 12, 2009 8:46 pm Post subject: Re: Special edition for you |
|
|
| 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 
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~ |
|
| Back to top |
|
|
| ChPicard
| | Joined: 12 Mar 2008 | | Posts: 82 | | : | | Location: Montreal, Canada |
Items |
|
| Posted: Fri May 15, 2009 9:57 pm Post subject: 20 new in a row by gsf |
|
|
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 |
|
|
| coloin
| | Joined: 05 May 2005 | | Posts: 97 | | : | |
Items |
|
| Posted: Fri May 15, 2009 10:27 pm Post subject: |
|
|
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 |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
