Sudoshiki (aka Sudoku Inequality) Generation, Properties

For fans of Killer Sudoku, Samurai Sudoku and other variants

Sudoshiki (aka Sudoku Inequality) Generation, Properties

Postby Mathimagics » Fri Dec 25, 2015 7:30 pm

I've recently turned my attention to the particular case of Sudoshiki, aka "Sudoku Inequality".

This is basically Futoshiki on a 9x9 grid, but with the added condition that the solution is a valid Sudoku grid.

I have been investigating p(U), ie the probability of a randomly generated grid having a unique solution. A grid has a unique solution in Futoshiki if and only if the corresponding set of clues ("<", ">") for every adjacent pair (ie: fully-specified ) uniquely corresponds to that grid.

For normal Futoshiki, ie: random latin squares of size 9, we have previously estimated p(U) = approx 1%. (see here)

But early testing of Sudoshiki grids suggests that p(U) for these cases is more like 30% !!

The only caveat is that I can't guarantee that my random Sudoku grid generator gives a uniformly distributed sample. Does anybody have access to the "full catalog" (5,472,730,538 classes) of Sudoku grids?

Or could anyone supply a sizeable sample thereof? Say a million or so?
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Sudoshiki Generation, Properties

Postby Mathimagics » Sat Dec 26, 2015 9:44 am

So roughly 1 in 3 Sudoku grids give rise to unique Sudoshiki solutions.

I then tested 20,000 of these U cases and found that around 1 in 16 were "pure", in the sense that these grids were unique solutions in regular Futoshiki. That is, they are still unique solution cases without the "unique in 3x3 block" restrictions.

This implies that the chances of a random 9x9 LS being U (wrt Futoshiki) are doubled (~ 2%) if the grid happens to have a Sudoku pattern.

I imagine that pure cases, when reduced (ie. clues removed to minimality) wrt Futoshiki, will still be further reducible for Sudoshiki.

Here are a couple of examples of "pure" grids.

Example 1:
Code: Select all
 9
 < < > < < > < > .
 > < > < > > < < .
 > < > > > < < < .
 > < < > < < < > .
 < > < > > < < > .
 < > < > < > < > .
 < > < > < < > < .
 < > > < > < > < .
 < > > < < < > < .
 > > < < > > < > <
 < < < < > > < < >
 < < > < > < < < >
 > < > > < < < < >
 < > < < < < > > >
 > > < > < > < > <
 > < < > < > > < <
 < < < > > < > < >
 . . . . . . . . .

Berthier format
 9
<<><<><>><><>><<><>>><<<><<><<<><><>><<><><><><><><><<><<>><><><<>><<<><
><<><>><><<<>><<<<>><<<<<<<><>>>>>><<<<>>><<<>><<<<<><>>><<<>><<<>>>><<>

Solution
4 5 6 2 8 9 1 7 3
3 1 8 4 7 6 2 5 9
7 2 9 5 3 1 4 6 8
9 3 4 7 1 2 5 8 6
5 8 1 6 4 3 7 9 2
6 7 2 9 5 8 3 4 1
2 4 3 8 6 7 9 1 5
1 6 5 3 9 4 8 2 7
8 9 7 1 2 5 6 3 4



Example 2:
Code: Select all
 9
 > < > < < > < > .
 < < < > > < > < .
 > < < > > > < > .
 < > < > < > > < .
 < > < > < < > < .
 > > < < > > > < .
 < < > < > < < > .
 < > > > < > > > .
 > < < < > < < < .
 > > > < > > < < <
 < < < > < > > < >
 > < > < > < < > <
 < < > > < > < < <
 < < < < < < > > >
 > > < > < > < < >
 < < < < > < > > >
 > > > > < > < < <
 . . . . . . . . .

Berthier format
 9
><><<><><<<>><><><<>>><><><><>><<><><<><>><<>>><<<><><<><>>><>>>><<<><<<
><><<><>><<<<><>><>><<<><><><><>><><<<><>><><><><><<><><<<><><><<><<>>><

Solution
7 4 9 1 6 8 3 5 2
1 2 5 9 4 3 8 6 7
8 3 6 7 5 2 1 9 4
2 5 4 8 1 9 7 3 6
6 7 1 3 2 5 9 4 8
9 8 3 4 7 6 2 1 5
4 6 7 2 9 1 5 8 3
5 9 8 6 3 7 4 2 1
3 1 2 5 8 4 6 7 9
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Sudoshiki Generation, Properties

Postby Mathimagics » Sat Dec 26, 2015 11:16 am

mathimagics wrote:I imagine that pure cases, when reduced (ie. clues removed to minimality) wrt Futoshiki, will still be further reducible for Sudoshiki.


Indeed that turns out to be true. Using example #1 above, I obtained this example of a reduced form wrt Futoshiki, in this case with 48 hints:
Code: Select all
 9
 < < > . . . . . .
 . . . . > . < . .
 . . . . . . < . .
 . . < . . . . > .
 < . . . > . < > .
 < . . . . . . . .
 < > < . . . . . .
 . > . . . . . . .
 < . . < . < . . .
 > . . . > . < > .
 . . . < . . . . >
 < . > . . < . . >
 . . . > . < . . .
 < . < < < . . . .
 . . < > < . . > .
 > . . . < . > . <
 . < < . . < > . .
 . . . . . . . . .

Berthier format
 9
<<>--------->-<-------<---<----><--->-<><-------<><------>------<--<-<--
>-<-<->--------<-->-<<-<-<-><>-->---<<<---<<---<<----->>>---->--->>---<-


For Sudoshiki, however, I can remove a further 17 hints, leaving just 31:

Code: Select all
 9
 < . . . . . . . .
 . . . . > . . . .
 . . . . . . . . .
 . . . . . . . > .
 < . . . > . < . .
 < . . . . . . . .
 . > < . . . . . .
 . > . . . . . . .
 < . . < . < . . .
 > . . . > . < . .
 . . . . . . . . >
 < . . . . < . . .
 . . . . . < . . .
 . . < . < . . . .
 . . < . < . . > .
 > . . . < . > . <
 . . . . . < > . .
 . . . . . . . . .

Berthier format
 9
<----------->------------------><--->-<-<--------><------>------<--<-<--
>-<--->-------------<<---------->---<<<---<<---<<----->>----->--->----<-
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Sudoshiki (aka Sudoku Inequality) Generation, Properties

Postby champagne » Sat Dec 26, 2015 6:28 pm

Mathimagics wrote: Does anybody have access to the "full catalog" (5,472,730,538 classes) of Sudoku grids?

Or could anyone supply a sizeable sample thereof? Say a million or so?


I guess that several of us have such a file and, in my case, subject to a new check of that old code, a program to create that file.

The corresponding files are compressed using different algorithms, so you need at least a file and the restoration code.

Another issue, if you don't use the complete set of solutions is how is done the sample.

I red that several members, long ago, used an index to select randomly one solution grid. Digging in the forum, you have a small chance to find the relevant threads. I never worked in that direction.

If you don't find a better solution, we can continue through pm.
champagne
2017 Supporter
 
Posts: 5500
Joined: 02 August 2007
Location: France Brittany

Sudoshiki Generation, Properties

Postby Mathimagics » Sun Dec 27, 2015 11:14 am

Thanks champagne ...

On reflection, I think that for the purposes of my rudimentary analysis, my pseudo-random generator is perhaps good enough.

If I change my mind, I'll send you a PM and ask for help. 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015


Return to Sudoku variants