SudokuSolver Forum http://www.rcbroughton.co.uk/sudoku/forum/ |
|
One-clue Jigsaw (NC) http://www.rcbroughton.co.uk/sudoku/forum/viewtopic.php?f=13&t=1476 |
Page 1 of 1 |
Author: | Mathimagics [ Mon Feb 11, 2019 4:48 am ] |
Post subject: | One-clue Jigsaw (NC) |
. Over at SPF, we have been looking at minimum-clue puzzles for SudokuNC (Sudoku Non-Consecutive). The minimum number of clues currently stands at 3. But if we move to Sudoku Jigsaw's with NC constraints, we find there are 1-clue puzzles on offer. This was found by me last night: Attachment: SudokuJ-NC-001.png [ 7.33 KiB | Viewed 6850 times ] Now this is definitely not being suggested as a P&P puzzle, only as confirmation that such puzzles exist. JSudoku has confirmed it has a unique solution, and says that it required only 27 guesses to do this, so perhaps it is not that diabolical? Code: SumoCueV1=0J1=0J1=0J1=0J1=0J1=0J1=0J1=0J2=0J2=0J1=0J1=0J3=0J0=0J4 =0J4=0J2=0J2=0J2=0J3=0J3=0J3=0J0=0J4=0J4=0J2=0J2=0J2=0J3=0J3=0J5=0J0 =0J4=0J4=0J4=0J2=0J6=0J3=0J3=0J5=0J0=0J0=0J0=4J4=0J6=0J6=0J3=0J7=0J5 =0J5=0J5=0J0=0J4=0J6=0J6=0J7=0J7=0J7=0J5=0J5=0J0=0J6=0J6=0J6=0J7=0J7 =0J7=0J5=0J5=0J0=0J6=0J8=0J8=0J7=0J7=0J8=0J8=0J8=0J8=0J8=0J8=0J8 Interestingly, a rather astonishing 64 of the 81 cells in the solution grid can provide a "1-clue puzzle". |
Author: | Andrew [ Wed Mar 20, 2019 6:47 pm ] | |||
Post subject: | Re: One-clue Jigsaw (NC) | |||
I wondered what score SudokuSolver would give but it gave up almost immediately. Starting from the given clue I managed to get as far as 4 locked in R9C3456 as in my first diagram. Then a bit later I had the thought that, since the jigsaw houses are rotationally symmetric, the solution may also be, so I managed a few more steps based on this possibly unjustified assumption. My start: After reaching the position in the second diagram I couldn't see any way to make a further logical guess. Even though I'm a 'glutton for punishment', having solved some extremely hard killer sudokus, that was enough for me. Presumably JSudoku must have had some logic in making its guesses. If it made 27 purely trial-and-error guesses while rejecting other possibilities, then this puzzle is way beyond diabolical. Apologies for the diagrams being at the end of this post; I'm not sure how to place them in the text.
|
Author: | Mathimagics [ Wed Mar 20, 2019 7:57 pm ] |
Post subject: | Re: One-clue Jigsaw (NC) |
Hi Andrew, A valiant attempt! I only just realised that I did not post a solution (tsk, tsk). I don't think it exhibits any sign of rotational symmetery, sadly .... I can't find the text format, so here's a JSudoku solution image: Solution: Cheers MM |
Author: | Mathimagics [ Thu Mar 21, 2019 9:06 am ] |
Post subject: | Re: One-clue Jigsaw (NC) |
Andrew, The key to solving this is most probably in the Jigsaw layout. This may be of some use: Hidden Houses: The colours indicate what are effectively two additional (complete) houses. So, for a start we can see that the following pairs of 4-cell sets must have matching contents (any eliminations in one 4-cell set can be applied to the other):
Combining these with the obvious 2-cell matches ( {r1c8, r1c9} = {r2c1, r2c2} and {r9c1, r9c2} = {r8c8, r8c9} ), we can further infer that:
Does this help at all? My SAT solver runs faster with these additional houses defined. I will see if it also solves faster with the "matching sets" constraints added. |
Author: | Mathimagics [ Sat Mar 23, 2019 3:58 am ] |
Post subject: | Re: One-clue Jigsaw (NC) |
I wrote: The key to solving this is most probably in the Jigsaw layout. On reflection, I realise now that this is NOT true !! Jigsaw layouts can be powerful constraints, reducing the solution space considerably. Some Jigsaw layouts have no solutions at all. But this particular layout is actually quite modest when measured on this scale. If we drop the NC requirement, that is, treat it as a standard Sudoku Jigsaw, and fix the contents of any one row, col, or region, then we find there are around one billion solutions. When we add the NC constraint, however, the effect is rather astonishing. Removing that single clue reveals that there are just 4 solutions in total: Code: 135724968681379524246853179792418635357962481819537246463185792928641357574296813 318692475753146829297581364642735918184269753536814297971358642425973186869427531 792418635357964281813529746468375192926841357574296813139752468685137924241683579 975386142429731586864257931318692475753148629291573864647925318182469753536814297 The symmetry of the layout means that solutions #1 and #2 are essentially the same, just mirror images. The same goes for #3 and #4. The only relabelling allowed under NC rules is a reversal of the cell values, ie {123456789} is replaced by {987654321}, so solution #1 and solution #4 are essentially the same, and so are #2 and #3. So in fact there is only one "essentially different" solution! Also, if the single clue value I gave originally (4) is changed to any value other than 6, then the puzzle will have NO solution. On reflection, then, "beyond diabolical" (for P&P solving) is probably spot on! |
Page 1 of 1 | All times are UTC |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |