SudokuFP

For fans of Killer Sudoku, Samurai Sudoku and other variants

SudokuFP

Postby Mathimagics » Mon Jan 07, 2019 8:10 pm

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

Consider this example:
SudokuFP-Example.png
SudokuFP-Example.png (11.59 KiB) Viewed 327 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 |
 +-------+-------+-------+
User avatar
Mathimagics
2017 Supporter
 
Posts: 1263
Joined: 27 May 2015
Location: Canberra

Re: SudokuFP

Postby coloin » Tue Jan 08, 2019 9:18 am

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: 1790
Joined: 05 May 2005

Re: SudokuFP

Postby qiuyanzhe » Tue Jan 08, 2019 9:36 am

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..
qiuyanzhe
 
Posts: 78
Joined: 21 August 2017
Location: China

Re: SudokuFP

Postby tarek » Tue Jan 08, 2019 9:38 am

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) :D

I know where all of this heading: chess piece FP and then Anti chess :D . 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 :twisted:

Tarek
User avatar
tarek
 
Posts: 2966
Joined: 05 January 2006

Re: SudokuFP

Postby Mathimagics » Tue Jan 08, 2019 12:35 pm

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?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1263
Joined: 27 May 2015
Location: Canberra

Re: SudokuFP

Postby qiuyanzhe » Tue Jan 08, 2019 1:43 pm

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..
qiuyanzhe
 
Posts: 78
Joined: 21 August 2017
Location: China

Re: SudokuFP

Postby Mathimagics » Tue Jan 08, 2019 6:21 pm

Thanks, qiuyanzhe, that gives me some useful data for comparison/verification purposes
User avatar
Mathimagics
2017 Supporter
 
Posts: 1263
Joined: 27 May 2015
Location: Canberra

Re: SudokuFP

Postby tarek » Tue Jan 08, 2019 7:04 pm

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" :idea:

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

tarek
User avatar
tarek
 
Posts: 2966
Joined: 05 January 2006

Re: SudokuFP

Postby Mathimagics » Wed Jan 09, 2019 1:28 am

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 :o


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

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?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1263
Joined: 27 May 2015
Location: Canberra

Re: SudokuFP

Postby tarek » Wed Jan 09, 2019 7:42 am

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]
Last edited by tarek on Wed Jan 09, 2019 8:31 pm, edited 1 time in total.
User avatar
tarek
 
Posts: 2966
Joined: 05 January 2006

Re: SudokuFP

Postby Mathimagics » Wed Jan 09, 2019 8:12 am

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?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1263
Joined: 27 May 2015
Location: Canberra

Re: SudokuFP

Postby Mathimagics » Wed Jan 09, 2019 8:30 am

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

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

Onward and upward downward!
User avatar
Mathimagics
2017 Supporter
 
Posts: 1263
Joined: 27 May 2015
Location: Canberra

Re: SudokuFP

Postby tarek » Wed Jan 09, 2019 1:15 pm

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
User avatar
tarek
 
Posts: 2966
Joined: 05 January 2006

Re: SudokuFP

Postby qiuyanzhe » Wed Jan 09, 2019 1:39 pm

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.
Last edited by qiuyanzhe on Thu Jan 10, 2019 5:58 am, edited 2 times in total.
qiuyanzhe
 
Posts: 78
Joined: 21 August 2017
Location: China

Re: SudokuFP

Postby tarek » Wed Jan 09, 2019 1:46 pm

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
User avatar
tarek
 
Posts: 2966
Joined: 05 January 2006

Next

Return to Sudoku variants