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
SudokuJ-NC-001.png [ 7.33 KiB | Viewed 6826 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:
This is a jigsaw; I’ve identified the jigsaw houses by their upper-left corners, for example HR1C8.
The puzzle is non-consecutive horizontally and vertically.

1a. 4 placed for R5, C7 and HR2C5
1b. R5C7 = 4 -> no 3,5 in R46C7 + R5C68 (NC)

2. Law of Leftovers(LoL) R1456C7 must contain exactly the same numbers as R9C3456 -> 4 in R9C3456, locked for R9 and HR8C8
Note that R1456C7 cannot contain more than one of 3,5 -> R9C3456 cannot contain more than one of 3,5

[Noting the rotational symmetry of the jigsaw houses, it’s possible that the solution may also be rotationally symmetric, meaning that the total of any two cells symmetrical about the centre of the grid with total 10, the first guess …]
3. Try R5C3 = 6, placed for R5, C3 and HR4C3
3a. R5C3 = 6 -> no 5,7 in R46C3 + R5C24 (NC)

4. LoL R4569C3 must contain exactly the same numbers as R1C4567 -> 6 in R1C4567, locked for R1 and HR1C1
Note that R4569C3 cannot contain more than one of 5,7 -> R1C4567 cannot contain more than one of 5,7

[Continuing making guesses based on the unproven assumption of rotational symmetry.]
5. R5C12 cannot contain both of 1,2 or 8,9, similarly for R5C89 while R5C456 cannot contain all of these numbers so assume that R5C12 contains either {18} or {29} with R5C89 containing the other pair for rotational symmetry (as this is a guess there’s no good reason why those cells shouldn’t contain 3 and 7) -> R5C456 = [357], placed for R5 and HR2C4, 3 placed for C4, 5 for C5 and 7 for C65a. R5C456 = [357] -> no 2 in R46C4, no 4 in R46C4 + R6C5, no 6 in R4C56 + R6C6, no 8 in R46C6
5b. 5 in HR2C5 only in R234C6, locked for C6, no 6 in R3C6 (NC)
5c. 5 in HR4C3 only in R678C4, locked for C4, no 4 in R7C4 (NC)

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.

Attachments:
One Clue Jigsaw (NC) 1.jpg
One Clue Jigsaw (NC) 1.jpg [ 128.93 KiB | Viewed 6677 times ]
One Clue Jigsaw (NC) 2.jpg
One Clue Jigsaw (NC) 2.jpg [ 124.24 KiB | Viewed 6677 times ]
Author:  Mathimagics [ Wed Mar 20, 2019 7:57 pm ]
Post subject:  Re: One-clue Jigsaw (NC)
Hi Andrew,

A valiant attempt! 8-)

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:
Attachment:
OneClue-JNC.png
OneClue-JNC.png [ 31.21 KiB | Viewed 6675 times ]

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:
Attachment:
OneClue-JNC-A.png
OneClue-JNC-A.png [ 7.96 KiB | Viewed 6665 times ]


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):

  • {r1c4, r1c5, r1c6, r1c7} and {r4c3, r5c3, r6c3, r9c3}

  • {r9c3, r9c4, r9c5, r9c6} and {r1c7, r4c7, r5c7, r6c7}

  • {r1c1, r1c2, r2c1, r2c2} and {r2c3, r3c3, r7c3, r8c3}

  • {r8c8, r8c9, r9c8, r9c9} and {r2c7, r3c7, r7c7, r8c7}

Combining these with the obvious 2-cell matches ( {r1c8, r1c9} = {r2c1, r2c2} and {r9c1, r9c2} = {r8c8, r8c9} ), we can further infer that:

  • r2c3 = r1c1 or r1c2

  • r8c7 = r9c8 or r9c9

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! 8-)
Page 1 of 1 All times are UTC
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/