The New Sudoku Players' Forum

[Mathimagics]

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 (2.01 KiB) Viewed 1989 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}.

[Mathimagics]

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 (3.87 KiB) Viewed 1981 times

The other two are less obvious:

Hidden Houses 4-5: Show

HiddenHousesB.png (2.89 KiB) Viewed 1981 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

[Mathimagics]

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 (6.24 KiB) Viewed 1958 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!

[Mathimagics]

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 (4.19 KiB) Viewed 1946 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}


[Wecoc]

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?

[mith]

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

[Mathimagics]

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 ...

[mith]

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]

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'

[Mathimagics]

My wife and I spent way too long on this ...

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)

[mith]

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

[Mathimagics]

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 ...

[mith]

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 )