## SudokuFP

For fans of Killer Sudoku, Samurai Sudoku and other variants

### SudokuFP

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

Consider this example:
SudokuFP-Example.png (11.59 KiB) Viewed 571 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 | +-------+-------+-------+`

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: SudokuFP

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 ?
coloin

Posts: 1918
Joined: 05 May 2005

### Re: SudokuFP

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

Posts: 88
Joined: 21 August 2017
Location: China

### Re: SudokuFP

coloin wrote: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

tarek

Posts: 3745
Joined: 05 January 2006

### Re: SudokuFP

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 10 0 0 1 1 1 1 1 11 0 0 0 1 1 1 1 11 1 0 0 0 1 1 1 11 1 1 0 0 0 1 1 11 1 1 1 0 0 0 1 11 1 1 1 1 0 0 0 11 1 1 1 1 1 0 0 01 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?

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: SudokuFP

Consider the center box:
Code: Select all
`According to JSudoku--25341....:  1672.3415...:  2202.341..5.: 23212.341...5:  561253.1.4..: 11992.3.154..:  4832.3.1.4.5:  8222.3.1..4.:115672.3.1...4: 157724..13...: 87202..413...: 14342...134..:127002...13.4.:1326924..1...3:148642.4.1...3: 3177TOTAL: 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..
qiuyanzhe

Posts: 88
Joined: 21 August 2017
Location: China

### Re: SudokuFP

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

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: SudokuFP

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

tarek

Posts: 3745
Joined: 05 January 2006

### Re: SudokuFP

tarek wrote: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?

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: SudokuFP

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...............................................................…5928461738463715291739258467385924614617382959251647382596173846174839523842596175 clues 3 symbols......2...........................1.........................3...........1...2....738495261261837495495162837972648513516273948384951726849516372627384159153729684Symmetric 5 clue+-------+-------+-------+| . . . | . . . | . . . || . . . | . . . | . . . || . . . | . . 5 | . . . |+-------+-------+-------+| . . . | . . . | 7 . . || . . . | . 9 . | . . . || . . 1 | . . . | . . . |+-------+-------+-------+| . . . | 6 . . | . . . || . . . | . . . | . . . || . . . | . . . | . . . |+-------+-------+-------+`

[EDIT: added Disclaimer regarding difficulty of above 3 puzzles]
Last edited by tarek on Wed Jan 09, 2019 8:31 pm, edited 1 time in total.

tarek

Posts: 3745
Joined: 05 January 2006

### Re: SudokuFP

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
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: SudokuFP

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

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: SudokuFP

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

tarek

Posts: 3745
Joined: 05 January 2006

### Re: SudokuFP

Non-Consecutive solution grid count
Code: Select all
`Non-Consecutive: FP(12 23 34 45 56 67 78 89)Centerbox | Count | *  | Total  | Notes2.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 | *=1234**.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.
Last edited by qiuyanzhe on Thu Jan 10, 2019 5:58 am, edited 2 times in total.
qiuyanzhe

Posts: 88
Joined: 21 August 2017
Location: China

### Re: SudokuFP

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

tarek

Posts: 3745
Joined: 05 January 2006

Next