## 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: 1901
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 1490 times

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

Mathimagics
2017 Supporter

Posts: 1901
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 1465 times

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

Mathimagics
2017 Supporter

Posts: 1901
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 1465 times

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

Mathimagics
2017 Supporter

Posts: 1901
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: 3968
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: 1901
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 focused one.

The largest trade discovered so far is 10 - ie: we get a FP(7, 4, 10) puzzle. One example is given below:

[ EDIT ] this image deleted 23/10/2021

Solution:
Hidden Text: Show
7654312
1423576
3542761
4165237
5371624
6217453
2736145
Last edited by Mathimagics on Sat Oct 23, 2021 2:24 am, edited 2 times in total.

Mathimagics
2017 Supporter

Posts: 1901
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 1446 times

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

Mathimagics
2017 Supporter

Posts: 1901
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: 909
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: 1901
Joined: 27 May 2015
Location: Canberra

### Re: Minimal Futoshiki/Sudoshiki Puzzles

.
Update (2 June 2022)

Following some recent postings related to this topic, I have finally built a SAT solver for Sudoshiki (aka Sudoku Greater Than, Sudoku Inequality), and on checking the 19R example given by blue above, I find that puzzle to be invalid (multiple solutions):

Code: Select all
`Blue: 9x9 - 19 clues------------<-----<<->---<------------------->-----<<----------->-----<->>-----------<---->--------<<<--->------------------------<-------------Base Clause count = 11988Clause count = 12672, Ineqs = 19Solving GTNS = 2 (maybe more)792413865165829734843675129237961458659384217418257693524138976381796542976542381792413865165829734843675129237961458659384217418257693524138976386792541971546382`

I have verified that both of these solutions reported by the solver are valid.

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### Re: Minimal Futoshiki/Sudoshiki Puzzles

Code: Select all
`Blue: 9x9 - 19 clues------------<-----<<->---<------------------->-----<<----------->-----<->>-----------<---->--------<<<--->------------------------<-------------`

Has an single solution confirmed by logic < SE 10 and SAT solvers:
Code: Select all
`9 4 5 8 1 3 7 2 68 2 1 9 6 7 4 5 36 7 3 4 5 2 1 8 94 1 2 3 7 8 6 9 53 9 6 5 2 1 8 4 77 5 8 6 9 4 3 1 22 6 4 7 8 9 5 3 11 8 7 2 3 5 9 6 45 3 9 1 4 6 2 7 8`

You could have pasted this in my solver (in newer versions empty grid not required):
Code: Select all
`.................................................................................------------<-----<<->---<------------------->-----<<----------->-----<->>-----------<---->--------<<<--->------------------------<-------------`

After running Sat4J or MiniSatExe you can get the cnf which in this case is 11215 clauses.

Totaling 6 vertical conflicts.
creint

Posts: 340
Joined: 20 January 2018

### Re: Minimal Futoshiki/Sudoshiki Puzzles

.
Hi creint!

Thanks for that info, that helped me identify the problem immediately - we are using different puzzle string forms.

I have always used left-to-right, row by row format for both the horizontal and vertical clue strings. That makes it easier (for me, at least) to build strings from puzzle images.

You, and blue have both used top-down, column by column, for the vertical clue string.

So for blue's 19 clue spec:
Code: Select all
`------------<-----<<->---<------------------->-----<<----------->-----<->>-----------<---->--------<<<--->------------------------<-------------`

To use in my solver & image rendering I need to convert that to:
Code: Select all
`------------<-----<<->---<------------------->-----<<----------->-----<->-------->--->------>----<----<--------<------<-<-----------------------`

And hey, presto, I now find the unique solution that you identified.

Cheers
MM

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### Re: Minimal Futoshiki/Sudoshiki Puzzles

I have finally found a painless way to "publish" images so I no longer have to rely on attachments.

So here is blue's record-setting 19-clue Sudoshiki, with its solution:

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### 17 Clue Sudoshiki ! (G=0)

Hi guys,

Will one or both of you please confirm that this one is valid too ?

Code: Select all
`17-clue 9x9 Sudoshiki.................................................................................----------<------<--------->---->---------------->---<---->>-->--------------------->>----<--->->-------------->----------->----->--------------+-----------+-----------+-----------+| .   .   . | .   .   . | .   .   . ||           | v         |           || .   .   . < .   .   . | .   .   . ||           |           |     v     || .   . < . | .   .   . | .   .   . |+-------- ^ +-----------+-----------+| .   .   . | . > .   . | .   .   . ||           |           | v         || . > .   . | .   .   . | .   .   . ||     v     |           |           || .   .   . | .   .   . | .   .   . |+---- v ----+-----------+-----------+| .   . > . | .   .   . < .   .   . ||         v |           |           || .   .   . > . > .   . | . > .   . ||           |     v     |           || .   .   . | .   .   . | .   .   . |+-----------+-----------+-----------+`

Solution:
Hidden Text: Show
Code: Select all
`158964327497832561623175849346751298982643175571298634265487913814329756739516482+-----------+-----------+-----------+| 1   5   8 | 9   6   4 | 3   2   7 ||           | v         |           || 4   9   7 < 8   3   2 | 5   6   1 ||           |           |     v     || 6   2 < 3 | 1   7   5 | 8   4   9 |+-------- ^ +-----------+-----------+| 3   4   6 | 7 > 5   1 | 2   9   8 ||           |           | v         || 9 > 8   2 | 6   4   3 | 1   7   5 ||     v     |           |           || 5   7   1 | 2   9   8 | 6   3   4 |+---- v ----+-----------+-----------+| 2   6 > 5 | 4   8   7 < 9   1   3 ||         v |           |           || 8   1   4 > 3 > 2   9 | 7 > 5   6 ||           |     v     |           || 7   3   9 | 5   1   6 | 4   8   2 |+-----------+-----------+-----------+`

Cheers,
Blue.

Edit: Fixed the solution. It was for a different puzzle !
Thanks Colin.
Last edited by blue on Fri Jun 17, 2022 7:15 pm, edited 1 time in total.
blue

Posts: 909
Joined: 11 March 2013

Next