Minimal Futoshiki/Sudoshiki Puzzles

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: Minimal Futoshiki/Sudoshiki Puzzles

Postby Mathimagics » Sat Jun 18, 2022 5:57 pm

.
Some further observations on blue's two 17-clue Sudoshiki puzzles:

  • a standard Sudoku puzzle on the first solution grid would require at least 18 givens
  • a standard Sudoku puzzle on the second solution grid would require at least 19 givens!

Pretty amazing, really. 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1901
Joined: 27 May 2015
Location: Canberra

Re: Minimal Futoshiki/Sudoshiki Puzzles

Postby mith » Mon Jun 20, 2022 4:24 pm

ryokousha and I have been investigating minimal thermo sudoku for a while - very much like this "Sudoshiki" but not restricted to orthogonally adjacent cells.

The best known in terms of cell count is 21 cells: Cascade
This comes out to 18 "clues" in terms of the greater-than relationships (but with some of these diagonal). ryokousha has gotten down to 2 solutions with 20 cells - the fact that 17-clue Sudoshiki exist makes me believe 20 cells is likely possible, trading the orthogonal restriction for the connectedness restriction of only three thermos.

We also have a puzzle with 18 "2CT" (2-cell thermos) here: https://f-puzzles.com/?id=yjy4qfna - that is, 18 clues (some - in fact almost all - diagonal) such that none of them are chained (one pair does share a bulb - that is, the cell is less than two other cells, but there is no direct relation between those two cells). I am less inclined to think 17 2CT is possible, based on the ridiculous geometry tricks we needed to pull of even 18, but can't rule it out either. It's worth noting that this one can be reduced to 16 2CT and 1 given:
Hidden Text: Show
the shared bulb is a 1
mith
 
Posts: 859
Joined: 14 July 2020

Re: Minimal Futoshiki/Sudoshiki Puzzles

Postby Mathimagics » Mon Jun 20, 2022 5:58 pm

mith wrote:I am less inclined to think 17 2CT is possible, based on the ridiculous geometry tricks we needed to pull of even 18 ...

I'm inclined to agree ...

I do note that the first of blue's two 17-clue Sudoshikis has only 18 total cells in thermo terms (6 x 2CT, 2 x 3CT)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1901
Joined: 27 May 2015
Location: Canberra

Re: Minimal Futoshiki/Sudoshiki Puzzles

Postby mith » Mon Jun 20, 2022 11:09 pm

Mathimagics wrote:
mith wrote:I am less inclined to think 17 2CT is possible, based on the ridiculous geometry tricks we needed to pull of even 18 ...

I'm inclined to agree ...

I do note that the first of blue's two 17-clue Sudoshikis has only 18 total cells in thermo terms (6 x 2CT, 2 x 3CT)


I think you're forgetting the 9CT there. :)
mith
 
Posts: 859
Joined: 14 July 2020

Re: Minimal Futoshiki/Sudoshiki Puzzles

Postby Mathimagics » Tue Jun 21, 2022 7:26 am

Sorry about that! :roll:

For some reason my grid-rendering function has been infected with something (COVID?) ... it's playing "hide -the-chain" ! :?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1901
Joined: 27 May 2015
Location: Canberra

Re: Minimal Futoshiki/Sudoshiki Puzzles

Postby blue » Tue Jun 21, 2022 9:40 am

mith wrote:ryokousha and I have been investigating minimal thermo sudoku for a while - very much like this "Sudoshiki" but not restricted to orthogonally adjacent cells.

The best known in terms of cell count is 21 cells: Cascade
This comes out to 18 "clues" in terms of the greater-than relationships (but with some of these diagonal). ryokousha has gotten down to 2 solutions with 20 cells - the fact that 17-clue Sudoshiki exist makes me believe 20 cells is likely possible, trading the orthogonal restriction for the connectedness restriction of only three thermos.


Hi mith,

I looked through the 18c puzzles that I have, and found two "nice" (and 6 total) 21-cell puzzles.
They both have 3 isolated (bent up) "thermos" with lengths of 9,8 and 4.

I don't have a very good collection -- generated from only a few good "seeds".
With that, I wouldn't be surprised if a 20-cell Sudoshiki exists.

#1
Hidden Text: Show
Code: Select all
18c, 21 cells

.................................................................................
----<--------<--------<-----------<<-----<------<-----------------<-----
------>------>------>--<------->--------<--------<--------<<<-----------

+-----------+-----------+-----------+    +-----------+-----------+-----------+
| .   .   . | .   . < . | .   .   . |    | 4   5   9 | 6   1 < 2 | 7   3   8 |
|           |         ^ |           |    |           |         ^ |           |
| .   .   . | .   .   . < .   .   . |    | 6   7   1 | 5   8   3 < 4   2   9 |
|           |           | ^         |    |           |           | ^         |
| .   .   . | .   .   . | . < .   . |    | 8   2   3 | 4   7   9 | 5 < 6   1 |
+-----------+-----------+---- ^ ----+    +-----------+-----------+---- ^ ----+
| .   .   . | .   .   . | .   .   . |    | 9   8   2 | 3   4   1 | 6   7   5 |
|           |           |     ^     |    |           |           |     ^     |
| .   .   . < . < .   . | .   .   . |    | 3   1   6 < 7 < 9   5 | 2   8   4 |
|         v |           |     ^     |    |         v |           |     ^     |
| .   . < . | .   .   . | .   .   . |    | 7   4 < 5 | 2   6   8 | 1   9   3 |
+---- v ----+-----------+-----------+    +---- v ----+-----------+-----------+
| . < .   . | .   .   . | .   .   . |    | 2 < 3   8 | 1   5   6 | 9   4   7 |
| v         |           |           |    | v         |           |           |
| .   .   . | .   .   . | .   .   . |    | 1   6   4 | 9   3   7 | 8   5   2 |
|         ^ | v         |           |    |         ^ | v         |           |
| .   .   . < .   .   . | .   .   . |    | 5   9   7 < 8   2   4 | 3   1   6 |
+-----------+-----------+-----------+    +-----------+-----------+-----------+

459612738671583429823479561982341675316795284745268193238156947164937852597824316

#2
Hidden Text: Show
Code: Select all
18c, 21 cells

.................................................................................
---->-------->-------->---<----->---------------->-------->>------------
------------>>----<--->----<----------->>-------->-------->>------------

+-----------+-----------+-----------+    +-----------+-----------+-----------+
| .   .   . | .   . > . | .   .   . |    | 3   5   8 | 4   9 > 7 | 2   6   1 |
|           |         v |           |    |           |         v |           |
| .   .   . | .   .   . > .   .   . |    | 4   2   7 | 1   3   6 > 5   8   9 |
|           |           | v         |    |           |           | v         |
| .   .   . | .   .   . | . > .   . |    | 6   9   1 | 8   5   2 | 4 > 3   7 |
+-------- ^ +-----------+---- v ----+    +-------- ^ +-----------+---- v ----+
| .   .   . < .   .   . | .   .   . |    | 1   4   3 < 5   6   9 | 7   2   8 |
|           | ^         |     v     |    |           | ^         |     v     |
| . > .   . | .   .   . | .   .   . |    | 9 > 8   2 | 7   4   3 | 6   1   5 |
|     v     |           |           |    |     v     |           |           |
| .   .   . | .   .   . | .   .   . |    | 5   7   6 | 2   8   1 | 3   9   4 |
+---- v ----+-----------+-----------+    +---- v ----+-----------+-----------+
| .   . > . | .   .   . | .   .   . |    | 2   6 > 5 | 9   7   8 | 1   4   3 |
|         v |           |           |    |         v |           |           |
| .   .   . > . > .   . | .   .   . |    | 8   1   4 > 3 > 2   5 | 9   7   6 |
|           |     v     |           |    |           |     v     |           |
| .   .   . | .   .   . | .   .   . |    | 7   3   9 | 6   1   4 | 8   5   2 |
+-----------+-----------+-----------+    +-----------+-----------+-----------+

358497261427136589691852437143569728982743615576281394265978143814325976739614852

#3 (forked (>) chains)
Hidden Text: Show
Code: Select all
18c, 21 cells

.................................................................................
------------<<--------<-----------<--->--<-------<---------<-----<<-----
-------------->----->>--------->--------<--------<--------<<------------

+-----------+-----------+-----------+    +-----------+-----------+-----------+
| .   .   . | .   .   . | .   .   . |    | 4   7   2 | 5   6   1 | 8   3   9 |
|           |         ^ |           |    |           |         ^ |           |
| .   .   . | .   . < . < .   .   . |    | 5   6   8 | 9   2 < 3 < 4   1   7 |
|           |           | ^         |    |           |           | ^         |
| .   .   . | .   .   . | . < .   . |    | 3   9   1 | 4   7   8 | 5 < 6   2 |
+-----------+-----------+---- ^ ----+    +-----------+-----------+---- ^ ----+
| .   .   . | .   .   . | .   .   . |    | 1   8   9 | 3   5   6 | 2   7   4 |
|           |           |     ^     |    |           |           |     ^     |
| .   .   . < .   .   . | . > .   . |    | 2   5   6 < 7   1   4 | 9 > 8   3 |
|         v |           |           |    |         v |           |           |
| .   . < . | .   .   . | .   .   . |    | 7   3 < 4 | 2   8   9 | 6   5   1 |
+-------- v +-----------+-----------+    +-------- v +-----------+-----------+
| .   . < . | .   .   . | .   .   . |    | 8   2 < 3 | 1   4   5 | 7   9   6 |
|     v     |           |           |    |     v     |           |           |
| .   .   . | . < .   . | .   .   . |    | 6   1   7 | 8 < 9   2 | 3   4   5 |
|           | v         |           |    |           | v         |           |
| .   . < . < .   .   . | .   .   . |    | 9   4 < 5 < 6   3   7 | 1   2   8 |
+-----------+-----------+-----------+    +-----------+-----------+-----------+

472561839568923417391478562189356274256714983734289651823145796617892345945637128

Cheers,
Blue.
blue
 
Posts: 912
Joined: 11 March 2013

Re: Minimal Futoshiki/Sudoshiki Puzzles

Postby mith » Tue Jun 21, 2022 4:57 pm

Very nice finds :)
mith
 
Posts: 859
Joined: 14 July 2020

Re: Minimal Futoshiki/Sudoshiki Puzzles

Postby Mathimagics » Sun Jun 26, 2022 12:36 pm

mith wrote:We also have a puzzle with 18 "2CT" (2-cell thermos) here - that is, 18 clues (some - in fact almost all - diagonal) such that none of them are chained (one pair does share a bulb - that is, the cell is less than two other cells, but there is no direct relation between those two cells). I am less inclined to think 17 2CT is possible, based on the ridiculous geometry tricks we needed to pull of even 18, but can't rule it out either. It's worth noting that this one can be reduced to 16 2CT and 1 given ...


Perhaps that puzzle should be called a "16 x 2C + 3C", rather than "18 x 2C" puzzle. A "transitive" 3-cell set ("sharing a bulb") might not be as strong a constraint as a 3-cell chain, but it is stronger than a 2-cell chain.

So, before we look at whether 17 x 2C is possible or not, we perhaps need to ask whether in fact there is a (true) "18 x 2C"? :?:

By the way, I note that the "16 x 2C" without the given, has 1,140,537,139 solutions (according to sigh's ISS solver). I don't think that I have ever seen such a huge reduction in a solution space with 1 given.

Cheers
MM
User avatar
Mathimagics
2017 Supporter
 
Posts: 1901
Joined: 27 May 2015
Location: Canberra

Re: Minimal Futoshiki/Sudoshiki Puzzles

Postby mith » Mon Jun 27, 2022 7:23 pm

I agree it's not ideal, though I don't know that we can say definitively that a shared-bulb is always stronger than *two* 2CTs.

This particular puzzle was the result of a search on all morphs of the setup of bulbs and tips - b134679 have two orientations (whether the thermos follow positive or negative diagonals), plus whether the bulbs in b28 align or not - followed by adding one more 2CT in all possible ways. This was the only "18 2CT" found. Of course, that doesn't mean there's no way to do it without sharing a bulb... but the setup is *very* restrictive, and we really only came up with one other setup that even came close (yielding a 19 2CT - and it's not *that* different, it has the same structure in b134679 along with c45, just something different to force things with c6).

What I may try at some point is an exhaustive search on the 15 2CT "setup" shared by the two 19 2CT found + three more thermos in all possible locations, maybe we're missing some slightly different way to handle c6 that this will catch. Otherwise, we need something substantially different.
mith
 
Posts: 859
Joined: 14 July 2020

Re: Minimal Futoshiki/Sudoshiki Puzzles

Postby blue » Thu Jun 30, 2022 4:16 pm

blue wrote:Hi mith,

I looked through the 18c puzzles that I have, and found two "nice" (and 6 total) 21-cell puzzles.
They both have 3 isolated (bent up) "thermos" with lengths of 9,8 and 4.

I don't have a very good collection -- generated from only a few good "seeds".
With that, I wouldn't be surprised if a 20-cell Sudoshiki exists.

I've found a few 20-celll puzzle, now.
Here are two of the nicer ones.

#1 - 18c, one clean, and one forked '>' chain:
Hidden Text: Show
Code: Select all
.................................................................................
---------->>----->>------------->-------------->------>------>----------
----------<<-----<-------->>------------------>-------<------<-----<<---

+-----------+-----------+-----------+    +-----------+-----------+-----------+
| .   .   . | .   .   . | .   .   . |    | 1   3   8 | 9   5   7 | 4   2   6 |
|           |           |           |    |           |           |           |
| .   .   . > . > .   . | .   .   . |    | 7   9   4 > 2 > 1   6 | 3   8   5 |
|         ^ |           |           |    |         ^ |           |           |
| .   . > . > .   .   . | .   .   . |    | 2   6 > 5 > 4   8   3 | 1   9   7 |
+---- ^ ----+ v --------+-----------+    +---- ^ ----+ v --------+-----------+
| .   .   . | .   .   . | .   .   . |    | 4   7   2 | 3   9   5 | 8   6   1 |
|     ^     | v         |         ^ |    |     ^     | v         |         ^ |
| . > .   . | .   .   . | .   .   . |    | 9 > 8   3 | 1   6   4 | 5   7   2 |
|           |           |         ^ |    |           |           |         ^ |
| .   .   . | .   .   . | .   . > . |    | 5   1   6 | 8   7   2 | 9   4 > 3 |
+-----------+-----------+---- ^ ----+    +-----------+-----------+---- ^ ----+
| .   .   . | .   .   . | . > .   . |    | 3   4   1 | 7   2   9 | 6 > 5   8 |
|           |         v | ^         |    |           |         v | ^         |
| .   .   . | .   .   . > .   .   . |    | 6   2   9 | 5   3   8 > 7   1   4 |
|           |           |           |    |           |           |           |
| .   .   . | .   .   . | .   .   . |    | 8   5   7 | 6   4   1 | 2   3   9 |
+-----------+-----------+-----------+    +-----------+-----------+-----------+

138957426794216385265483197472395861983164572516872943341729658629538714857641239

#2 - 17c, 3 clean chains
Hidden Text: Show
Code: Select all
.................................................................................
---------->>----->------>------------------>--->------>------>----------
-->-------<------<-----------<--<------------->-------<------<------<---

+-----------+-----------+-----------+    +-----------+-----------+-----------+
| .   .   . | .   .   . | .   .   . |    | 2   3   7 | 9   1   5 | 4   8   6 |
|           |     ^     |           |    |           |     ^     |           |
| .   .   . > . > .   . | .   .   . |    | 1   8   4 > 3 > 2   6 | 5   9   7 |
|         ^ |           |           |    |         ^ |           |           |
| .   . > . | .   .   . | .   .   . |    | 9   6 > 5 | 8   7   4 | 2   1   3 |
+ v - ^ ----+-----------+-----------+    + v - ^ ----+-----------+-----------+
| . > .   . | .   .   . | .   .   . |    | 8 > 7   2 | 4   9   1 | 3   6   5 |
|           |           |           |    |           |           |           |
| .   .   . | .   .   . | .   .   . |    | 5   4   6 | 2   8   3 | 9   7   1 |
|           |           |         ^ |    |           |           |         ^ |
| .   .   . | . > .   . | .   . > . |    | 3   1   9 | 6 > 5   7 | 8   4 > 2 |
+-----------+ ^ --------+---- ^ ----+    +-----------+ ^ --------+---- ^ ----+
| .   .   . | .   .   . | . > .   . |    | 4   2   1 | 7   3   9 | 6 > 5   8 |
|           |         v | ^         |    |           |         v | ^         |
| .   .   . | .   .   . > .   .   . |    | 6   5   3 | 1   4   8 > 7   2   9 |
|           |           |           |    |           |           |           |
| .   .   . | .   .   . | .   .   . |    | 7   9   8 | 5   6   2 | 1   3   4 |
+-----------+-----------+-----------+    +-----------+-----------+-----------+

237915486184326597965874213872491365546283971319657842421739658653148729798562134
blue
 
Posts: 912
Joined: 11 March 2013

Re: Minimal Futoshiki/Sudoshiki Puzzles

Postby Mathimagics » Thu Jun 30, 2022 5:59 pm

Confirmed both of these examples ...

Great work, blue! 8-)

And all this with purely orthogonal chains (ie without resorting to diagonal adjacency) ... :)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1901
Joined: 27 May 2015
Location: Canberra

Re: Minimal Futoshiki/Sudoshiki Puzzles

Postby mith » Thu Jun 30, 2022 8:21 pm

Beautiful, nicely done blue :)

The 17c has a cool solve path, as well.
mith
 
Posts: 859
Joined: 14 July 2020

Re: Minimal Futoshiki/Sudoshiki Puzzles

Postby coloin » Thu Jun 30, 2022 8:28 pm

That 17c is pretty good the way it propagates the solution
eg
Code: Select all
+---+---+---+
|...|.1.|...|
|..4|32.|...|
|965|...|...|
+---+---+---+
|87.|...|...|
|...|...|..1|
|...|...|.32|
+---+---+---+
|...|..8|54.|
|...|..7|6..|
|...|...|...|
+---+---+---+  has 0 solutions - a 1@r5c9 is forbidden somehow



maybe this one is a good seed ?
Code: Select all
+---+---+---+
|...|...|.87|
|3..|...|.9.|
|5..|4..|...|
+---+---+---+
|..6|5..|...|
|.87|...|...|
|.9.|...|...|
+---+---+---+
|...|.98|...|
|...|.7.|32.|
|...|..1|4..|
+---+---+---+  17C with 11 clues in the diagonal B348 -  with [optional] 2 at r8c8
coloin
 
Posts: 2219
Joined: 05 May 2005
Location: Devon

Re: Minimal Futoshiki/Sudoshiki Puzzles

Postby mith » Thu Jun 30, 2022 10:50 pm

ryokousha is using the 17c as a seed, and has 19 thermo cells down to 10 solutions already with diagonals allowed. We'll keep you posted :)
mith
 
Posts: 859
Joined: 14 July 2020

Re: Minimal Futoshiki/Sudoshiki Puzzles

Postby mith » Thu Jun 30, 2022 11:16 pm

I got it down to 3 solutions, but not making any good progress on modifying it from here.

We do now have several examples with a pair of 9CTs plus one 2CT. For example: https://f-puzzles.com/?id=258rmyq5 (remove the r8c5 bulb for the 3 solution 19 cell)
mith
 
Posts: 859
Joined: 14 July 2020

PreviousNext

Return to Sudoku variants