17-clue and 18-clue Sudoku update

Everything about Sudoku that doesn't fit in one of the other sections

Postby gsf » Thu Aug 23, 2007 2:18 pm

gfroyle wrote:Nice picture... but not quite the clear power-law decline that we might have hoped for...

One thing though - you say that the left-hand point is (1,177) but there is clear red line going well above 200 at x=1 or x=0; is this an artifact of your plotting program or is there some mistake...

or behind curtain #3: the left point does not have the max y value
here are the 671 x y data points scrunched to odd even pairs for posting

1 177 2 226 3 195 4 223 5 201 6 198 7 183 8 168 9 165 10 156 11 149 12 162 13 149 14 166 15 139 16 142 17 159 18 147 19 142 20 146 21 147 22 159 23 138 24 163 25 164 26 140 27 146 28 136 29 135 30
156 31 150 32 162 33 169 34 160 35 180 36 169 37 146 38 156 39 156 40 148 41 147 42 146 43 148 44 162 45 159 46 169 47 180 48 163 49 149 50 170 51 177 52 152 53 152 54 166 55 157 56 166 57 171 58 178
59 178 60 160 61 155 62 159 63 136 64 153 65 167 66 159 67 183 68 151 69 154 70 166 71 136 72 166 73 141 74 155 75 159 76 166 77 161 78 171 79 145 80 158 81 154 82 163 83 157 84 180 85 170 86 153 87
141 88 175 89 160 90 167 91 167 92 163 93 151 94 160 95 180 96 141 97 166 98 154 99 147 100 184 101 166 102 152 103 141 104 150 105 143 106 159 107 136 108 144 109 164 110 154 111 151 112 141 113 119
114 144 115 128 116 117 117 162 118 158 119 160 120 145 121 149 122 155 123 154 124 132 125 135 126 151 127 144 128 136 129 148 130 135 131 142 132 150 133 135 134 132 135 142 136 141 137 148 138 122
139 132 140 152 141 130 142 159 143 149 144 150 145 124 146 127 147 111 148 128 149 122 150 129 151 150 152 115 153 137 154 110 155 125 156 140 157 125 158 119 159 127 160 126 161 134 162 121 163 128
164 112 165 111 166 102 167 126 168 139 169 108 170 110 171 123 172 127 173 134 174 152 175 144 176 126 177 121 178 119 179 123 180 119 181 123 182 91 183 113 184 103 185 118 186 101 187 119 188 114
189 114 190 110 191 113 192 107 193 126 194 106 195 96 196 117 197 105 198 112 199 99 200 108 201 88 202 94 203 102 204 97 205 87 206 109 207 90 208 99 209 104 210 105 211 89 212 105 213 93 214 93
215 103 216 97 217 96 218 85 219 78 220 80 221 96 222 103 223 100 224 79 225 90 226 84 227 95 228 89 229 74 230 92 231 82 232 67 233 73 234 91 235 73 236 74 237 81 238 71 239 75 240 82 241 75 242 76
243 91 244 70 245 92 246 71 247 84 248 66 249 69 250 75 251 69 252 72 253 70 254 71 255 74 256 70 257 74 258 69 259 74 260 56 261 75 262 77 263 63 264 59 265 66 266 69 267 61 268 62 269 75 270 61 271
71 272 68 273 59 274 60 275 63 276 65 277 59 278 57 279 51 280 61 281 70 282 63 283 57 284 62 285 54 286 64 287 49 288 48 289 57 290 61 291 53 292 63 293 53 294 49 295 60 296 43 297 55 298 54 299 51
300 55 301 55 302 45 303 40 304 41 305 59 306 44 307 48 308 60 309 48 310 46 311 51 312 52 313 45 314 41 315 60 316 46 317 43 318 48 319 50 320 34 321 32 322 57 323 45 324 31 325 40 326 43 327 47 328
36 329 32 330 40 331 50 332 37 333 46 334 36 335 42 336 57 337 31 338 34 339 38 340 34 341 41 342 27 343 36 344 34 345 37 346 40 347 33 348 28 349 33 350 28 351 28 352 37 353 42 354 25 355 23 356 20
357 30 358 32 359 29 360 29 361 24 362 35 363 22 364 27 365 19 366 31 367 23 368 26 369 28 370 29 371 25 372 35 373 19 374 19 375 25 376 12 377 21 378 20 379 26 380 18 381 26 382 28 383 18 384 19 385
22 386 17 387 25 388 29 389 23 390 21 391 9 392 21 393 19 394 23 395 25 396 16 397 21 398 14 399 30 400 20 401 16 402 12 403 23 404 12 405 28 406 22 407 16 408 19 409 13 410 22 411 19 412 16 413 18
414 15 415 17 416 13 417 17 418 15 419 16 420 16 421 18 422 12 423 16 424 7 425 12 426 11 427 14 428 14 429 19 430 22 431 14 432 9 433 15 434 9 435 10 436 18 437 18 438 11 439 9 440 12 441 8 442 11
443 14 444 11 445 16 446 19 447 13 448 10 449 9 450 10 451 10 452 11 453 8 454 7 455 10 456 7 457 11 458 11 459 14 460 6 461 8 462 6 463 9 464 16 465 7 466 6 467 13 468 10 469 8 470 9 471 10 472 8
473 9 474 10 475 7 476 7 477 9 478 8 479 8 480 5 481 8 482 17 483 6 484 11 485 10 486 7 487 2 488 10 489 5 490 5 491 5 492 4 493 8 494 7 495 12 496 8 497 3 498 7 499 4 500 7 501 7 502 5 503 7 504 6
505 6 506 7 507 4 508 1 509 6 510 6 511 2 512 7 513 8 514 7 515 7 516 10 517 6 518 7 519 2 520 7 521 6 522 4 523 2 524 6 525 8 526 1 527 1 528 3 529 4 530 3 531 5 532 2 533 6 534 4 535 7 536 7 537 2
538 3 539 4 540 3 541 8 542 5 543 3 544 1 545 3 546 2 547 6 548 4 549 2 550 3 551 4 552 1 553 4 555 2 556 6 557 4 558 2 559 1 560 2 561 3 562 1 563 3 564 3 565 2 566 2 567 2 568 1 569 1 570 2 571 3
572 1 573 2 574 2 575 2 576 2 577 3 578 3 579 3 580 2 581 4 582 1 583 1 584 1 585 2 586 1 587 1 589 2 590 1 591 2 592 3 593 1 594 2 595 2 596 1 598 1 599 1 600 3 601 3 602 1 603 1 604 3 605 2 607 1
608 3 609 2 611 1 613 1 614 2 615 4 616 3 617 1 618 2 619 1 620 1 625 1 626 1 627 1 628 2 629 2 631 1 632 1 633 1 634 3 635 1 639 1 640 2 641 1 645 5 648 2 650 2 651 1 652 2 657 1 658 1 659 2 660 1
665 1 666 1 667 2 669 1 670 1 672 3 674 2 676 1 682 1 684 1 693 1 694 1 695 1 700 1 708 2 710 1 714 1 716 1 723 1 724 1 731 1 732 1 734 2 750 1 758 1 764 1 773 1 774 1 786 1 788 1 792 1 796 1 818 1
876 1 923 1
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Thu Aug 23, 2007 9:05 pm

gsf wrote:which means that all of the known 17s are in the {-5+5} closure

From your data this would mean all puzzles in your analysis are accounted for
Code: Select all
177 puzzles which have  1 other puzzle. within 5*
226 puzzles which have  2 other puzzles within 5*
........
........
1 puzzle which has 876 other puzzles within 5*
1 puzzle which has 923 other puzzles within 5*
---------
41596 puzzles = G

Maybe a good way to make 18 puzzles for searching purposes would be to start from the 177 most remote 17-puzzles.

Expand with {-1+2}x1{-1+1}x1 and then at least {-1+1}x6...........

Given that any 18puzzle made from subjecting a 17puzzle to{-1+2}x1{-1+1}x1 cant provide us with a "new" puzzle, it is now perhaps feasable to remove these puzzles from a .dat file.
coloin wrote:Any idea how we can avoid making these ?

Initially i thought we would have to generate the 10-20 million "useless" 18s formed from {-1+2}x1{-1+1}x1 of G.

But it may be achieved more simply by excluding any 18s which have 16 clue subpuzzles in common with the 16 clue subpuzzles in G.

C
coloin
 
Posts: 1632
Joined: 05 May 2005

Postby coloin » Sat Aug 25, 2007 4:00 pm

JPF wrote:and the number N of non isomorphic grids with n non isomorphic 17s :

Code: Select all
 n      N     n x N                                                             
                                                                               
29      1        29   *                                                           
20      1        20   *                                                         
14      1        14                                                             
12      1        12   *                                                         
11      1        11   *                                                         
 9      1         9   *                                                         
 8      3        24                                                             
 7      7        49                                                             
 6     20       120                                                             
 5     18        90                                                             
 4     81       324                                                             
 3    236       708                                                             
 2   1599      3198                                                             
 1  35487     35487
              ------                                                             
              40095


Here is an interesting and strangley familiar discovery !!!!!

The SF grid has 29 different 17 puzzles....18 of which result from this 16 clue pseudopuzzle with 2 solutions
Code: Select all
+---+---+---+
|...|.4.|7..|
|.8.|...|...|
|.1.|...|.2.|
+---+---+---+
|...|8..|..6|
|7..|...|...|
|4..|...|2..|
+---+---+---+
|3.2|.7.|...|
|...|...|...|
|...|..6|.18|
+---+---+---+ 2 solutions - 18 different puzzles



Starting from the SF grid I made many 18s and did a reductive scan to make possibly new 17s.
I was surprised to find at least a dozen with this pattern of 16 clues
Code: Select all
+---+---+---+
|...|.4.|7..|
|.8.|2..|...|
|.1.|...|...|
+---+---+---+
|...|8..|..5|
|7..|...|...|
|4..|...|2..|
+---+---+---+
|3..|.7.|...|
|...|...|..2|
|...|..6|.18|
+---+---+---+ 4 solutions - 19 different puzzles


It even looked strangely familiar........and it had quite a few puzzles......except it had 4 solutions and 19 puzzles

Of course these weren't new puzzles they were the grids which we have long known to have 29 and 20 puzzles each [see JPFs chart at top]. The "second best" grid just never has been scrambled this way.......

So I did a {4-on} on the 13 common clues
Code: Select all
....4.7...8........1.....2....8....67........4.....2..3.2.7..................6.18    2 grid sol.
....4.7...8.2......1..........8....97........4.....2..3...7............2.....6.18    4 grid sol.

....4.7...8........1..........8.....7........4.....2..3...7..................6.18    9766550 grid sol.


With a 4-on search [actually 58 times 3-ons] in two hours I had 132 different puzzles [none new]
Code: Select all
29 puzzles in SF grid
639241785284765193517983624123857946796432851458619237342178569861594372975326418
....4.7...8........1.....2....8....67........4.....2..3.2.7...............5..6.18
....4.7...8........1.....2....8....67........4.....2..3.2.7.............9....6.18
....4.7...8........1.....2....8....67........4.....2..3.2.7........9.........6.18
....4.7...8........1.....2....8....67........4.....2..3.2.7.......5..........6.18
....4.7...8........1.....2....8....67........4.....2..3.2.7...9..............6.18
....4.7...8........1.....2....8....67........4.....2..3.2.7.5................6.18
....4.7...8........1.....2....8....67........4....92..3.2.7..................6.18
....4.7...8........1.....2....8....67........45....2..3.2.7..................6.18
....4.7...8........1.....2....8....67......5.4.....2..3.2.7..................6.18
....4.7...8........1.....2....8....679.......4.....2..3.2.7..................6.18
....4.7...8........1.....2....8..9.67........4.....2..3.2.7..................6.18
....4.7...8........1.....2....85...67........4.....2..3.2.7..................6.18
....4.7...8........1.9...2....8....67........4.....2..3.2.7..................6.18
....4.7...8.......51..........8....67........4.....2..3.2.7............2.....6.18
....4.7...8.......51..........8....67........4.....2..3.2.7...........7......6.18
....4.7...8.......51..........8....67........4.....2.73.2.7..................6.18
....4.7...8.......51.....2....8....67........4.....2..3.2.7..................6.18
....4.7...8.....9..1..........8....67........4.....2..3...7......1.....2.....6.18
....4.7...8.....9..1..........8....67........4.....2..3..17............2.....6.18
....4.7...8.....9..1..........8....67........4.....2..3.2.7............2.....6.18
....4.7...8.....9..1..........8....67........4.....2..3.2.7...........7......6.18
....4.7...8.....9..1..........8....67........4.....2.73.2.7..................6.18
....4.7...8.....9..1.....2....8....67........4.....2..3.2.7..................6.18
....4.7...8...5....1.....2....8....67........4.....2..3.2.7..................6.18
....4.7.5.8........1.....2....8....67........4.....2..3.2.7..................6.18
...24.7...8........1.....2....8....67........4.....2..3...7...5..............6.18
...24.7...8.......51..........8....67........4.....2..3...7............2.....6.18
...24.7...8.....9..1..........8....67........4.....2..3...7............2.....6.18
..9.4.7...8........1.....2....8....67........4.....2..3.2.7..................6.18

20 puzzles in grid
239541786587263194614789523126837945753492861498615237342178659861954372975326418
....4.7...8.2......1..........8....57........4.....2..3...7............2..5..6.18
....4.7...8.2......1..........8....57........4.....2..3...7............29....6.18
....4.7...8.2......1..........8....57........4.....2..3...7...9........2.....6.18
....4.7...8.2......1..........8....57........4.....2..3...7..5.........2.....6.18
....4.7...8.2......1..........8....57........4.....2..3...7.6..........2.....6.18
....4.7...8.2......1..........8....57........4.....23.3...7............2.....6.18
....4.7...8.2......1..........8....57........4....52..3...7............2.....6.18
....4.7...8.2......1..........8....57........4..6..2..3...7............2.....6.18
....4.7...8.2......1..........8....57......6.4.....2..3...7............2.....6.18
....4.7...8.2......1..........8....57.3......4.....2..3...7............2.....6.18
....4.7...8.2......1.....2....8....57........4.....2..3...7...9..............6.18
....4.7...8.2......1....5.....8....57........4.....2..3...7............2.....6.18
....4.7...8.2......1...9......8....57........4.....2..3...7............2.....6.18
....4.7...8.2.....61..........8....57........4.....2..3...7............2.....6.18
....4.7...8.2...9..1..........8....57........4.....2..3...7............2.....6.18
....4.7...8.26.....1..........8....57........4.....2..3...7............2.....6.18
....4.7..58.2......1..........8....57........4.....2..3...7............2.....6.18
....4.7.6.8.2......1..........8....57........4.....2..3...7............2.....6.18
...54.7...8.2......1..........8....57........4.....2..3...7............2.....6.18
..9.4.7...8.2......1..........8....57........4.....2..3...7............2.....6.18

12 puzzles in grid
635241789987563124214789563123897645756432891498615237342178956861954372579326418
....4.7...8........1..........8..6..7........4.....2.73.2.7..5...............6.18
....4.7...8........1.....6....8.....7........4.....2.73.2.7.9................6.18
....4.7...8........1.....6....8....57........4.....2..3...7......1.....2.....6.18
....4.7...8........1.....6....8....57........4.....2..3..17............2.....6.18
....4.7...8........1.....6....8....57........4.....2..3.2.7............2.....6.18
....4.7...8........1.....6....8....57........4.....2..3.2.7...........7......6.18
....4.7...8........1.....6....8....57........4.....2.73.2.7..................6.18
....4.7...8........1.....6....8....57....2...4.....2..3...7............2.....6.18
....4.7...8........1....5.....8.....7........4.....2.73.2.7...6..............6.18
....4.7...8.....2..1.....6....8....57........4.....2..3.2.7..................6.18
...24.7...8........1..........8....57........4.....2..3...7.9..........2.....6.18
...24.7...8........1.....6....8....57........4.....2..3...7............2.....6.18

11 puzzles in grid
653241789984765123217983564125837946796452831438619257342178695861594372579326418
....4.7...8........1..........8....67........4.....25.3.2.7............2.....6.18
....4.7...8........1..........8....67........4.....25.3.2.7...........7......6.18
....4.7...8........1..........8....67........4.....25.3.2.7.........4........6.18
....4.7...8........1..........8....67........4.....2573.2.7..................6.18
....4.7...8........1..........8....67..4.....4.....25.3.2.7..................6.18
....4.7...8........1..........8...467........4.....25.3.2.7..................6.18
....4.7...8........1..........8.7..67........4.....25.3.2.7..................6.18
....4.7...8........1.....6....8.....7........4.....2573.2.7..................6.18
....4.7...8........1.....6....8.7...7........4.....25.3.2.7..................6.18
....4.7...8.....2..1..........8....67........4.....25.3.2.7..................6.18
...24.7...8........1..........8....67........4.....25.3...7............2.....6.18

9 puzzles in grid
635241789987563124214789653123897546756432891498615237342178965861954372579326418
....4.7...8........1.....5....8....67........4.....2..3...7......1.....2.....6.18
....4.7...8........1.....5....8....67........4.....2..3..17............2.....6.18
....4.7...8........1.....5....8....67........4.....2..3.2.7............2.....6.18
....4.7...8........1.....5....8....67........4.....2..3.2.7...........7......6.18
....4.7...8........1.....5....8....67........4.....2.73.2.7..................6.18
....4.7...8........1.....5....8....67....2...4.....2..3...7............2.....6.18
....4.7...8.....2..1..........8....67........4.....2..3.2.7.9................6.18
....4.7...8.....2..1.....5....8....67........4.....2..3.2.7..................6.18
...24.7...8........1.....5....8....67........4.....2..3...7............2.....6.18

7 puzzles in grid
.5..4.7...8.2......1..........8....57........4.....2..3...7............2.....6.18
..3.4.7...8.2......1..........8....57........4.....2..3...7............2.....6.18
....4.7...8.29.....1..........8....57........4.....2..3...7............2.....6.18
....4.7...8.2......1..........8....57.5......4.....2..3...7............2.....6.18
....4.7...8.2......1..........8....57...6....4.....2..3...7............2.....6.18
....4.7...8.2......1..........8....57........43....2..3...7............2.....6.18
....4.7...8.2......1..........8....57........4....92..3...7............2.....6.18

5 puzzles in grid
....4.7...8.2......1..........8....37........4.....25.3...7............2.....6.18
....4.7...8.2......1..........8....37.5......4.....2..3...7............2.....6.18
....4.7...8.2......1..........85...37........4.....2..3...7............2.....6.18
....4.7..58.2......1..........8....37........4.....2..3...7............2.....6.18
...54.7...8.2......1..........8....37........4.....2..3...7............2.....6.18

5 puzzles in grid
..5.4.7...8........1.2........8....57........4.....2..3...7............2.....6.18
...94.7...8........1.2........8....57........4.....2..3...7............2.....6.18
....4.7..98........1.2........8....57........4.....2..3...7............2.....6.18
....4.7...8........1.2........8....57...5....4.....2..3...7............2.....6.18
....4.7...8........1.2........8....57........45....2..3...7............2.....6.18

5 puzzles in grid
....4.7...8.2......1..........8....57........4.....2..3...7........9...2.....6.18
....4.7...8.2......1..........8....57........4.....2..3...7.......5....2.....6.18
....4.7...8.2......1..........8....57........4..9..2..3...7............2.....6.18
....4.7...8.2......1..........8....57........45....2..3...7............2.....6.18
....4.7...8.2......1..........8....57...5....4.....2..3...7............2.....6.18
 
3 puzzles in grid
....4.7...8........1.2........8....57........4.....29.3...7............2.....6.18
....4.7...8........1.2.......98....57........4.....2..3...7............2.....6.18
.9..4.7...8........1.2........8....57........4.....2..3...7............2.....6.18

3 puzzles in grid
....4.7...8........1..........8....67........4.....25.3.5.7............5.....6.18
....4.7...8........1....5.....8....67........4.....25.3.5.7..................6.18
...54.7...8........1..........8....67........4.....25.3...7............5.....6.18

2 puzzles in grid
....4.7...8........1.2........8....57......9.4.....2..3...7............2.....6.18
....4.7...8........1.2........8....57...3....4.....2..3...7............2.....6.18
2puzzles in grid
....4.7...8........1.2........89...57........4.....2..3...7............2.....6.18
....4.7...8........1.2.......38....57........4.....2..3...7............2.....6.18
 
2 puzzles in grid
....4.7...8........1.2........8....57........4..9..2..3...7............2.....6.18
....4.7...8..5.....1.2........8....57........4.....2..3...7............2.....6.18

2 puzzles in grid 
....4.7...8........1.2........8....57........4..5..2..3...7............2.....6.18
....4.7...8..9.....1.2........8....57........4.....2..3...7............2.....6.18 

1 puzzle in grid
....4.7...8.5......1..........8...9.7........4.....2.53...7...........5......6.18
....4.7...8..2....51..........8....57........4.....2..3.2.7..................6.18
...24.7...8........1..........8....57........4.....29.3...7............2.....6.18
....4.7...8........1.2........8...5.7........4.....2.93...7...........2......6.18
...54.7...8.2......1..........8.....7....3...4.....2..3...7............2.....6.18
....4.7...8.5......1..........8....97........4.....25.3...7............5.....6.18
....4.7...8........1.5........8....37....9...4.....2..3...7............5.....6.18
....4.7...8.5......1..........8....37....9...4.....2..3...7............5.....6.18
....4.7..58.2......1..........8.....7....9...4.....2..3...7............2.....6.18
....4.7...8.5......1..........8....97....2...4.....2..3...7............5.....6.18
....4.7...8.....5..1.2........8.....7....3...4.....2..3...7..9...............6.18
....4.7...8........1.2........8....37.5......4.....2..3...7............2.....6.18
....4.7...8........1.5........8....37....2...4.....2..3...7............5.....6.18
....427...8........1.5........8....37........4.....2..3...7............5.....6.18
....4.7...8........1.5........8....37.9......4.....2..3...7............5.....6.18


C

Edited...interchanges of 5&9
Last edited by coloin on Sat Aug 25, 2007 5:38 pm, edited 2 times in total.
coloin
 
Posts: 1632
Joined: 05 May 2005

Postby gsf » Sat Aug 25, 2007 4:36 pm

coloin wrote:With a 4-on search [actually 58 times 3-ons] in two hours I had 132 different puzzles [none new]

but you have been adding a bunch of new ones lately
a change in tactics?
I basically have 4 21/20 clue generators passed into {-2+1}xn to get to 17 running in the background
for an average ~5 new 17s / day
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Sat Aug 25, 2007 6:04 pm

gsf wrote:change in tactics ?


I am not sure if what I am doing is much different....except

I suppose I have two computors at work working over the WE on large [100k] dat files of 18s. So it is probably a reflection of the number of 18s you search.

However.......I am making the 18s differntly

Recently I have used 2 sourses
1- start from the SF grid, {-1+2} make a lot of 18s, 1*x4
2- start from the remote 4* 17s[-1+2} you posted ! and make 18s, 1*x4

remove "useless" 18s derived from the original 17s

I perform a furthur 3x1* , subjecting only the new ones made in the last 1* to a {-2+1}

I am getting new puzzles from both methods - i think the puzzles end up having 6 or 7 clues different from the original 17 !!!.

I think by fanning out the 18s you increase the chances of finding new ones. Its a bit like trawling with a larger net . I think succesive {1*} gets you more into puzzles already found - and I have been able to remove some of these useless18s from my search dat files. I am still generating many non new 17s along the way - its impossible to avoid this entirely.

By not repeating searches you save time
eg if you have a series of {1*} actions on a file of 18puzzles
making file1,file2,file3,file4,file5,file6,file7,file8......
it is only worth searching new puzzles in file3-[2+1] and file7-[6+5+4+3+2+1]
the inbetween files are represented in the search

With Havards Beta-program which he leant me, it is relatively easy to subtract/remove unwanted puzzles from each successive generation. Once the dat file is pruned the puzzles just keep coming !

It does a {-2+2} on a 17 in 6 minutes
It does a {-2+1} on an 18 in 2 seconds
It does a {-1+1} on an 18 in 1/10 second

And it works in windows !

I still use your canonicalization siftware !

C
coloin
 
Posts: 1632
Joined: 05 May 2005

Postby JPF » Sat Aug 25, 2007 9:29 pm

coloin wrote:I suppose I have two computors at work working over the WE on large [100k] dat files of 18s. So it is probably a reflection of the number of 18s you search.

Yes, of course.

We all end up with a lot of 18s and use a {-2+1} to find 17s.
It will be nice to know the yield = (number of new 17s)/(number of 17s produced)

As I mentionned earlier, I'm around 4%.
For example, I produced yesterday a batch of 237 17s ; 9 were new.
yield = 9/237 = 3.8%

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby coloin » Sun Aug 26, 2007 6:55 pm

JPF wrote:As I mentionned earlier, I'm around 4%.
I dont think I find as many
My last run, I found 4 new ones out of 176, so around 2.2%
I devided the ordered dat file into 3 parts
Code: Select all
          17s made    new
file 1        161      1
file 2        113      1
file 3        155      2
file 1+2+3    176      4


My other run, despite producing a large number of puzzles, there were 11 new out of 1013 [1.1%].

And to complete the grids which have an exceptional number of puzzles I was able to morph the puzzles from the grid with 14 17puzzles, to within 3 of one * of the puzzles from the SF grid.
Code: Select all
14clue subpuzzle
....4.7...8........1.....2....8..9.67........4..........2.7....................18
Code: Select all
29puzzlegrid                                                                     
..9.4.7...8........1.....2....8....67........4.....2..3.2.7..................6.18
...24.7...8.....9..1..........8....67........4.....2..3...7............2.....6.18
...24.7...8.......51..........8....67........4.....2..3...7............2.....6.18
...24.7...8........1.....2....8....67........4.....2..3...7...5..............6.18
....4.7.5.8........1.....2....8....67........4.....2..3.2.7..................6.18
....4.7...8...5....1.....2....8....67........4.....2..3.2.7..................6.18
....4.7...8.....9..1.....2....8....67........4.....2..3.2.7..................6.18
....4.7...8.....9..1..........8....67........4.....2.73.2.7..................6.18
....4.7...8.....9..1..........8....67........4.....2..3.2.7...........7......6.18
....4.7...8.....9..1..........8....67........4.....2..3.2.7............2.....6.18
....4.7...8.....9..1..........8....67........4.....2..3..17............2.....6.18
....4.7...8.....9..1..........8....67........4.....2..3...7......1.....2.....6.18
....4.7...8.......51.....2....8....67........4.....2..3.2.7..................6.18
....4.7...8.......51..........8....67........4.....2.73.2.7..................6.18
....4.7...8.......51..........8....67........4.....2..3.2.7...........7......6.18
....4.7...8.......51..........8....67........4.....2..3.2.7............2.....6.18
....4.7...8........1.9...2....8....67........4.....2..3.2.7..................6.18 *
....4.7...8........1.....2....85...67........4.....2..3.2.7..................6.18
....4.7...8........1.....2....8..9.67........4.....2..3.2.7..................6.18
....4.7...8........1.....2....8....679.......4.....2..3.2.7..................6.18
....4.7...8........1.....2....8....67......5.4.....2..3.2.7..................6.18
....4.7...8........1.....2....8....67........45....2..3.2.7..................6.18
....4.7...8........1.....2....8....67........4....92..3.2.7..................6.18
....4.7...8........1.....2....8....67........4.....2..3.2.7.5................6.18
....4.7...8........1.....2....8....67........4.....2..3.2.7...9..............6.18
....4.7...8........1.....2....8....67........4.....2..3.2.7.......5..........6.18
....4.7...8........1.....2....8....67........4.....2..3.2.7........9.........6.18
....4.7...8........1.....2....8....67........4.....2..3.2.7.............9....6.18
....4.7...8........1.....2....8....67........4.....2..3.2.7...............5..6.18
                                                         
14puzzlesgrid                                                                   
....4.7.5.8........1.9........8....67.2..3...4........3...7............9.......18
....4.7...8....1...1.9........8....67.2..3...4........3...7............9.......18
....4.7...8.....9..1.9........8....67.2..3...4........3...7............9.......18
....4.7...8........1.9........8..9.67.2..3...4........3...7............9.......18
....4.7...8........1.9........8....6792..3...4........3...7............9.......18
....4.7...8........1.9........8....679...3...4.....2..3...7............9.......18
....4.7...8........1.9........8....67.2.63...4........3...7............9.......18
....4.7...8........1.9........8....67.2..3.5.4........3...7............9.......18
....4.7...8........1.9........8....67.2..3..14........3...7............9.......18
....4.7...8........1.9........8....67.2..3...46.......3...7............9.......18
....4.7...8........1.9........8....67.2..3...4...1....3...7............9.......18
....4.7...8........1.9........8....67.2..3...4.....2..3...7............9.......18
....4.7...8........1.9........8....67....3...4.....2..35..7............9.......18
....4.7...8........1.9........8....67....3...4.....2..3.9.7............9.......18
                                                                                 
8puzzlegrid                                                                     
..5.4.7...8........1.9........8....67........4....32..3...7............9.......18
...64.7...8........1.9........8....67........4....32..3...7............9.......18
....4.7..68........1.9........8....67........4....32..3...7............9.......18
....4.7...8...2....1.9........8....67........4....32..3...7............9.......18
....4.7...8........1.9........8....67........4....32..3..57............9.......18
....4.7...8........1.9........8....67........4....32..3...7.........6..9.......18
....4.7...8........1.9........8....67........4....32..3...7............95......18
....4.7...8........1.9........8....67........4....32..3...7............9..6....18

Yet again ALL Strangely Familiar !!!!

C
coloin
 
Posts: 1632
Joined: 05 May 2005

Postby gsf » Sun Aug 26, 2007 8:08 pm

coloin wrote:With Havards Beta-program which he leant me, it is relatively easy to subtract/remove unwanted puzzles from each successive generation. Once the dat file is pruned the puzzles just keep coming !

It does a {-2+2} on a 17 in 6 minutes
It does a {-2+1} on an 18 in 2 seconds
It does a {-1+1} on an 18 in 1/10 second

And it works in windows !

I periodically check to make sure I'm in the ballpark
could you post your cpu Ghz and the example 17 and 18 clue puzzles for the above timings
and either the output puzzles or puzzle counts if the output is too large

thanks
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby JPF » Mon Aug 27, 2007 11:19 am

Does anybody have an idea on the number of inequivalent patterns with 17 clues ?

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby Lars Petter Endresen » Mon Aug 27, 2007 8:30 pm

could you post your cpu Ghz and the example 17 and 18 clue puzzles for the above timings


Sudoku Architect may run ~4 times faster on a 2 GHz Core 2 Duo, than on a 2 GHz Pentium M or Pentium 4, as the former CPU has twice as many cores and the double amount of integer execution units within each core. The program automaticaly threads to the number of cores presents, so a 16 Core server may give ~ 16 times the speed of the single Core 2 Solo, at the same GHz.
Lars Petter Endresen
 
Posts: 7
Joined: 03 June 2007
Location: NORWAY

Postby gfroyle » Tue Aug 28, 2007 12:04 pm

JPF wrote:Does anybody have an idea on the number of inequivalent patterns with 17 clues ?

JPF


Yes.. there are Binomial(81,17) ways of selecting 17 cells

128447994798305325

The group acting on the set of patterns to form equivalence classes has size 6^8 x 2 = 3359232.

So a lower bound on the number of inequivalent patterns is

128447994798305325 / 3359232 = 38237309836

or about 38.237 x 10^9.

If every pattern had no non-trivial symmetries, then this would be the exact number, but patterns with symmetries have smaller equivalence classes and therefore cause this number to be an underestimate.

By standard combinatorial experience, the number of patterns with symmetries will be an insignificant proportion of the total and hence that number will be accurate to several significant figures...

Cheers

Gordon

PS Might be worth tackling with a million computers... maybe we could get the guys who run the Storm botnet to run Sudoku instead of sending spam!
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby JPF » Tue Aug 28, 2007 6:59 pm

Thanks Gordon.

I was quite sure I would get an answer from you.

Finally, I'm not so bad in combinatorics:) :
I got the lower bound as you did : 81!/(17!64!x 2 x 6^8)

But I was not able to go further.

38 x 10^9 is a lot:(

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby coloin » Fri Aug 31, 2007 7:53 pm

:idea::idea::idea::idea::idea::idea:

Can we speed up the present search a factor of 5 with this approach:?:

At present we are making 17s from 18s using a 2-off/1-on method....

We have been searching in the background sets of 30000 puzzles...... getting arouund 300 17s of which maybe 1 or 2 are new. This has been taking around a day for each set of 18s.

Successive {-1+1} generates new 18s, it appears there is no substitute for searching as many 18s as possible, and in general any one 18 is no more or less likely to give us a 17 than any other, near or far off.

Non minimal 18s will occur in the {-1+1} from an 18 which would have given a 17 if a {-2+1} had been performed instead.

Therefore

instead of {-1+1}x5{-2+1}

do {1+1}x6{-1+0}........... might it be ? 5 times quicker !!!

Code: Select all
18 {-2+1*} =   [16]      + [1*]       [17 clue puzzle]
18 {-1+1*} =   [16 + 1s] + [1*]       [18 clue non-minimal puzzle]

where [1s] is superfluous clue

C
coloin
 
Posts: 1632
Joined: 05 May 2005

Postby wintder » Sat Sep 01, 2007 12:39 pm

The -1 + 0 will only work on a non minimal puzzle.

-2 + 1 MIGHT work on any puzzle.
wintder
 
Posts: 297
Joined: 24 April 2007

Postby coloin » Sat Sep 01, 2007 4:37 pm

I agree.....I will edit it to

If a {-2+1} works to produce a 17 then a {-1+1} might give a non minimal 18..................

But it unfortunately doent work all the time [perhaps only 25%]

The superfluous clue limits very much the possible clue placements.

If a non-minimal 18 is produced the next {-1+1} is going to make 62 other non minimal 18s. The next {-1+1} on these 18s is going to be even more unproductive !

This would explain why the generation of new 17s is not proportional to the size of the set of 18s made with the {-1+1} function.

Im not sure how it can be easily prevented.

C
coloin
 
Posts: 1632
Joined: 05 May 2005

PreviousNext

Return to General