The New Sudoku Players' Forum

[Mathimagics]

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?

[Mathimagics]

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


[Mathimagics]

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


[champagne]

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.

[Mathimagics]

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.