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
gsf

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

Items
PostPosted: Sat May 16, 2009 1:39 am    Post subject: Reply with quote

coloin wrote:
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.........

I reposted my solver 2009-05-10 (Mother's day) with a fix for the : notation for:
Code:
-go{-3+1}:23{-2+1}:18{-1+1}x4{-2+1}

coloin's final 18 => 17 transition is in there
again this means:
apply {-3+1} until #clues <= 23
then apply {-2+1} until #clues == 18
the apply {-1+1} 4 times to tour around the 18s
then apply {-2+1} to check for 17s
-go{2} ({-2+2} closure) is done for each new 17

I apply that to 22s and 23s generated by my solver

yes, its all up to chance, because to now the actual and proposed searches
are based on (pseudo)random seed puzzles
besides some insights on seed generation (or insights on the structure of 17s)
the best we can do is throw more warm cpus at the search ...
ChPicard wrote:
did you improve again your method or is it a pure chance?

its pseudo-random chance
and ...
I have a ~512 core collections of machines at my disposal
its in the early stages and there were requests to stress the setup
I obliged this week
first with 16 searches using the above -go option
there was a bug where the new discovery script did not contact gordon's site
thankfully the logs saved the day (always log long running computations to help error/catastrophe recovery)
that wast the batch of 9 yesterday
I ramped up to 256 today
I'm hoping this will hit ~10/day for a bit
barring a meltdown I'll add another 128 monday
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 16, 2009 11:19 am    Post subject: Reply with quote

gsf, must pat you on the back for your perseverence on the 17-clue project. The random nature of the search probably means that we wont have a satisfactory outcome. [i.e we will never know when we reach the end]

I think I have a means to approach this perhaps more satisfactorly. I have reached the llimit of my capabilities but berhaps you can extend it.

It might be just possible to perform a concentrated directed search.........

Bear with me...........here is another insight Idea

two of the rules for a 9*9 puzzle

1. must have 8 clue values
2. must have at least one clue in the 18 loci in two rows within a band.

Code:
+---+---+---+
|***|***|***|
|***|***|***|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+  example of 18 loci within a band

Here are two examples of an [min-lex] 8 clue subpuzzle [ML8], It has clues 1-8, There is at least one clue in all the 18 clue double-rows
Code:

+---+---+---+
|...|...|...|
|...|...|..1|
|...|...|..2|
+---+---+---+
|...|...|...|
|...|...|..3|
|...|...|.4.|
+---+---+---+
|...|...|...|
|...|..5|...|
|.67|.8.|...|
+---+---+---+

+---+---+---+
|...|...|...|
|...|...|..1|
|...|...|.2.|
+---+---+---+
|...|...|...|
|...|..3|...|
|..4|...|...|
+---+---+---+
|...|.5.|...|
|..6|..7|...|
|.8.|...|...|
+---+---+---+

OK.......so the rule will be the ML8 has an 8 and there is a 1 at r2c9

I believe there are 1131 different ways to have these specific ML8
Code:
      1  .................1........2.................3.......4...............5....67.8....
      2  .................1........2.................3.......4..............56....78......
      3  .................1........2.................3.......4............5..6....7..8....
   ****                                                                                     
   1129  .................1.....2..........3.......4....5..........6.....7.......8........
   1130  .................1.....2..........3.....4......5............6.....7......8.......
   1131  .................1.....2..........3.....4......5............6...7.......8........

perhaps almost all will be associated with a known 17-puzzle.

I have looked at various 17 puzzles using your software. 17 !/ 8! * 9! = 24310, 17-puzzles have around 21000 different 8clue patterns [so around ~15% dups maybe]

Counting these ML8s [with a 1@r2c9] from a few 17-puzzles ...
Code:
a random 17-puzzle  - 10-20 on average
A puzzle from the SF range had only - 5.
A few puzzles didnt have any [8 clues, empty rows]

71 random 17-puzzles 563 different ML8s,
71 random 17-puzzles 551 different ML8s
71 random 17-puzzles [47,000+] - 488 different ML8s
these 213 17-puzzles had  763 different ML8s


With these 8 clues fixed there will be many ways [?] to make a 17-puzzle - but perhaps not as many as you would expect ! With a little thought the reasons for this and possible advantages of this clue restriction will become apparent.

Almost all the puzzles will not be isomorphic......[although there will be an isomorph if the puzzle has two instances of the particular 8-clue, it wont happen that often.]

So.............................. starting from all the known 17s which have one particular 8-clue pattern, and these all morphed to that pattern.

We could easily generate the 18s [via {-1+2}] with these clues fixed. We could continue to perform {-1+1} on these 18s for a good few rounds. By insisting on only searching for puzzles which have those fixed clues there wont be that many new ones produced each time.

A subsequent {-2+1} on the new generated 18s could be performed. [again keeping these clues fixed - x4 quicker ]

The number of new 17s - [if any] would be revealing........

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

Joined: 24 Apr 2009
Posts: 52
:

Items
PostPosted: Sat May 16, 2009 9:46 pm    Post subject: Reply with quote

you can also do canical form restrictions

to the pattern as

if you assume the first row ording in resolution path

must be = 1,2,3,4,5,6,7,8,9

then none issomorphs would be generated.

for a higher % of the random generated grids.

this would aslo disable puzzles patterns that cannot compelte the restiction as welll..

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

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Sat May 16, 2009 11:06 pm    Post subject: Reply with quote

I await a formal work out of the frequency of these ML8s with a 1 @ r2c9 in all the 17-puzzles. {located 1045 out of 1131 for 1000 puzzles}

there will be a few isomorphs - if a puzzle has 2 different occurances of the ML8, await how common this is too. The fixing of the 1,2,3,4,5,6,7,8 clues fixes 8! isomorphs. I dont think fixing the first row will help.

In fixing the clues there will be speed up in the all the processes [if easily programmed] not just the final one.

The problem may arise that the {-1+1} extension on the 18s dries up......but hopefully this may not happen. There will be many more 18s with the ML8, hopefully not too many. I would be hopeful that the restricted search space could be completely trawled by a repeditive 18 generation process.

Is there a flaw in this ?

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

Joined: 24 Apr 2009
Posts: 52
:

Items
PostPosted: Sun May 17, 2009 12:14 am    Post subject: Reply with quote

Quote:
there will be a few isomorphs - if a puzzle has 2 different occurances of the ML8, await how common this is too. The fixing of the 1,2,3,4,5,6,7,8 clues fixes 8! isomorphs. I dont think fixing the first row will help.


not fixing the first row,

comparing solution states to the first row.

if the alloted grid solution in depth checking results in a row out side of 1-9

then its likely an issomoprh of a combination...

basically i see it as.

1 2 3 4 5 6 7 8 9 (are requirmenst not fixed cells)

your fixed sells are the pattern of 8 digits.

valid none issomorphs can only solve as 123456789 as the top row.

and random grids generated from the pattern can only use 1-9 in the first row in canical form.

but the rows solution must equal 1-9...in canacal form.


i see it as fixing space with a pattern limit.

then generating all grids off the fixed pattern compared to the restraint in combinations on the row.
.
i figure that would get rid off all the issomorphs.??? or im just thinking odd.
Back to top
View user's profile Send private message
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Sun May 17, 2009 1:07 am    Post subject: Reply with quote

I think we tried that when searching for puzzles in their form where the solution grid has the constant min-lex clues here. searching for new puzzles in the "gaps". The gaps proved to be too big in most cases and there are 48000 gaps. What "fixing" clues does is to reduce the search space, but this reduces the effectivness of our generation {-1+1} methods.

gsf's and havard's programs both do an isomorph check each time a puzzle is generated, comparing it to the previous puzzles in the file......except here the problem will not be recurrent isomorph generation [for once !] which will speed up the process even more if we omit the check.

The difficulty will be in extending the 18 clue puzzles with a {-1+1} with the 8 fixed clues.

Because there are few isomorphs the puzzle space will be considerably sparser. [but still a big reduction of a very big space !]

If there are 500 known 17s [1/100 of the total] with the pattern, and we dont expect there to be many more new 17s, but there will still be very many 18s. [1/100th = 10 million?] Lets hope the {-1+1} extends the 18 space easily and quickly.
Back to top
View user's profile Send private message
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Mon May 18, 2009 8:20 am    Post subject: Reply with quote

gsf massive effort !in getting >100 new 17s..............quite possibly this could be the final steps....

I have been slowly exploring the extent to which an 18 subjected to {-1+1} with 8 fixed clues expands to the "space". It potentially could be very very quick, but i have no idea if programming it is feasible. Havard did mention a fixing clues facility which probably wouldnt be too difficult with his GUI...but he seems to have retired.
This 17
Code:
.3...............1...1..6.22......4....7.8.3...4..5......3........26.....7.....8.
has this ML8
Code:
                                                                               
.................1........2................3...4..5................6.....7.....8.

and plenty of directions with {-1+1}
Code:
13...............1.....46.22......4.....78.3...4..58..............26.....7.....8.
.3..5............1......6.22......4....7.9.3...4..58.....3........26.....7.....8.
.3..5...4........1......6.22...........7.8.3...4..5......3........26.4...7.....8.
.3..5............1......6.22......4....7.8.3...4..5......1........26.4...7.....8.
.3..9............1......6.22......4....7.9.3...4..58.....3........26.....7.....8.
.3...........5...1......6.22......4....7.9.3...4..58.....3........26.....7.....8.
.3...........9...1......6.22......4....7.9.3...4..58.....3........26.....7.....8.
.3..5............1......6.22......4....9.7.3...4..58.....3........26.....7.....8.
.3..5...4........1......6.22...........7.8.3...4..5......1........26.4...7.....8.
.3..9............1......6.22.9....4......8.3...4..59.....3........26.....7.....8.
.3..5............1......6.22......4....7.8.3...4..5......1........26...4.7.....8.
.3..........9....1......6.22.9....4......8.3...4..59.....3........26.....7.....8.
..........8......1...1..6.22......4....7.8.3...4..5............9..26.....7.....89
.8...............1...1..6.22...........748.3...4..5............9..26.....7.....89
..........8......1...1..6.22......4....7.8.3...4..5..............926.....7.....89


Of coure we probably have many seeds from all those other 18s we have generated. To use those we would need a "identify a subpuzzle" -> "morph to this" facility.

To search the large number of minimal and non-minimal 18s made - I suggest easy {-1+0} ....this checks ~ 2M per hour !

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

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

Items
PostPosted: Wed May 20, 2009 10:03 pm    Post subject: How to be up to date with Royle's list? Reply with quote

Hi

Now gsf finds a new 17 given sudoku each hour. It is difficult to be up to date .

How to reach EASILY the new ones?

Is it possible to pick a new # with an address like this :

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

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

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

Items
PostPosted: Thu May 21, 2009 12:49 am    Post subject: Re: How to be up to date with Royle's list? Reply with quote

ChPicard wrote:
Hi

Now gsf finds a new 17 given sudoku each hour. It is difficult to be up to date .

How to reach EASILY the new ones?

Is it possible to pick a new # with an address like this :

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

if you put the puzzle number in the grid field it retrieves that puzzle
right now there are 48213 puzzles in the catalog
if your local db only has up to 48210
then you just enter 48211 through 48213 to pick up the 3 new ones
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: Thu May 21, 2009 8:34 am    Post subject: Re: How to be up to date with Royle's list? Reply with quote

gsf wrote:
ChPicard wrote:
Hi

Now gsf finds a new 17 given sudoku each hour. It is difficult to be up to date .

How to reach EASILY the new ones?

Is it possible to pick a new # with an address like this :

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

if you put the puzzle number in the grid field it retrieves that puzzle
right now there are 48213 puzzles in the catalog
if your local db only has up to 48210
then you just enter 48211 through 48213 to pick up the 3 new ones


Thanks Glenn

My local database has up to 48158 and after 2 or 3 days late, I must go from 48158 to 48215, no 48216, no 48217, no 48218....

The source is:


<form action="/gordon/sudokuid.php" method="POST"

Enter your details: (optional)<br>
Name:
<input type="text" name="name" size="64" value="Anonymous "
<br>
Email:
<input type="text" name="email" size="64" value="anon@anon.com" <br>

<br>

Enter your puzzle: <br>
<input type="text" name="puzzle" size="81" value="605000000000002708300900000070000000000001050000000061001000300009600000000000200"
<br>
<input type="submit" value="Identify Me!"

</form>



Can we do something with that?

Thanks again
Back to top
View user's profile Send private message
gsf

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

Items
PostPosted: Thu May 21, 2009 1:20 pm    Post subject: Re: How to be up to date with Royle's list? Reply with quote

ChPicard wrote:
gsf wrote:
ChPicard wrote:
Hi

Now gsf finds a new 17 given sudoku each hour. It is difficult to be up to date .

How to reach EASILY the new ones?

Is it possible to pick a new # with an address like this :

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

if you put the puzzle number in the grid field it retrieves that puzzle
right now there are 48213 puzzles in the catalog
if your local db only has up to 48210
then you just enter 48211 through 48213 to pick up the 3 new ones


Thanks Glenn

My local database has up to 48158 and after 2 or 3 days late, I must go from 48158 to 48215, no 48216, no 48217, no 48218....

The source is:


<form action="/gordon/sudokuid.php" method="POST"

Enter your details: (optional)<br>
Name:
<input type="text" name="name" size="64" value="Anonymous "
<br>
Email:
<input type="text" name="email" size="64" value="anon@anon.com" <br>

<br>

Enter your puzzle: <br>
<input type="text" name="puzzle" size="81" value="605000000000002708300900000070000000000001050000000061001000300009600000000000200"
<br>
<input type="submit" value="Identify Me!"

</form>



Can we do something with that?

Thanks again

I use this command line to get a puzzle (here 48000) by index
Code:
wget --output-document=- --quiet --post-data=puzzle=48000 http://people.csse.uwa.edu.au/gordon/sudokuid.php

I run on unix/linux but you should be able to get wget(1) for windows
a sed(1) script parses the puzzle grid from the wget output
don't know the windowish alternative for that
Back to top
View user's profile Send private message Visit poster's website
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Thu May 21, 2009 5:54 pm    Post subject: Reply with quote

Repeated appreciation of gsfs efforts !

However, i have investigated the "fixing clues" idea and have made a few conclusions.

The idea that 8 clues [in ML8 format] can reduce dramatically the number of isomorphic completions when 9 clues are added remains valid.

The vast majority of ML8s have an associated 17 puzzle.
Most 17s have 10-20 ML8s , remote 17s have probably more than average.
Most 18s have around 100 ML8s

Concerning making 17/18 puzzles with a fixed ML8:
- It is probably possible to propagate a {-1+1} throughout the 18 space, except it is too large. [~10^8 puzz]
- The opposite occurs with the 17 space because it is too small [~400 puzz] Puzzles all with 8 fixed clues - the 400 additional ways to add 9 clues are widespread.

The finding of new 17s continues with a random method which relies on the many isomorphs of our puzzles keeping the enormous search space connected.

gsf assumming the programming power remains constant the rate of new puzzles per hour is indicative oh how many are left.....
C
Back to top
View user's profile Send private message
gsf

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

Items
PostPosted: Sat May 23, 2009 4:58 am    Post subject: Reply with quote

coloin wrote:

gsf assumming the programming power remains constant the rate of new puzzles per hour is indicative oh how many are left.....

some stats
I have 288 pentium cores in on the search right now
(32 added a few days ago)
the number of new 17s for the first 8 days are:
Code:
  12 2009-05-15
  31 2009-05-16
  19 2009-05-17
  29 2009-05-18
  21 2009-05-19
  13 2009-05-20
  24 2009-05-21
  19 2009-05-22

out of 615926 17s generated
169 were new
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: Sat May 23, 2009 10:49 am    Post subject: Reply with quote

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


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 halted by running HaltQuestFor17.bat

For anyone participating in this quest, who wants to run the quest automatized, ask Jean-Pierre for that 'special' version.

To create the batch files yourself, just open notepad and copy the code for each batch file to it and save it with the according filename in the folder where you keep the files you got from Jean-Pierre. (Or PM me and I will send them to you)

Don't forget to create the subfolders 'Done' and 'Good' and move the GOODCursor files to the 'Good' folder and move all but the last Cursor files to the 'Done' folder. The processed GRIDCursor files can be deleted.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
gsf

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

Items
PostPosted: Sun May 24, 2009 12:52 pm    Post subject: Reply with quote

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?
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)
you've been running this for a week or so, I'm guessing with no hits, how do you know its working?
Back to top
View user's profile Send private message Visit poster's website
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 2 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