The New Sudoku Players' Forum

[Mathimagics]

Not another exotic variant, something a little more subtle this time.

Consider this example:

SudokuFP-Example.png (11.59 KiB) Viewed 1531 times

It looks like a normal Sudoku, right?

But you might have noticed that it has only 15 givens, and these only have 7 different values, so it's definitely not standard Sudoku, but oh, so close.

FP stands for "forbidden pairs". These additional clues specify that certain value-pairs can never occur in adjacent cells (in rows or columns). For the puzzle above the FP clues are {3,4}, {4,5} and {5,8}.

FP's can be redundant, too. There is another pair here:

ExtraPair: Show

Code: Select all

{1, 7}

that applies to this puzzle, but is not actually needed to solve it (it's already easy enough). Like all redundant clues, they can be used to eliminate more candidates, ie to simplify the puzzle.

So this variant is a close relation of "Consecutive Sudoku". These are "nice" variants because they require minimal interference (none at all in FP's case) to the presentation, and can be applied to just about any other variant (eg SudokuP, Jigsaw, Killer, Outside Clue, etc). They do the simple job of providing alternate forms of candidate elimination with minimal fuss.

I will perhaps leave the production of harder examples to my friends here, that should be fun. Or I can produce them myself if requested.

Cheers!

Solution: Show

Code: Select all

 +-------+-------+-------+
 | 5 9 3 | 6 1 4 | 7 8 2 |
 | 7 8 1 | 5 2 9 | 4 6 3 |
 | 2 6 4 | 7 8 3 | 9 5 1 |
 +-------+-------+-------+
 | 4 7 6 | 9 3 5 | 1 2 8 |
 | 9 3 8 | 1 6 2 | 5 7 4 |
 | 1 5 2 | 8 4 7 | 6 3 9 |
 +-------+-------+-------+
 | 6 2 9 | 4 7 8 | 3 1 5 |
 | 3 1 5 | 2 9 6 | 8 4 7 |
 | 8 4 7 | 3 5 1 | 2 9 6 |
 +-------+-------+-------+


[coloin]

What about stipulating the forbidden pairs formally - eg 1-2,2-3,3-4,4-5,5-6,6-7,7-8,8-9 [9-1 ?]
What would the min clues be ... or how difficult would the puzzles be ?

[qiuyanzhe]

Yes! FP is a common variant in competitions.. And most of the time the puzzles have another name, like--

Hidden Text: Show

Non Consecutive--12 23 34 45 56 67 78 89
Non Cons Variation--12 23 34 45 56 67 78 89 91
Non Cons 2--13 35 57 79 24 46 68
Non Cons 3..
No 4--13 14 15 37 59 48 28 26
No 9(add)--18 27 36 45
No VX--19 14 46 28 23 37
Primes(I forgot the actual name, cells adjacent to 1 contain primes)--14 16 18 19
An isomorph of the previous one, namely "Odd Ones"(not sure)--12 14 16 18

And sometimes just like in Consecutive Sudoku, there are some such pairs and all of them are marked with a dot--

Hidden Text: Show

Tennis--16 26 36 46 57 67 68 79
Tens--19 28 37 46(isomorph of Nines)
8--17 18 19 24 26 35
12--39 48 57 26 34
Mysterious Kropki--12 23 34 45 56 67 78 89 24 36 48

Admittedly, most of such rules appear only once, then they dies..

It is fairly great to summarize such types of rules, and there might also be some nice properties or puzzles in another rule..
For pairs that does not form loops(like 12 23 34 41)or branches(12 13 14), I make new puzzles by JSudoku, where we can design/generate (non-)consecutive puzzles with any set of digits, so we can set "1,2,3,4,5,7,8,9,10" it equals NonCons(2), or "1,2,3,4,6,7,8,9,11" for No VX..

[tarek]

What about stipulating the forbidden pairs formally - eg 1-2,2-3,3-4,4-5,5-6,6-7,7-8,8-9 [9-1 ?]
What would the min clues be ... or how difficult would the puzzles be ?

Oh Coloin, you are opening a can of worms ( non consecutive worms)

I know where all of this heading: chess piece FP and then Anti chess . All by the way close to my heart but such a big can of worms.

I’m losing pace to keep up with all of the variants. I can probably contribute to the NC project .

BTW coloin I’m not sure if you posed you question as a joke or not

Tarek

[Mathimagics]

The NC variants, and "No VX", etc, are all just specific examples of the general FP case.

From an analytical perspective I think that the underlying structure is really the truth-table that corresponds to each FP list (here I use 0 = forbidden, 1 = allowed). These have diagonal symmetry, obviously. The PTT (pairwise truth-table) for NC Sudoku would thus be:

Code: Select all

0 0 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1
1 0 0 0 1 1 1 1 1
1 1 0 0 0 1 1 1 1
1 1 1 0 0 0 1 1 1
1 1 1 1 0 0 0 1 1
1 1 1 1 1 0 0 0 1
1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 0


For the cyclic version of NC (where {1,9} is included), the TRC and BLC entries become 0, and the PTT is then "balanced" (same number of 0's in every row/col).

Some general questions that seem worth investigating:

• What is the distribution of solution grids with 0, 1, 2 … FP's

• How many essentially different PTT's are there?

• Geometric transformations applied to a grid usually alter the grid's PTT. So, for a given ED solution grid, S, what is the distribution of PTT's across the isotopes of S (ie the set of grids isomorphic to S)?

Specific questions:

• how many NC Sudoku grids are there?

[qiuyanzhe]

Consider the center box:

Code: Select all

According to JSudoku--
25341....:  167
2.3415...:  220
2.341..5.: 2321
2.341...5:  561
253.1.4..: 1199
2.3.154..:  483
2.3.1.4.5:  822
2.3.1..4.:11567
2.3.1...4: 1577
24..13...: 8720
2..413...: 1434
2...134..:12700
2...13.4.:13269
24..1...3:14864
2.4.1...3: 3177
TOTAL: 73081
*isomorph=8, there are 584648 nonconsecutive solutions with center cell 1(also that many with center=9)


These are copied manually, so these may not be reliable..
But I think starting from the center box can reduce repeating for isomorphic solutions..

[Mathimagics]

Thanks, qiuyanzhe, that gives me some useful data for comparison/verification purposes

[tarek]

I like the idea of the "Truth table" very much. This will allow to pair with more than 2 symbols if you want. I can also see how the No "VX" is now essentially the same set of symbols but linked in a different way (The 5 is the 11). All of which can be achieved via the "truth table"

I'm running the generator with some cyclic NC. I'm getting many puzzles with 4 givens & some puzzles have only 3 different symbols

tarek

[Mathimagics]

I'm running the generator with some cyclic NC. I'm getting many puzzles with 4 givens & some puzzles have only 3 different symbols

Hmm, I'll make a prediction here - most of those puzzles will solve to some isotope of the MC grid!

I take it by "cyclic NC" you mean the extended NC, ie including FP {1,9} ??

[EDIT] I mentioned the MC grid as it is particularly rich in NC solutions, so I put 2 and 2 together and got 100. The repeating minirows/cols could explain the low clue/symbol counts. But if you found these puzzles by reducing solution grids, then you'd know if the starting point was an MC grid. On the other hand, if you found them via clue-pattern testing, then it could still be true … do the solutions have lots of repeating minirows?

[tarek]

I didn't have a look at the solution grids to analyze. I also couldn't verify a single solution through other independent solvers:

Code: Select all

Cyclic NC (including 1,9) [All require multiple guesses to solve]
4 clues
..28........3.1...............................................................…
592846173846371529173925846738592461461738295925164738259617384617483952384259617

5 clues 3 symbols
......2...........................1.........................3...........1...2....
738495261261837495495162837972648513516273948384951726849516372627384159153729684

Symmetric 5 clue
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . 5 | . . . |
+-------+-------+-------+
| . . . | . . . | 7 . . |
| . . . | . 9 . | . . . |
| . . 1 | . . . | . . . |
+-------+-------+-------+
| . . . | 6 . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+

[EDIT: added Disclaimer regarding difficulty of above 3 puzzles]

[Mathimagics]

Interesting!

First solution is very close to MC. Minirows repeat in each band, but different between bands (although 592 repeats in all bands).

Code: Select all

 +-------+-------+-------+
 | 5 9 2 | 8 4 6 | 1 7 3 |
 | 8 4 6 | 3 7 1 | 5 2 9 |
 | 1 7 3 | 9 2 5 | 8 4 6 |
 +-------+-------+-------+
 | 7 3 8 | 5 9 2 | 4 6 1 |
 | 4 6 1 | 7 3 8 | 2 9 5 |
 | 9 2 5 | 1 6 4 | 7 3 8 |
 +-------+-------+-------+
 | 2 5 9 | 6 1 7 | 3 8 4 |
 | 6 1 7 | 4 8 3 | 9 5 2 |
 | 3 8 4 | 2 5 9 | 6 1 7 |
 +-------+-------+-------+


On the other hand, the second grid only has repeating minirows in the first band:

Code: Select all

 +-------+-------+-------+
 | 7 3 8 | 4 9 5 | 2 6 1 |
 | 2 6 1 | 8 3 7 | 4 9 5 |
 | 4 9 5 | 1 6 2 | 8 3 7 |
 +-------+-------+-------+
 | 9 7 2 | 6 4 8 | 5 1 3 |
 | 5 1 6 | 2 7 3 | 9 4 8 |
 | 3 8 4 | 9 5 1 | 7 2 6 |
 +-------+-------+-------+
 | 8 4 9 | 5 1 6 | 3 7 2 |
 | 6 2 7 | 3 8 4 | 1 5 9 |
 | 1 5 3 | 7 2 9 | 6 8 4 |
 +-------+-------+-------+


Ok, that's good. The 2nd example shows reductions like these can be achieved without being too close to the MC grid, ie without having many minirow repeats?

[Mathimagics]

.
Hmmm, is a one-given puzzle possible? I wonder ... was thinking 2 must be absolute minimum to resolve symmetry isomorphs, but maybe it can all be done with a single given ....

I'll need to get a more efficient solver built before I can play with these!

Well done on reaching 4, I'm suitably impressed!

Onward and upward downward!

[tarek]

With a simple cyclic NC relabelling the clues to shift the clues (biderectional) in addition to reflection/ rotation operations will give a minglex version of the solution grid

[qiuyanzhe]

Non-Consecutive solution grid count

Code: Select all

Non-Consecutive: FP(12 23 34 45 56 67 78 89)
Centerbox | Count | *  | Total  | Notes
2.3.1.... | 18917 | 16 | 302672 |
2...13... | 36123 | 16 | 577968 |
2**.1...3 | 18041 | 16 | 288656 | 4 in *
1.3.2.... | 46490 | 16 | 743840 |
1**.2...3 | 28852 | 16 | 461632 | 4 in *
2.4.3.... | 51995 | 16 | 831920 |
2**.3...4 | 22733 | 16 | 363728 | 5 in *
3.5.4.... | 41437 | 16 | 662992 |
3**.4...5 | 29105 | 16 | 465680 | 6 in *
4.6.5..*. | 22414 | 16 | 358624 | *=123
4**.5...6 | 28667 |  8 | 230936 | 7 in *
TOTAL=5288648


Still using JSudoku, but saved screensnaps.. and checked that numbers are not miscopied.
EDIT: The coefficients were wrong, corrected now.

[tarek]

With a non cyclical simple FP only the the start and endpoint are reversed to find a minlex isomorph. With a cyclic NC, any point can be the start and both directions can be reversed find the minlex isomorph