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

coloin · Posted: Sat May 16, 2009 11:19 am Post subject:

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.

strmckr · Posted: Sat May 16, 2009 9:46 pm Post subject:

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?

coloin · Posted: Sat May 16, 2009 11:06 pm Post subject:

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

strmckr · Posted: Sun May 17, 2009 12:14 am Post subject:

coloin · Posted: Sun May 17, 2009 1:07 am Post subject:

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.

coloin · Posted: Mon May 18, 2009 8:20 am Post subject:

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

ChPicard

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

gsf

ChPicard

gsf

coloin · Posted: Thu May 21, 2009 5:54 pm Post subject:

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

gsf · Posted: Sat May 23, 2009 4:58 am Post subject:

Lunatic · Posted: Sat May 23, 2009 10:49 am Post subject:

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

gsf · Posted: Sun May 24, 2009 12:52 pm Post subject: