Minimal Futoshiki/Sudoshiki Puzzles

For fans of Killer Sudoku, Samurai Sudoku and other variants

Minimal Futoshiki/Sudoshiki Puzzles

Postby Mathimagics » Wed Jan 20, 2016 1:56 pm

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Minimal Futoshiki/Sudoshiki Puzzles

Postby Mathimagics » Wed Jan 20, 2016 2:00 pm

Here is a case of SI(9, 0, 27):

SImin9_R27.jpg
Minimal Sudoshiki, N = 9, G = 0, R = 27
SImin9_R27.jpg (21.49 KiB) Viewed 391 times


Solution:
Hidden Text: Show
456289173
318476259
729531468
934712586
581643792
672958341
243867915
165394827
897125634
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Minimal Futoshiki (N = 7)

Postby Mathimagics » Mon Jan 25, 2016 8:21 am

The smallest R for which an FP(7, 0, R) has been found so far is 15. Here is one example:

Fmin7_G0_R15.jpg
Example #7a: FP(N=7, G=0, R=15)
Fmin7_G0_R15.jpg (13.49 KiB) Viewed 366 times

Solution:
Hidden Text: Show
7134256
4325761
6413572
1547623
2761345
3256417
5672134
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Minimal Futoshiki (N=7, G>0)

Postby Mathimagics » Mon Jan 25, 2016 8:23 am

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:
Fmin7_G4_R11.jpg
Example #7b: FP(N=7, G=4, R=11)
Fmin7_G4_R11.jpg (14.16 KiB) Viewed 366 times

Solution:
Hidden Text: Show
6135247
1467352
5713624
2351476
7246135
4672513
3524761
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

jigSu-shiki ?

Postby Pat » Mon Jan 25, 2016 1:15 pm

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)

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

but a vast task,
to review all possible box-shapes for jigsaw——
User avatar
Pat
 
Posts: 3449
Joined: 18 July 2005

Re: jigSu-shiki ?

Postby Mathimagics » Mon Jan 25, 2016 5:27 pm

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).
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Minimal Futoshiki (N=7, 14 hints)

Postby Mathimagics » Thu Jan 28, 2016 8:54 am

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:

Fmin7_G4_R10.jpg
N = 7, G = 4, R = 10
Fmin7_G4_R10.jpg (14.1 KiB) Viewed 347 times

Solution:
Hidden Text: Show
7654312
1423576
3542761
4165237
5371624
6217453
2736145
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Minimal Futoshiki (N = 7, 12 Hints)

Postby Mathimagics » Thu Jan 28, 2016 9:10 am

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:

Fmin7_G8_R4.jpg
N = 7, G = 8, R = 4
Fmin7_G8_R4.jpg (14.23 KiB) Viewed 347 times


Solution:
Hidden Text: Show
7364251
3642517
6425173
4251736
2517364
5173642
1736425
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Minimal Futoshiki/Sudoshiki Puzzles

Postby blue » Thu Jan 28, 2016 8:37 pm

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: 573
Joined: 11 March 2013

Re: Minimal Futoshiki/Sudoshiki Puzzles

Postby Mathimagics » Fri Jan 29, 2016 1:47 pm

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
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015


Return to Sudoku variants