Them & Us

Everything about Sudoku that doesn't fit in one of the other sections

Them & Us

Postby Red Ed » Sun May 06, 2007 10:13 am

Have you seen the discussions in the Eureka! topic at the Telegraph sudoku site? Full of bright people nit-picking each others' grammar and (occasionally) making significant contributions to the world of sudoku. I thought we might like to steer them onto some useful work for a change. Patronising? Oh yes. Bring on the nanny state.

I had the following in mind. Between us, we come up with five (say) long-standing problems that we'd like to have resolved. I don't mean the really hard stuff like proving there's no 16, but instead something more open to discussion like coming up with a good difficulty rating or a good way of resolving forcing nets. The ideas are then posted into five (say) separate threads in the Eureka topic and the good denizens of that forum set to work on it.

Why pick that forum instead of this to post those challenge problems? Well, a few reasons. One is that whilst I enjoy reading that forum, I get sick of trawling through in-fighting which, in my opinion, comes from lack of clarity about the problem in hand as much as anything else. Another reason is that I think that the other forum would attack the topics with more vigour than us because, with their relatively narrow experience (IMO), much of what we challenge them with might be new & exciting (and we could do with a fresh look at some problems). Finally, there's the trivial thing that the Eureka topic doesn't have too many threads on it and new ones always stay together, grouped by the date posted -- so they wouldn't be "lost" as might happen here.

So ... anything worth challenging them with? I'll restate the two mentioned earlier, though more than happy to see better ones suggested:
  • Challenge: determine a good difficulty-rating system for puzzles.
  • Challenge: find a good algorithm for discovering and solving forcing nets. (Confession: I've no idea if this is even a sensible thing to ask for, not being much of a solver myself)
Hoping to see your ideas chipped-in here ... feel free to flame me, too, if you want to hone your etiquette for the other forum:)
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Mike Barker » Sun May 06, 2007 12:55 pm

Ed, you are so right on:D .

One challenge I've tried to get them to take up, but have only seen a little progress recently, is to evaluate why GEM eliminations occur. Understanding them might lead to something new or possibly show the relationship between GEM and forcing chains. Maybe GEM is the way to formalize forcing chains.

Another challenge I've often considered is understanding characteristics of unreachable backdoors and seeking ways to access them. By unreachable I'm refering to the fact that all puzzles apparently have backdoors, but in the hard ones there is no way to make eliminations in them directly.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Red Ed » Sun May 06, 2007 1:36 pm

Great, I hoped someone would take the bait! Good suggestions.

Whilst apparently criticising the Other Forum in my previous post, I also recognise that this one isn't always great when it comes to looking at things in detail. Our outlook is broad and sometimes a little superficial; theirs is fairly narrow but often quite deep. I'm just hoping for a happy middle ground. And to prove that we're better than they are:) - just kidding.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Havard » Sun May 06, 2007 2:27 pm

Will there be secret handshakes? Count me in!:)

My challenge would be:
Find an algorithm that fixes all possible symmetrical constraints on a given template w.l.o.g.

No wait, that's my challenge...:D

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Re: Them & Us

Postby gsf » Wed May 09, 2007 5:24 am

Red Ed wrote:
  • Challenge: determine a good difficulty-rating system for puzzles.
  • Challenge: find a good algorithm for discovering and solving forcing nets. (Confession: I've no idea if this is even a sensible thing to ask for, not being much of a solver myself)

both of these are just about rolled into one in the (work in progress, always awaiting commentary) -q1 rating in my solver,
which was prodded on by the eruption of hard puzzles last month

its based on propositions (probably equivalent to forcing nets),
addresses isomorphic puzzle permutations (although slighly imperfect in implementation),
rates by counting the complexity of a search of all possibilities, with the (time saving) restriction of checking the most constrained choices first,
and is tractable in implementation and use (as opposed to SE)

and my take on cannibalistic forums
life is too short to suffer the aggravation
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: Them & Us

Postby Red Ed » Wed May 09, 2007 6:14 am

gsf wrote:and my take on cannibalistic forums
life is too short to suffer the aggravation
I'm starting to think you're right. Let's forget this idea.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Them & Us

Postby gsf » Wed May 09, 2007 2:26 pm

Red Ed wrote:
gsf wrote:and my take on cannibalistic forums
life is too short to suffer the aggravation
I'm starting to think you're right. Let's forget this idea.

that's not to say I don't peruse those forums
sort of like tabloids at the supermarket checkout
glean the good info and leave the cruft behind
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Wed May 09, 2007 2:39 pm

I had a look too

Of interest.... someone suggested that if we spoke Japanese we could go to a japanese website and find all our work already done .

Do we really think this is true ?

C
coloin
 
Posts: 1662
Joined: 05 May 2005

Postby Steve K » Mon Jun 04, 2007 11:54 am

The concept of backdoors and GEM, are, in my opinion, closely related.
I have a broad theory about "dimensioning" of sudoku deductions. Specifically, it tries to analyze deductions based upon the complexity of interactions between the native sets considered. This idea is still very rough, but promises to reveal the apparent inaccessability of both backdoors and explain why GEM eliminations occur.

In the proof of new strong inference set, If, for each member of a strong inference considered, one needs to consider only one weak inference set, then that particular deduction is two-dimensional. Most known sudoku eliminations that do not consider uniqueness fall into this category. Many sudoku eliminations that may appear very complex actually become no more complex than bi-value or bilocation chains using this template.

Multi-dimensional considerations are much harder to define - at least for me, - except that they are not 2-dimensional. Many "3-D medusa" chains are in fact 2-dimensional. Deductions that are strictly greater than 2-dimensional are probably better referenced as nets. Nevertheless, many 2-dimensional chains are understood as nets, but certainly can be expressed as strict chains.

Some deductions are potentially as large as 4 dimensional. I think that with sudoku, 4 diimensions is the maximum. Also, it is possible that once one uses uniqueness, 3 dimensions becomes the maximum complexity.

Such broadly vague investigations are what I am very interested in. However, the vagueness of the investigations makes them very difficult, as precision is immediately demanded. The point of vagueness early on, is, in my opinion, precisely to not exclude potential discoveries. Downside:
It is difficult to collaborate with such vagueness!
Steve K
 
Posts: 98
Joined: 18 January 2007


Return to General