The New Sudoku Players' Forum

[Mathimagics]

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

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.

[Mathimagics]

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!

[denis_berthier]

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

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]

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!

yes, good idea

[Mathimagics]

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!

[Mathimagics]

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!

[denis_berthier]

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
)

[Mathimagics]

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.

[denis_berthier]

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

[Mathimagics]

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.

[Mathimagics]

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?

[denis_berthier]

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

[Mathimagics]

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.

[denis_berthier]

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.

[blue]

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.