Futoshiki Generation, properties

For fans of Killer Sudoku, Samurai Sudoku and other variants

Ok let's start again!

Postby Mathimagics » Tue Jun 16, 2015 3:26 pm

Sigh! Your format seems to be listing vertical hint information column by column, not row by row! 8-)

It's my fault, I simply assumed the interpretation was obvious.

For the record, I list both sets of hints by row, with the hint at (R, C) specifying the relationship (R, C) <> (R, C+1) for horizontal entries, or (R, C) <> (R+1, C) for vertical.

I will have to change my specs for you and resubmit.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Futoshiki properties

Postby Mathimagics » Tue Jun 16, 2015 3:29 pm

Then perhaps we can get Jason to rewind this thread back to the point where I first gave you the examples, and we'll start again! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Ok let's start again!

Postby denis_berthier » Tue Jun 16, 2015 3:35 pm

Mathimagics wrote:Sigh! Your format seems to be listing vertical hint information column by column, not row by row! 8-)

For the same copying purposes as in Kakuro, I adopted a similar order.
I hope we didn't have the same misunderstanding when we talked about Kakuro.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Futoshiki properties

Postby denis_berthier » Tue Jun 16, 2015 3:35 pm

Mathimagics wrote:Then perhaps we can get Jason to rewind this thread back to the point where I first gave you the examples, and we'll start again! 8-)

yes, good idea
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Ok let's start again!

Postby Mathimagics » Tue Jun 16, 2015 3:44 pm

denis_berthier wrote:For the same copying purposes as in Kakuro, I adopted a similar order.
I hope we didn't have the same misunderstanding when we talked about Kakuro.


Oh, dear me! :shock:
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Futoshiki Generation, properties

Postby Mathimagics » Tue Jun 16, 2015 3:46 pm

This is quite funny! I assumed the row-by-row format because it worked for Kakuro!

The grids we were using were insensitive to such a transformation, having reflective symmetry! Not so for Futoshiki! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Futoshiki Generation, properties

Postby denis_berthier » Tue Jun 16, 2015 4:14 pm

Some explanation of my (Futoshiki) format.
As I said for Kakuro, it's purely contingent to the fact that I had to copy manually lots of puzzles.
I never decided about a format. It just happened that I copied them that way (one row at a time, one column at a time) because it was easier and less error prone.
Without such a context, there must be better formats to represent the givens.

For H4062
Copy of lines: (top to bottom)
->>>-><<
<---<---
--<-<--<
-<->->--
--------
<->-->--
-->-<<--
<->-<->>
-<------
compacted into:
->>>-><<<---<-----<-<--<-<->->----------<->-->---->-<<--<->-<->>-<------


Copy of columns (left to right)
--<<--<>
-<----<-
-<----->
->----->
--------
--<-->-<
>-----<<
>--<-<<-
<-----<>
compacted into:
--<<--<>-<----<--<----->->----->----------<-->-<>-----<<>--<-<<-<-----<>


Then I used the compact forms to feed the solve function:
(solve 9
"................................................................................." ; givens, if any
"->>>-><<<---<-----<-<--<-<->->----------<->-->---->-<<--<->-<->>-<------" ; horiz data
"--<<--<>-<----<--<----->->----->----------<-->-<>-----<<>--<-<<-<-----<>" ; verti data
)
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

New versions reduced form Futoshiki

Postby Mathimagics » Tue Jun 16, 2015 4:17 pm

Ok, let's try again!

This is puzzle #1 in the original batch, reduced form (with a maximal chain, ie 9 ), my DFS = 4623
Code: Select all
9
--------------->->---<<---<---<<-----------<---->----->--->-----<----<<-
------<------>----->>------<<<<-<<-->-<-----<-<----->>------><->->-<<<->


This is puzzle #1 in the original batch, reduced form (with max chain len 6), my DFS = 250,000
Code: Select all
9
--------------->->--<<----<---<<------<------<-->->-<<>--->>---------<<-
---<>-->--<------>->>------<-<<-<--<>-<-----<-->---->>---<---<->->-<<<->


This is puzzle #2, reduced form (maximal chains), my DFS = 107,000
Code: Select all
9
>>>>->->-->->---->-----<--<-----<<--<>------>>><----->>--<->->---->-->-<
-<<----><-<-->>>-<----------->-->----<<-<----------<---<----<-<----->---

I suspect these might not be that hard, since my DFS obviously has problems.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: New versions reduced form Futoshiki

Postby denis_berthier » Tue Jun 16, 2015 4:37 pm

Code: Select all
This is puzzle #1 in the original batch, reduced form (with a maximal chain, ie 9 ), my DFS = 4623
9
--------------->->---<<---<---<<-----------<---->----->--->-----<----<<-
------<------>----->>------<<<<-<<-->-<-----<-<----->>------><->->-<<<->

W = 5


Code: Select all
This is puzzle #1 in the original batch, reduced form (with max chain len 6), my DFS = 250,000
9
--------------->->--<<----<---<<------<------<-->->-<<>--->>---------<<-
---<>-->--<------>->>------<-<<-<--<>-<-----<-->---->>---<---<->->-<<<->

W = infinity


Code: Select all
This is puzzle #2, reduced form (maximal chains), my DFS = 107,000
9
>>>>->->-->->---->-----<--<-----<<--<>------>>><----->>--<->->---->-->-<
-<<----><-<-->>>-<----------->-->----<<-<----------<---<----<-<----->---

W = 10


There now seems to be some consistency between our ratings - but it may be mere chance
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Futoshiki properties

Postby Mathimagics » Tue Jun 16, 2015 4:50 pm

No, I think we're in sync. My DFS ratings are skewed, but relatively they still reflect easier v harder.

My DFS ratings are skewed by the fact that my choice of next cell to visit was driven by an assumption that the puzzles were specified in a maximal way, which was what we started with.

The problem, now that I have reduced forms is that this is potentially the worst way to go! Many of the chains are totally disconnected so that in a large grid pursuing them mindlessly invariably means a poor selection.

You'll notice that H4062 has clearly separate sub-sections at the bottom, both separated from the top half. It was just a classic worst-case scenario for my Solver.

But I know how to fix it.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Name that inference type

Postby Mathimagics » Wed Jun 17, 2015 5:16 pm

Consider this "value v can go where" bit table for a Latin Square:
Code: Select all
 0  0  0  0  0  0  0  0  0
 0  0  0  0  1  1  0  0  1
 1  0  0  0  0  1  0  0  0
 0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0
 1  0  0  0  0  1  0  0  0
 1  0  0  0  0  0  0  0  0
 0  0  0  0  1  0  0  0  1
 0  0  0  0  0  0  0  0  0

Clearly we can infer that (7, 1) can't be v, nor can (2, 6), so both those bits can be cleared.

But what is this case called in the parlance of the genre? It's not "naked pair" or "hidden pair", but what?
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Name that inference type

Postby denis_berthier » Wed Jun 17, 2015 5:50 pm

Mathimagics wrote:Consider this "value v can go where" bit table for a Latin Square:
Code: Select all
 0  0  0  0  0  0  0  0  0
 0  0  0  0  1  1  0  0  1
 1  0  0  0  0  1  0  0  0
 0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0
 1  0  0  0  0  1  0  0  0
 1  0  0  0  0  0  0  0  0
 0  0  0  0  1  0  0  0  1
 0  0  0  0  0  0  0  0  0

Clearly we can infer that (7, 1) can't be v, nor can (2, 6), so both those bits can be cleared.
But what is this case called in the parlance of the genre? It's not "naked pair" or "hidden pair", but what?


X-Wing:
In rows 3,6 v can only be in columns 3, 6
conclusion: in columns 3, 6 v can only be in rows 3,6 ==> (2, 6) ≠ v

Jellyfish:
in rows 2, 3, 6, 8, v can only be in columns 1, 5, 6, 9
conclusion: in columns 1, 5, 6, 9, v can only be in rows 2, 3, 6, 8 ==> (7, 1) ≠ v
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Futoshiki Fishing

Postby Mathimagics » Wed Jun 17, 2015 6:10 pm

Thanks! I'd never have guessed that.

I've got my DFS solver stabilised now, and am in the process of fine tuning it.

That "very hard" reduced form I gave you, with max chain length 6 (W = infinity by your rating) is proving to be tough. I have it down to under a million node visits, which takes about 90s.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Futoshiki Fishing

Postby denis_berthier » Wed Jun 17, 2015 6:21 pm

Mathimagics wrote:Thanks! I'd never have guessed that.

I don't know the origin of the names.
Personally, I call them Super-Hidden Subsets, for symmetry reasons I explain in chapter 8.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Name that inference type

Postby blue » Wed Jun 17, 2015 6:38 pm

Mathimagics wrote:Consider this "value v can go where" bit table for a Latin Square:
Code: Select all
 0  0  0  0  0  0  0  0  0
 0  0  0  0  1  1  0  0  1
 1  0  0  0  0  1  0  0  0
 0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0
 1  0  0  0  0  1  0  0  0
 1  0  0  0  0  0  0  0  0
 0  0  0  0  1  0  0  0  1
 0  0  0  0  0  0  0  0  0

Clearly we can infer that (7, 1) can't be v, nor can (2, 6), so both those bits can be cleared.

But what is this case called in the parlance of the genre? It's not "naked pair" or "hidden pair", but what?

For a "flip" answer: The puzzle has (at least) 5 rows needing a 'v', but only 4 columns that can take one. It has no solutions, and so any candidate can be eliminated :)

In more detail, if the 4 rows showing all 0's, already contain a 'v', then presumably 4 such columns, also contain a 'v', and one column has been left with no place to put a 'v'. Conclusion: It's time to backtrack.
blue
 
Posts: 573
Joined: 11 March 2013

PreviousNext

Return to Sudoku variants