## Minimal Futoshiki/Sudoshiki Puzzles

For fans of Killer Sudoku, Samurai Sudoku and other variants

### Minimal Futoshiki/Sudoshiki Puzzles

Surprisingly there appears to be little information available on this topic - for a given grid size N, what is the minimum number of clues needed to fix a unique solution to a Futoshiki puzzle, or a Sudoshiki puzzle?

A Sudoshiki puzzle here is assumed to be a Futoshiki puzzle on a standard Sudoku grid (eg: 9 3x3 regions, 8 2x4 regions, 6 2x3 regions, etc).

Since clues can be in two forms - givens and relationships - a puzzle has 3 basic attributes:
• N - the grid size
• G - the number of givens
• R - the number of relationship clues (<, >)

A puzzle, FP(N, G, R) or SI(N, G, R) (SI for Sudoshiki, aka Sudoku Inequality) is minimal if removal of any given or relationship causes the puzzle to have multiple solutions.

My primary interest is in puzzles with G = 0, but I will in time take a look at puzzles with G > 0.

Searching for minimal cases is a time-consuming business, so my results for N > 5 are by no means definitive, but here they are:

Code: Select all
`Minimal Futoshiki/Sudoshiki (no givens)  N      R(FP)    R(SI)-----------------------    4        4        3  5        6  6        9        8  7       15  8       24       19  9       36       27`

If anybody is aware of any examples of smaller R I'd be glad to hear from you, of course!
Last edited by Mathimagics on Wed Jan 20, 2016 7:57 pm, edited 1 time in total. Mathimagics
2017 Supporter

Posts: 1486
Joined: 27 May 2015
Location: Canberra

### Minimal Futoshiki/Sudoshiki Puzzles

Here is a case of SI(9, 0, 27): Minimal Sudoshiki, N = 9, G = 0, R = 27
SImin9_R27.jpg (21.49 KiB) Viewed 915 times

Solution:
Hidden Text: Show
456289173
318476259
729531468
934712586
581643792
672958341
243867915
165394827
897125634 Mathimagics
2017 Supporter

Posts: 1486
Joined: 27 May 2015
Location: Canberra

### Minimal Futoshiki (N = 7)

The smallest R for which an FP(7, 0, R) has been found so far is 15. Here is one example: Example #7a: FP(N=7, G=0, R=15)
Fmin7_G0_R15.jpg (13.49 KiB) Viewed 890 times

Solution:
Hidden Text: Show
7134256
4325761
6413572
1547623
2761345
3256417
5672134 Mathimagics
2017 Supporter

Posts: 1486
Joined: 27 May 2015
Location: Canberra

### Minimal Futoshiki (N=7, G>0)

Now consider the following table, where we consider min R for various G:

Code: Select all
`Minimal R for N = 7 --------------    G     R--------------    0    15  1    14  2    13    3    12  4    11   (example given below)  5    10  6     9`

These are the minimal R cases found so far for given G, after a week of 4-core searching. We might be forgiven for thinking that the total hints, H = G + R, is always at least 15, however this is demonstrably false.

Consider cases at the other extreme, ie. with R = 0. These correspond to standard Latin Square/Sudoku puzzles, and hence minimal G corresponds to the size of the smallest critical set for the given solution. For N = 7 we know that G can be as low as 12.

Also, for standard Sudoku we know that G can be as low as 17, whereas the smallest R we have found so far, (ie: for G = 0), is 27.

Here is an example of an FP(7, 4, 11) puzzle: Example #7b: FP(N=7, G=4, R=11)
Fmin7_G4_R11.jpg (14.16 KiB) Viewed 890 times

Solution:
Hidden Text: Show
6135247
1467352
5713624
2351476
7246135
4672513
3524761 Mathimagics
2017 Supporter

Posts: 1486
Joined: 27 May 2015
Location: Canberra

### jigSu-shiki ?

Mathimagics wrote:

A Sudoshiki puzzle here is assumed to be a Futoshiki puzzle on a standard Sudoku grid (eg: 9 3x3 regions, 8 2x4 regions, 6 2x3 regions, etc)

or include jigSu-shiki ?
(Futoshiki in a jigsaw-SuDoku)

allows all puzzle-sizes (e.g. 7-squared)

to review all possible box-shapes for jigsaw—— Pat

Posts: 3880
Joined: 18 July 2005

### Re: jigSu-shiki ?

Pat wrote:or include jigSu-shiki ? (Futoshiki in a jigsaw-SuDoku)

SudokuXtra refers to these as "Jigsaw Inequality" puzzles. I'll call them JI for short, to go with FP and SI.

Pat wrote:but a vast task, to review all possible box-shapes for jigsaw——

Indeed! By my count, for N = 7, there are 158,747,952 different (contiguous) jigsaw layouts to consider.

We do know that JI(N, N-1, 0) puzzles exist, ie. with G = N - 1 and R = 0. And conversely, JI(N, 0, N-1) puzzles exist, also (although not very interesting ones). Mathimagics
2017 Supporter

Posts: 1486
Joined: 27 May 2015
Location: Canberra

### Minimal Futoshiki (N=7, 14 hints)

I have found cases of 14-hint puzzles for N = 7.

These were found by looking at FP(7, 14, 0) instances, ie: latin squares of order 7 with MCS = 14 (Minimal Critical Set size).

I then used a GR-trade process - this involves trying to replace givens with relationships, ie {-G, +R}. This is still a slow process, since all symbol-permutations need to be considered, but it is at least a focussed one.

The largest trade discovered so far is 10 - ie: we get a FP(7, 4, 10) puzzle. One example is given below: N = 7, G = 4, R = 10
Fmin7_G4_R10.jpg (14.1 KiB) Viewed 871 times

Solution:
Hidden Text: Show
7654312
1423576
3542761
4165237
5371624
6217453
2736145 Mathimagics
2017 Supporter

Posts: 1486
Joined: 27 May 2015
Location: Canberra

### Minimal Futoshiki (N = 7, 12 Hints)

For N = 7, we know that the smallest known MCS is 12, so theoretically we have 12-hint puzzles possible.

These cases are less productive. The underlying latin square has one basic form, ie. each row/col is simply a rotation of the first (the basic form is the back-circulant LS). I did find one trade of size 4, which gives a G=8, R=4 puzzle: N = 7, G = 8, R = 4
Fmin7_G8_R4.jpg (14.23 KiB) Viewed 871 times

Solution:
Hidden Text: Show
7364251
3642517
6425173
4251736
2517364
5173642
1736425 Mathimagics
2017 Supporter

Posts: 1486
Joined: 27 May 2015
Location: Canberra

### Re: Minimal Futoshiki/Sudoshiki Puzzles

Here are some more G=0, "low R" puzzles -- no idea if the R's are the minimums for G=0.
They're in the format that you and Denis Berthier developed.
For 6x6 and 8x8 Sudoshiki, the layout is with boxes that are 2 cells tall by 3 or 4 cells wide.

Code: Select all
`Futoshiki:7x7 - 12 clues---<---------------------<-<>----<----------->---------->>--------->>>------>-------8x8 - 18 clues------>--------<--->--------------><--<---------------------->>-->>>----------<----------<---<<---<<------<-----9x9 - 24 clues-----------<<-----<---<<---<----<-------<------->--------->-->>-->-<--------->-------->>-->----<->--<----------------->--->-------------->------Sudoshiki:6x6 - 7 clues--------<------>---------->>---------->>------>-------------8x8 - 15 clues----------<----------<--->>------<---------------->---->--<--------<----->---->--------------------->>------>>--9x9 - 19 clues------------<-----<<->---<------------------->-----<<----------->-----<->>-----------<---->--------<<<--->------------------------<-------------`
blue

Posts: 894
Joined: 11 March 2013

### Re: Minimal Futoshiki/Sudoshiki Puzzles

Great work, blue!

My search technique clearly leaves something to be desired! How did you find these?

Updated table:
Code: Select all
`Minimal Relationships (no givens)      Futoshiki Sudoshiki   N        R        R  -----------------------    4        4        3  5        6  6        9        7  7       12  8       18       15  9       24       19` Mathimagics
2017 Supporter

Posts: 1486
Joined: 27 May 2015
Location: Canberra