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 237 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: 1304
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 229 times


The other two are less obvious:

Hidden Houses 4-5: Show
HiddenHousesB.png
HiddenHousesB.png (2.89 KiB) Viewed 229 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: 1304
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 206 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: 1304
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 194 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: 1304
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: 56
Joined: 08 April 2019
Location: Girona, Catalonia


Return to Sudoku variants