Absolutely Clueless

For fans of Killer Sudoku, Samurai Sudoku and other variants

Absolutely Clueless

Postby Mathimagics » Mon Mar 25, 2019 7:42 pm

Ladies and Gentlemen!

I give you a puzzle with no givens, and yet only one solution.

Sudoku Jigsaw with Forbidden Pairs {15 18 23 39 49 57 59 68}

Clueless-JFP.png
Clueless-JFP.png (2.01 KiB) Viewed 1129 times


Forbidden Pairs: for the uninitiated, FP's specify that certain digit pairs can not be placed in adjacent cells. "Non-consecutive" Suduku is just one particular set of FP's, namely {12 23 34 45 56 67 78 89}.
Last edited by Mathimagics on Tue Mar 26, 2019 4:59 am, edited 2 times in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1804
Joined: 27 May 2015
Location: Canberra

Hidden Houses

Postby Mathimagics » Mon Mar 25, 2019 10:08 pm

Some Jigsaw layouts provide additional "clues" that are particular to the layout. The "Law of Leftovers" tells us that in some cases, certain cells have the same value, or that two pairs of cells must have the same two values, etc. This technique generally might be better called "Matching Sets" - two sets of N cells are matched if the layout implies that they must have the same N values.

"Hidden Houses" are a similar idea. If a set of N adjacent rows or columns contains N-1 complete regions, then the 9 "leftover" cells must constitute an additional region, with all the normal properties of a region - techniques such as candidate eliminations, naked/hidden singles, etc can be used on these as well.

The clueless puzzle above has 5 hidden houses. The first 3 are fairly obvious, they correspond to the 3 regions that span only 2 rows/cols:

Hidden Houses 1-3: Show
HiddenHousesA.png
HiddenHousesA.png (3.87 KiB) Viewed 1121 times


The other two are less obvious:

Hidden Houses 4-5: Show
HiddenHousesB.png
HiddenHousesB.png (2.89 KiB) Viewed 1121 times


Hidden houses can assist the human solver, but also the computer solver, as the following results demonstrate:

Code: Select all
Clueless solve time:
  Normal model:  SAT = 12.5s   dSolver = 14s
  Extra houses:  SAT =  9.8s   dSolver =  3s
User avatar
Mathimagics
2017 Supporter
 
Posts: 1804
Joined: 27 May 2015
Location: Canberra

Matching Sets

Postby Mathimagics » Tue Mar 26, 2019 11:44 am

Matching Sets can be determined by examining the list of Hidden Houses.

Look at the block of N rows (or columns) containing the hidden house - if that hidden house has 5, 6, 7 or 8 cells that are in the same Jigsaw region, then there is a Matching Set of size 4, 3, 2 or 1. There are 4,3,2 or 1 cells in the Jigsaw region that are outside the N x 9 block, and these correspond to the same number of cells inside the block that complete the hidden house. (These sets are sometimes called "innies" and "outies").

There are two such instances in the Jigsaw layout above. In each case the set size is 4, and there are 4 cells (marked "A") outside the block whose cell values must match the 4 cells marked "B"):

Matching Sets: Show
MatchedSets.png
MatchedSets.png (6.24 KiB) Viewed 1098 times


Assuming the computer solver knows about the hidden houses, there is little advantage to be gained from implementing Matching Sets checking.

But for P&P solvers, this is normally very useful information!
User avatar
Mathimagics
2017 Supporter
 
Posts: 1804
Joined: 27 May 2015
Location: Canberra

Absolutely Clueless #2

Postby Mathimagics » Tue Mar 26, 2019 6:56 pm

Here is a second example:

Forbidden Pairs: 13 18 19 23 26 35 48 58

JL:
Code: Select all
AAAADDEEBAAAADDEEBFFACDDEEBFCCCDDEEBFCHCCDEBBFCHHGGGBBFCHHGGIBIFFHHGGIIIFHHGGIIII


Clueless #2 image: Show
Clueless-JLFP0C-002.png
Clueless-JLFP0C-002.png (4.19 KiB) Viewed 1086 times


This JL appears at first sight to be much "weaker" than that of puzzle #1 above, as it gives many times the number of Jigsaw solutions, when fixing row 1 and solving as a normal Jigsaw:
Code: Select all
Puzzle #1:      3,594,861  solutions (fixed row 1)
Puzzle #2: 78,914,392,086  solutions (fixed row 1)


But this layout actually offers much more information for the player. There are 7 hidden houses, and several matching sets, so this puzzle might be more susceptible to attack by logic ...

Here is a JL analysis report from my solver - XH identifies an extra (hidden) house definition, and all matching sets are listed. The number pairs here are all simple cell identifiers, eg 85 = r8c5.

Code: Select all
        c1     : {11 21} = {32 82}
        c3     : {13 23 33 43} = {64 74 84 92}
        c6     : {66 76 86 96} = {15 25 35 45}
        c7     : {67 77 87 97} = {18 28 38 48}
        c9     : {79 89 99} = {58 68 78}
 XH # 1 c1 - c2: 11 21 12 22 42 52 62 72 92
 XH # 2 c5 - c6: 55 65 75 85 95 66 76 86 96  {55 96} = {67 94}
 XH # 3 c7 - c8: 67 77 87 97 58 68 78 88 98  {67 58 68 78} = {79 89 96 99}
 XH # 4 c8 - c9: 18 28 38 48 88 98 79 89 99  {18 28 38 48} = {77 87 96 97}
 XH # 5 c7 - c9: 67 77 87 97 88 98 79 89 99  {67} = {96}
 XH # 6 c1 - c4: 42 52 62 72 43 34 44 54 94  {94} = {55}
 XH # 7 c6 - c9: 16 26 36 46 56 66 76 86 67  {66 76 86 67} = {15 25 35 45}
 XH # 8 c1 - c5: 94 15 25 35 45 65 75 85 95  {15 25 35 45} = {66 67 76 86}
 XH # 9 c5 - c9: 55 65 75 85 95 66 76 86 67  {55} = {94}
 XH #10 c1 - c6: 94 65 75 85 95 66 76 86 96  {96} = {67}
 XH #11 c4 - c9: 14 24 34 44 54 64 74 84 55
 XH #12 c1 - c7: 96 17 27 37 47 57 77 87 97  {96 77 87 97} = {18 28 38 48}
User avatar
Mathimagics
2017 Supporter
 
Posts: 1804
Joined: 27 May 2015
Location: Canberra

Re: Absolutely Clueless

Postby Wecoc » Fri May 10, 2019 1:15 am

If you wanted to fill this with interchangable letters a-i without considering the forbidden pairs, would it still have 1 unique solution? (without considering the letter interchanges, let's say one of the regions has fixed letters)
In other words, the FP (and the bonds between numbers they make) are mainly used to disambiguate between the a-i solution and the real unique 1-9 solution, or they do much more than that in the solving process? :?
Wecoc
 
Posts: 76
Joined: 08 April 2019
Location: Girona, Catalonia

Re: Absolutely Clueless

Postby mith » Tue Dec 08, 2020 10:28 pm

Bumping this to note that the digits in the first example can be permuted to give the following rule:

Adjacent digits summing to 9 must be coprime; other adjacent digits must be non-consecutive. (This is a subset of "anti-kropki" constraints, since the only pair summing to 9 that isn't coprime is also the only pair summing to 9 with a 2:1 ratio.)

15 18 23 39 49 57 59 68
76 78 12 23 43 65 63 98
mith
 
Posts: 577
Joined: 14 July 2020

Re: Absolutely Clueless

Postby Mathimagics » Wed Dec 09, 2020 6:03 am

Apologies to Wecoc, I had no idea a question had been asked, until mith bumped this thread! :?

The answer is that letters and numbers are interchangeable, Sudoku NxN is about sets of N symbols, these can be anything, as long as they are distinct.

It is only when certain clue types (eg non-consecutive, inequality/Futoshiki) are used that the symbols are required to have some known order ...

Forbidden Pair clues don't imply any numerical properties, they simply define pairs of symbols that can't be adjacent, so you can use letters instead of numbers ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1804
Joined: 27 May 2015
Location: Canberra

Re: Absolutely Clueless

Postby mith » Wed Dec 09, 2020 5:19 pm

Now I'm wondering if there is a particular set of letters you could pick so that you could arrange the forbidden pairs to spell a message. :)
mith
 
Posts: 577
Joined: 14 July 2020

Re: Absolutely Clueless

Postby mith » Thu Dec 10, 2020 5:07 am

My wife and I spent way too long on this, and came up with the following morph:

VE RB OT EN BO RD ER IN'
mith
 
Posts: 577
Joined: 14 July 2020

Re: Absolutely Clueless

Postby Mathimagics » Fri Dec 11, 2020 5:02 am

mith wrote:My wife and I spent way too long on this ...
:lol:

More might be possible - have you considered what might be done with any number of repeats, and given that you actually have 16 pairs to play with? (in your example VE and EV are both allowed)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1804
Joined: 27 May 2015
Location: Canberra

Re: Absolutely Clueless

Postby mith » Thu Dec 17, 2020 4:44 am

We were actually deliberately avoiding repeats; originally we were trying to make something work with FO RB ID DE NP AI R... but never found a nice finish that kept the structure of either puzzle.

How difficult were these to find? I was considering reversing the process and coming up with a potential phrase first (which is already hard, since the pairs need to be connected in such a way that no permutations are possible).
mith
 
Posts: 577
Joined: 14 July 2020

Re: Absolutely Clueless

Postby Mathimagics » Thu Dec 17, 2020 7:08 am

mith wrote:How difficult were these to find?

Not very difficult, if I remember correctly ... unfortunately my recall is basically a push-down stack, and so I can't recall exactly where I put the code , or the exact process involved :?

The basic idea is to take a jigsaw layout, generate random solutions, test the solution grids for FP candidates (ie pairs that don't occur in the grid), then solve with the FP's to see if the solution is then unique.

If the jigsaw layout is combined with standard boxes, that would seem to be even more likely to yield a clueless, but I never did that. Typically, as soon as I found the example above, I declared victory and abandoned the field ... 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1804
Joined: 27 May 2015
Location: Canberra

Re: Absolutely Clueless

Postby mith » Tue May 18, 2021 12:58 pm

Another bump :)

I was able to find an example just with kropki rules (non-consecutive and non-2:1-ratio). It appears to be very hard - the irregular grid isn't particularly restrictive on its own - but maybe there's a way through it somehow.

https://sudokulab.net/?pzl=_2RlFHlw

(sudokulab's logical solver isn't very far along, I just like the look of it :))
mith
 
Posts: 577
Joined: 14 July 2020


Return to Sudoku variants