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
 
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: 408
:
Location: NJ USA

Items
PostPosted: Tue Aug 25, 2009 2:08 pm    Post subject: Reply with quote

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

right, I should have said puzzles (some empty cells), not grids (81 clues)

since we have enumerated all minlex grids, we can count exactly the number of minlex grids in the gap between any two minlex grids

one of the the problems with minlex puzzles, or puzzle prefixes at gap boundaries,
is that clues added in the gap may change the minlex arrangement of clues in the prefix and possibly place the puzzle in another different gap

I've been enumerating the gaps of size 5 (gaps <= 4 are done)
but its slow going, 1 completes every few hours
Back to top
View user's profile Send private message Visit poster's website
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Thu Aug 27, 2009 5:51 am    Post subject: Reply with quote

Nice work on exploring those gaps - the two normalizations are indeed confusing - and the gaps are not straightforward at all !
: 1. minlexpuzzle
: 2. puzzle from the minlex grid of the puzzle solution

I agree that a puzzle found in the gap between either of these normlizations is probably unlikely to be new.

Changing back to minlexpuzzles,,,,,,,,,

It would be interesting to know just how many possible minlex 17-templates are in the "gap" between two 17-templates from the minlexpuzzles.

These min lex templates....there are 36137 different templates in my collection of Gordon's 48072.

How many possible templates are there with 17 clues ?

81! /[64! x 17!] = 128447994798305325

These will be subject to the 6^8 *2 reductions = 38237309836.9

But many of these will be invalid.
eg
must have at least 1 clue in every double row of 18 clues
must have at least 3 clues in a band of 27 clues ?
must have at least 8 clues in 2 bands [2 x 27 clues]
must have no more than 9 clues in a band
there are also many other patterns which dont have minimal puzzles.

This is based on the fact that there isnt a 17 puzzle with 2 clues in a band. [2,8,9]
There isnt a puzzle with 3 clues in band 1, 4 clues in band 2 and 27 clues in band 3. [3,4,27][to my knowledge]
Code:
+---+---+---+
|...|...|...|
|...|...|..x|
|...|..x|.x.|
+---+---+---+
|...|..x|...|
|.x.|...|..x|
|.x.|...|...|
+---+---+---+
|xxx|xxx|xxx|
|xxx|xxx|xxx|
|xxx|xxx|xxx|
+---+---+---+  ? no puzzle with this 3,4,27 pattern ?


counts of horizontal bands in the 17-puzzles
Code:
3  77
4  12942
5  48971
6  54142
7  25148
8  1212
9  5


There are 17-puzzles with [4,4,9] and probably all of [3,5,9],[3,6,8],[3,7,7] and the more obvious [4,6,7],[4,5,8],[5,6,6],[5,5,7] clue distributions within the respective bands.
Here is a [4,4,9]
Code:
+---+---+---+
|...|...|...|
|...|...|..1|
|..2|..3|.4.|
+---+---+---+
|...|..5|...|
|.1.|...|..6|
|.7.|...|...|
+---+---+---+
|..8|.1.|...|
|..9|.6.|52.|
|.5.|.7.|.3.|
+---+---+---+   

A valid template has to have at least [3,5,5] [13] or [4,4,4] [12] clues, if there is 3 or 4 clues in the initial band .

This has to be demonstrable in the columns as well of course.

This may not be of use - perhaps there are many templates with 12+ clues which satisfy these rules - although with a stroke of elegance we have "proved" that n[min] is at least 12 clues.

Out of interest.........how difficult would it be to test a template ?

Although I do appreciate that the majority of templates have only one puzzle.

Perhaps try these numbered puzzles selected from the catalogue to see how feasible it is !

Code:

#   26098   #   ................12..3..4.........5.......63.417...........8.......17..2.3.4.2....
#   26201   #   ................12..3..4.........5.......63.417...........8.......17..9.8.4.9....
#   40277   #   ................12..3..4.........5.......63.417...........7.......28..5.2.4.1....
#   40278   #   ................12..3..4.........5.......63.417...........7.......82..5.2.4.1....

#   24890   #   ................12..3..4........15...26......78...........7.9....4...3..5..82....
#   24891   #   ................12..3..4........15...26......78...........8.9....4...3..5..72....
#   24892   #   ................12..3..4........15...26......78...........7.3....4...9..5..82....
#   24893   #   ................12..3..4........15...26......78...........8.3....4...9..5..72....
#   38878   #   ................12..3..4........15...26......78...........7.9....9...3..5..82....
#   38879   #   ................12..3..4........15...26......78...........7.9....9...4..5..82....
#   38880   #   ................12..3..4........15...26......78...........8.9....9...3..5..72....
#   38881   #   ................12..3..4........15...26......78...........8.9....9...4..5..72....

#   26316   #   ................12..3..4..5.....63...7....4..52...........1.......72......8...63.
#   26317   #   ................12..3..4..5.....67...6....8..29...........9.......21......7...63.
#   26321   #   ................12..3..4..5.....36...7....8..52...........1.......27......9...38.
#   26322   #   ................12..3..4..5.....36...4....7..28...........8.......12......9...37.
#   35752   #   ................12..3..4..5.....64...7....8..29...........9.......21......6...37.
#   35767   #   ................12..3..4..5.....36...7....8..52...........1.......72......8...46.
#   37552   #   ................12..3..4..5.....36...4....7..28...........8.......21......5...97.

#   16886   #   ........1.....2..3..4.5..........46..7.......31...8......46.9.....7.....23.......
#   46832   #   ........1.....2..3..4.5..........46..1.......73...8......64.8.....9.....32.......
#   46837   #   ........1.....2..3..4.5..........46..3.......71...8......64.8.....9.....32.......


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
Page 4 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