SudokuSolver Forum

A forum for Sudoku enthusiasts to share puzzles, techniques and software
It is currently Thu Mar 28, 2024 8:20 pm

All times are UTC




Post new topic Reply to topic  [ 5 posts ] 
Author Message
 Post subject: One-clue Jigsaw (NC)
PostPosted: Mon Feb 11, 2019 4:48 am 
Offline
Addict
Addict

Joined: Sat Jan 05, 2019 1:02 pm
Posts: 40
Location: Canberra, Australia
.
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 6711 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".


Top
 Profile  
Reply with quote  
 Post subject: Re: One-clue Jigsaw (NC)
PostPosted: Wed Mar 20, 2019 6:47 pm 
Offline
Grand Master
Grand Master

Joined: Wed Apr 23, 2008 6:04 pm
Posts: 1893
Location: Lethbridge, Alberta, Canada
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 6562 times ]
One Clue Jigsaw (NC) 2.jpg
One Clue Jigsaw (NC) 2.jpg [ 124.24 KiB | Viewed 6562 times ]
Top
 Profile  
Reply with quote  
 Post subject: Re: One-clue Jigsaw (NC)
PostPosted: Wed Mar 20, 2019 7:57 pm 
Offline
Addict
Addict

Joined: Sat Jan 05, 2019 1:02 pm
Posts: 40
Location: Canberra, Australia
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 6560 times ]

Cheers
MM


Top
 Profile  
Reply with quote  
 Post subject: Re: One-clue Jigsaw (NC)
PostPosted: Thu Mar 21, 2019 9:06 am 
Offline
Addict
Addict

Joined: Sat Jan 05, 2019 1:02 pm
Posts: 40
Location: Canberra, Australia
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 6550 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.


Top
 Profile  
Reply with quote  
 Post subject: Re: One-clue Jigsaw (NC)
PostPosted: Sat Mar 23, 2019 3:58 am 
Offline
Addict
Addict

Joined: Sat Jan 05, 2019 1:02 pm
Posts: 40
Location: Canberra, Australia
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-)


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 5 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 7 guests


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 post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group