|
| View previous topic :: View next topic |
| Author |
Message |
| Lunatic
 | | Joined: 11 Mar 2007 | | Posts: 166 | | : | | Location: Ghent - Belgium |
Items |
|
 Posted: Wed Apr 09, 2008 11:03 pm Post subject: |
 |
|
| I wrote: |
...isn't it so that if one ore more 16 given sudokus exists, then each of those 16 celled patterns will have a unique cover in only 1 of those 5.472.730.538 essentially different solved sudoku grids ?
So the first cell will subdivide those level 0 set of 5.472.730.538 in maximum 9 level 1 subsets
The second cell will subdivide each level 1 subset again in maximum 9 level 2 subsets
For each next cell each subset can be divided again until, hopefully, a level 16 subset has only 1 member, A (or THE) 16 GIVEN SUDOKU !!!  |
I've done a test with 4x4 grid sudokus
There are 288 solved grids, after reducing them by relabelling, rotating, permutating, there are only 6 essentially different solved sudoku grids. According to my above thoughts, one could easely isolate a level 2 subset with only 1 member, BUT... that doesn't led to a unique solution. Conclusion: I was wrong  Back to the drawing board.... (Do I need all 6.670.903.752.021.072.936.960 solutions ?  )
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~ |
|
| Back to top |
|
 |
| coloin
| | Joined: 05 May 2005 | | Posts: 97 | | : | |
Items |
|
| Posted: Wed Apr 09, 2008 11:24 pm Post subject: |
|
|
The 16 clues would have to define a solution / solve from 6^10^21 grids - not 5*10^9.
One clue does tend to reduce the number of grid solutions by a factor of 9.
9^16 is way below our requirements, but we know 17 clues will suffice.
Although I do believe every essentially different grid has these "equivalent" clues in somewhere | Code: | +---+---+---+
|1..|...|...|
|...|2..|...|
|...|...|3..|
+---+---+---+
|.4.|...|...|
|...|.5.|...|
|...|...|.6.|
+---+---+---+
|..7|...|...|
|...|..8|...|
|...|...|..9|
+---+---+---+
|
[not proven]
If it fits your theory - do recheck your figures, there are only 2 essentially different 2x2x4 grids.
Im impressed though !
C |
|
| Back to top |
|
|
| Adak
| | Joined: 27 Feb 2008 | | Posts: 87 | | : | |
Items |
|
| Posted: Wed Apr 09, 2008 11:29 pm Post subject: |
|
|
| gsf wrote: | what coloin is hinting at is symmetries of solution and puzzle grids
the symmetries that can be used to determine equivalence
if you don't take symmetries into account you will be doing 10^21 / 10^9 = 10^12 times too much work
that is not something you want to discover 1 year down the road
"its is proven" is a subtle hint to research the player's and programmer's forums
a proposal of this scale deserves some research
you might also help your cause by dropping the superfluous comments and sticking to details
like maybe some numbers that show you can finish the search in your lifetime |
Of course, I'm reading what I can. The coding goes on, however. Subtle hints are hard to separate from subtle sarcasm, in a text message.
Although the generator is getting smarter, I doubt it will ever search through the least possible number of grids.
I don't have the data yet for any projections on the search time needed. It's being programmed on my laptop (old P3 cpu), but will be run on the C2D's, which can fly.
@coloin:
You may see a strong link between the search for 16'ers, and Harvard's two 39 puzzles, but this search isn't being done that way. The 16 given grids will be treated as distinct.
This is the most focused way I know of to do a search. I don't see the advantage of trying to search through one search space, by focusing our efforts on different search spaces. If others do, then that may be a great way for them to work. I wouldn't choose that way. |
|
| Back to top |
|
|
| coloin
| | Joined: 05 May 2005 | | Posts: 97 | | : | |
Items |
|
| Posted: Wed Apr 09, 2008 11:46 pm Post subject: |
|
|
I think the hints that I give are such that when you work out things for yourself you get some satisfaction yourself. Apologies if they are too subtle.
The reduction by 10^12 should make you sleep easier !
However if you are still aiming to generate all ways of inserting 16 clues you have to admit to me that all the 16 combinations from Havards puzzles are going to be in your test run.
I just mentioned it as I thought eliminating 2x37 billion of your combinations was worthy of at least a thank-you !
How you code it and tabulate it I have no idea !
C |
|
| Back to top |
|
|
| JPF
| | Joined: 05 Dec 2005 | | Posts: 29 | | : | | Location: Paris |
Items |
|
| Posted: Thu Apr 10, 2008 12:09 am Post subject: |
|
|
| coloin wrote: | Although I do believe every essentially different grid has these "equivalent" clues in somewhere | Code: | +---+---+---+
|1..|...|...|
|...|2..|...|
|...|...|3..|
+---+---+---+
|.4.|...|...|
|...|.5.|...|
|...|...|.6.|
+---+---+---+
|..7|...|...|
|...|..8|...|
|...|...|..9|
+---+---+---+
|
[not proven] |
Could you elaborate please ?
| coloin wrote: | | there are only 2 essentially different 2x2x4 grids. |
Yes, see here.
JPF |
|
| Back to top |
|
|
| coloin
| | Joined: 05 May 2005 | | Posts: 97 | | : | |
Items |
|
| Posted: Thu Apr 10, 2008 1:14 am Post subject: |
|
|
Well, with row/colum/ band swapping and relabelling I think every grid has several of these "non attacking rook" patterns.
Lunatic I think was filtering reductions with one clue - above.
Each of these disjoint clues reduces the options by 9 [I think]
This must mean there are 6*10^21 / 9^9 grid solutions with this pattern.
More than one per essentially different grid then ?
The relevance........well there are only two 17-puzzles with this pattern. So not good clues .
| Code: | 1....6......2.7...9.....3...4..9....3...5...........6...7...2....6..8.........1.9
1...7.......2......8....3...4...3.....9.5...7.......6...7...........84..5.....8.9
1...........2...........3...4...........5...........6...7...........8...........9 |
Actually the reason they are not good clues is that all the possible ways to add 8 more clues to make a 17 puzzle are isomorphs of the two 17-puzzles. And there will be 6^8 *2 of these per puzzle.
EDIT
There might not be 6^8*2 per puzzle, but there will be many. [?9!]
Maybe the 9 clues arent so "bad" / inefficient after all.
C
Last edited by coloin on Thu Apr 10, 2008 5:55 pm; edited 1 time in total |
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Thu Apr 10, 2008 1:49 am Post subject: |
|
|
| coloin wrote: |
Every time gsf finds a new one he has probably had to reproduce ? 1000 antiques maybe more 
|
that's about right
| Quote: |
The complete collection of minlex grids can be compressed into 5.34 GiBytes - probably a program can generate them relativly easily. See Canonical Form
|
my solver for one
the grids are labeled by minlex bands (the first 3 rows) -- there are 416 of them, 001-416
the earlier bands typically contain more grids
bands 001-100 each take about 1-2 hrs to generate
the time drops for the higher bands
some bands in the 300s and 400s have no grids
here are the minlex grid counts by band
| Code: |
_______________________________________________________________________________
001:1007170 068:47978806 135:15272476 202:3064062 269:424148 336:18996
002:25502082 069:47059527 136:14918036 203:2966309 270:378441 337:17212
003:16538087 070:46231581 137:7254450 204:2932890 271:361885 338:14780
004:8417906 071:22715795 138:14383075 205:2841380 272:360821 339:13660
005:48737791 072:44778204 139:7011714 206:2701985 273:176161 340:12324
006:96229042 073:44053469 140:13738161 207:2628788 274:172023 341:10597
007:15765443 074:43401907 141:13445152 208:2532198 275:165927 342:9562
008:5306280 075:21398806 142:6593805 209:2443960 276:154694 343:9012
009:8136013 076:42061440 143:12918117 210:1243959 277:150664 344:8215
010:47174193 077:41316125 144:6403269 211:2317171 278:309399 345:7261
011:46788396 078:40571245 145:12568136 212:2357854 279:144927 346:3569
012:46177270 079:40282447 146:12354720 213:1137589 280:141820 347:7136
013:15340394 080:39233218 147:12036469 214:1083228 281:137601 348:455
014:45397270 081:38522319 148:5931073 215:2183311 282:287667 349:2935
015:45600758 082:37881913 149:5949060 216:2244753 283:246093 350:2990
016:1631576 083:37460193 150:11577852 217:2143677 284:123480 351:4836
017:15093541 084:18460204 151:11435633 218:2100798 285:124070 352:2156
018:45101600 085:36127803 152:11155974 219:1007465 286:116970 353:2141
019:44832423 086:35584769 153:10671486 220:1970315 287:117351 354:1959
020:88782526 087:34821531 154:10525735 221:1841722 288:110418 355:4171
021:44036568 088:34334716 155:10188634 222:1873099 289:37988 356:3376
022:85627559 089:33769162 156:10059617 223:1772301 290:109351 357:3171
023:42711122 090:33174401 157:9805813 224:347777 291:211267 358:3150
024:85102373 091:32520037 158:9629320 225:1968442 292:209636 359:647
025:41847039 092:31945541 159:9490222 226:1677704 293:189161 360:1528
026:41335391 093:31221072 160:9280124 227:1521001 294:188766 361:2484
027:4455504 094:30579410 161:8844112 228:1498734 295:171584 362:2233
028:41102914 095:29977732 162:8628099 229:1515366 296:152633 363:1930
029:4591391 096:29390061 163:8429593 230:1457098 297:147806 364:1353
030:4664261 097:14518368 164:8227144 231:1331185 298:70955 365:1368
031:13606209 098:14372444 165:7998287 232:1279569 299:133302 366:1232
032:40697707 099:28268021 166:7813413 233:1262013 300:139754 367:1667
033:80468663 100:27849953 167:3839149 234:1218744 301:119226 368:925
034:79175610 101:13768854 168:7548052 235:386642 302:20203 369:872
035:77979783 102:26929453 169:7349287 236:1182963 303:62246 370:928
036:38536298 103:26382806 170:7146807 237:570172 304:63613 371:808
037:76146967 104:4359314 171:6993422 238:1111083 305:69669 372:560
038:74505665 105:25997296 172:6828801 239:1076551 306:58811 373:757
039:74154564 106:25467197 173:6674911 240:167032 307:21225 374:451
040:72171447 107:24888528 174:6476248 241:533940 308:56942 375:245
041:36053455 108:24423300 175:3166465 242:1048083 309:55120 376:333
042:70552290 109:23988326 176:6205963 243:974591 310:49427 377:156
043:69437575 110:23541927 177:6040631 244:967788 311:91869 378:193
044:67978951 111:23070530 178:5882934 245:455310 312:89983 379:161
045:33904021 112:22609142 179:5812748 246:915249 313:80765 380:23
046:66337407 113:22100458 180:5615082 247:500537 314:43270 381:163
047:65880161 114:10879514 181:5461387 248:783336 315:74594 382:154
048:64996381 115:21378062 182:5367414 249:822496 316:69012 383:111
049:63898062 116:20985174 183:5222068 250:377256 317:73627 384:124
050:62192220 117:20674972 184:5072949 251:408556 318:62449 385:87
051:61691475 118:20107116 185:4918277 252:437792 319:59123 386:49
052:60192385 119:19854606 186:4778878 253:387029 320:57580 387:66
053:29966384 120:9732970 187:4641003 254:140436 321:47910 388:125
054:29734495 121:19084488 188:4539624 255:361962 322:44876 389:27
055:58731513 122:9491325 189:4407284 256:354702 323:46852 390:59
056:57263818 123:18532281 190:2186822 257:675674 324:46002 391:19
057:57033275 124:9142485 191:4220821 258:661737 325:40108 392:41
058:55394556 125:18075269 192:4158097 259:313209 326:37300 393:2
059:55022930 126:17675306 193:4070158 260:623191 327:36969 394:16
060:54018514 127:17545752 194:3857103 261:546083 328:31504 396:11
061:52964870 128:16990098 195:3785628 262:524804 329:28919 399:10
062:52242492 129:8369473 196:3693474 263:534167 330:27982 401:1
063:51245000 130:16406705 197:3555681 264:503384 331:29202 405:4
064:50540742 131:16189996 198:3453089 265:464985 332:25098 407:19
065:49644127 132:15791769 199:3345667 266:461786 333:20652 411:3
066:49190978 133:2613345 200:3252227 267:441645 334:10105 416:1
067:24077300 134:15362664 201:3165254 268:418773 335:19471
|
to list the grids in band 300
to list the first and last grid in band 200
to list all of them (~2 weeks, and disk space if you want to save them)
although slow, generation is currently much more feasible than downloading
|
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Thu Apr 10, 2008 4:19 am Post subject: |
|
|
| Adak wrote: |
Of course, I'm reading what I can. The coding goes on, however. Subtle hints are hard to separate from subtle sarcasm, in a text message.
|
if you took any part of my posts as sarcastic, that was not the intention, and I apologize
can you at least make a guess as to how long it will take you to search one solution grid? |
|
| Back to top |
|
|
| Adak
| | Joined: 27 Feb 2008 | | Posts: 87 | | : | |
Items |
|
| Posted: Thu Apr 10, 2008 9:15 am Post subject: |
|
|
| gsf wrote: | | Adak wrote: |
Of course, I'm reading what I can. The coding goes on, however. Subtle hints are hard to separate from subtle sarcasm, in a text message.
|
if you took any part of my posts as sarcastic, that was not the intention, and I apologize
can you at least make a guess as to how long it will take you to search one solution grid? |
No problem, gsf. It wasn't your post that I took as sarcasm.
Unfortunately, I can't say anything about a time to search one solution. My focus has been on generating the grids. If we can't get a good generator plan working, then the solution work on the grids, is irrelevant.
My idea was to to test each grid for uniqueness, period. Hopefully with a faster program than I could write.
And that brings us to the real problem. Quest 16 needs to be nothing less than a BOINC DC project, with talented input from several programmers, and lots of enthusiastic (maybe competitive) "crunchers", donating computer time, as well as a web and server guy to keep things rolling along on that end of things, on a part time basis.
After working with volunteer projects for many years, both in R/L and on the net, I know the *one* thing a project needs is enthusiastic participation; that willingness to work on it. There's a big difference between an interested poster/person on the subject, and an enthusiastic participant in a project.
I'm going to keep wrestling with the problem because I find it interesting, but Quest 16 is closed. |
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Thu Apr 10, 2008 10:16 am Post subject: |
|
|
| Adak wrote: |
And that brings us to the real problem. Quest 16 needs to be nothing less than a BOINC DC project, with talented input from several programmers, and lots of enthusiastic (maybe competitive) "crunchers", donating computer time, as well as a web and server guy to keep things rolling along on that end of things, on a part time basis.
|
[ edit I composed most of the respose before noticing quest16 is closed
I'll still post, mainly because I think the lack of enthusiasm you sense is because
you haven't made your case w.r.t. how much time you think it will take ]
you won't get many participants until you provide estimates on how long you expect the entire search to take
and after those estimates withstand some peer review
I think that's why the current sudoku BOINC project has such paltry participation (just a handful, right?)
no one thinks they will get to the last phase
right now you are concerned with a fast solver
but it may not be the hotspot in all of the required computations
these are the approximate numbers your algorithm(s) are facing:
total number of solution grids up to isomorphism: 10^9
check a grid for 16s: checker estimates: 10^3 .. 10^5 Ghz-sec
suppose on average checker requires 10^4 Ghz-sec
checking all grids requires 10^9 * 10^4 Ghz-sec = ~10^13 Ghz-sec
lets call it 10^14 Ghz-sec to be safe
suppose the average BOINC participant can provide a continuous 1 Ghz-sec
with checker it would take 1 participant ~ 10^6 years to search all solution grids for 16s
1 million participants 1 year
100K participants 10 years
10K participants -- too long
SETI has ~10^6 participants -- is there any other project on that scale?
you might be able to get 100 participants from the sudoku forums
you need to make similar arguments before people will jump onboard |
|
| Back to top |
|
|
| coloin
| | Joined: 05 May 2005 | | Posts: 97 | | : | |
Items |
|
| Posted: Thu Apr 10, 2008 6:43 pm Post subject: |
|
|
gsf - spectatular feat to make the grids so available !
| Adak wrote: | | Quest 16 is closed |
What does this mean ? I didnt think we had started yet ?
I hope none of my comments were interpreted as sarcastic either, maybe when you have wrestled more with the problem you will appreciate that they were genuine attempts to forward your proposal.
However impossibly large the project was, the theoretical "reductions" that we have touched upon are interesting to think about.
I was particularly impressed in the reductions by JPF which devided the number of iterations for 16 clues [3*10^16] by the [6^8*2] number ~ 10^9 = number of essentially different 16 clue templates.
C |
|
| Back to top |
|
|
| Lunatic
| | Joined: 11 Mar 2007 | | Posts: 166 | | : | | Location: Ghent - Belgium |
Items |
|
| Posted: Thu Apr 10, 2008 8:05 pm Post subject: |
|
|
| coloin wrote: |
| Adak wrote: | | Quest 16 is closed |
What does this mean ? I didnt think we had started yet ?
|
I share that thought. I thought the purpose of this thread was more and more heading towards collecting ideas on how to reduce the brute force Quest 16.
I have to admit that there are a lot of things i don't understand, because:
- i'm not a math-magician
- some used terms are dark to me, to technical for me normally speaking dutch.
So, i was wondering if there is some sort of formula to determine the minimum number of clue cells that are needed to make a valid 9x9 sudoku. With numbers like 6*10^21 / 9^9 or 5.472.730.538 or 6.670.903.752.021.072.936.960 it is difficult to have an overview, so i took a step down to 4x4 sudokus...
With only 288 different solved grids, it's more easy to get an overview. It seems that the minimum needed clue cells to have a valid 4x4 sudoku is 4 (still have to check for myself, on paper, by hand). But what is the relation between the size of the grid and the minimum needed clue cells ? If we could find it for 4x4 sudokus and use that same formula for 9x9 sudokus, whe could know if it is possible to have a valid 16 clue sudoku.
Unfortunatly, taking the grid a further step down to have another reference on how to explore the relation between the grid and the minimum needed clue cells is of no use, we end up with a single cell (1x1 sudoku) where the minimum needed clue cells is 0. Don't think that is very useful.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~ |
|
| Back to top |
|
|
| coloin
| | Joined: 05 May 2005 | | Posts: 97 | | : | |
Items |
|
| Posted: Thu Apr 10, 2008 8:17 pm Post subject: |
|
|
| Lunatic wrote: | So, i was wondering if there is some sort of formula to determine the minimum number of clue cells that are needed to make a valid 9x9 sudoku.......
It seems that the minimum needed clue cells to have a valid 4x4 sudoku is 4 |
4 is correct
I think your initial comment was also true.
Whilst we are thinking , for amusement a certain DrZ posted his solution !!
Enjoy
C |
|
| Back to top |
|
|
| JPF
| | Joined: 05 Dec 2005 | | Posts: 29 | | : | | Location: Paris |
Items |
|
| Posted: Thu Apr 10, 2008 10:19 pm Post subject: |
|
|
| coloin wrote: | Although I do believe every essentially different grid has these "equivalent" clues in somewhere | Code: | +---+---+---+
|1..|...|...|
|...|2..|...|
|...|...|3..|
+---+---+---+
|.4.|...|...|
|...|.5.|...|
|...|...|.6.|
+---+---+---+
|..7|...|...|
|...|..8|...|
|...|...|..9|
+---+---+---+
|
[not proven] |
It's not true for all the 288 (4 x 4) grids.
True for : | Code: | 1 2 | 3 4
3 4 | 1 2
----+----
2 1 | 4 3
4 3 | 2 1
|
96 grids
not true for : | Code: | 1 2 | 3 4
3 4 | 1 2
----+----
2 3 | 4 1
4 1 | 2 3
|
192 grids
JPF |
|
| Back to top |
|
|
| Lunatic
| | Joined: 11 Mar 2007 | | Posts: 166 | | : | | Location: Ghent - Belgium |
Items |
|
| Posted: Thu Apr 10, 2008 11:06 pm Post subject: |
|
|
| coloin wrote: | | Whilst we are thinking , for amusement a certain DrZ posted his solution !! |
Odd, with the 1x1 grid in mind not needing any clue to solve (obvious), i was thinking that if there was a formula then there could be a substraction of 1 involved. Something like this:
Minimum clues = {formula} - 1
So, DrZ's formula is correct for both 4x4 and 1x1 grids ? At least these are easy to check.
I wonder if the formula still stands for grids with non-square boxes (boxsize 2x3 for example).
| Code: |
12 34 56
34 56 12
56 12 34
21 43 65
43 65 21
65 21 43
|
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~ |
|
| Back to top |
|
|
|
|
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
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
