Guesses?

Advanced methods and approaches for solving Sudoku puzzles

Postby Myth Jellies » Sat Oct 08, 2005 5:47 am

Angus,

For promoting Sudoku to the masses, Pappocom is beyond great. For attaching perjorative phrases such as invalid or arguably unfair to legitimate puzzles and avoiding them like the plague is, while understandable, perhaps not so great. Comparing them, he is far on the plus side, so perhaps I did do him a disservice. (Although, I certainly like your "extreme" or Mepham's old pre-nerfed "diabolical" characterization better.) I'm sure he gets hundreds or thousands of e-mails whenever he posts a puzzle that is too hard, including some very important ones from the editors of papers who subscribe to his services. So my opinion does not count for much except for me.

But the way things stand, cutting edge solving techniques probably won't be holding up a Pappocom puzzle as an example to be solved; which I feel is a shame because they probably have the widest forum & would generate the most buzz. Wave it off as a pipe dream from an old grouch:)
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby angusj » Sat Oct 08, 2005 6:49 am

Myth Jellies wrote:For attaching perjorative phrases such as invalid or arguably unfair to legitimate puzzles and avoiding them like the plague is, while understandable, perhaps not so great.

Again, in fairness to Pappocom, I'm pretty sure he made these comments well before exotic techniques were discovered / documented. Also, they were most likely made in the context of pen and paper solving where swordfish, coloring, xy-wing etc could very reasonably be considered well beyond any but the most extreme enthusiast and hence "arguably unfair".

Myth Jellies wrote:Wave it off as a pipe dream from an old grouch:)

:D
angusj
 
Posts: 306
Joined: 12 June 2005

Postby PaulIQ164 » Sat Oct 08, 2005 12:00 pm

And I think there's certainly something to be said for not publishing 'advanced' sudoku puzzles, in newspapers at least, simply because you should be able to do them with nothing more than that newspaper and a pen. As I understand it, people don't solve the advanced puzzles like that. Making them available on computer programs, strictly as an optional extra, would be a good idea I guess - no reason not to, but I wouldn't go any further than that.
PaulIQ164
 
Posts: 533
Joined: 16 July 2005

Postby stuartn » Sat Oct 08, 2005 1:27 pm

Agree totally Paul..... the good thing about the published puzzles is that they're normally solvable during the working day - either on the train (or bus etc) to or from work, or during breaks. Making them virtually impossible for all but the most sagacious Sudonauts would turn the casual player away.

The balance is exactly right as it stands. If we want a downright b*stard to solve we know where to find them. Likewise - if people want to know about multiple forcing chains and the various aquatic or airborne strategies they will invariably find help from this august forum on the web.

Gladys on the 7:25 from Ashford to Tonbridge is quite happy with her non-demanding but satisfying level of play.... thankyou.

Back out into the sunshine of Northern Cyprus now - and a nice cold beer (again)

Stuartn:D
stuartn
 
Posts: 211
Joined: 18 June 2005

Postby Karyobin » Sat Oct 08, 2005 4:37 pm

Top stuff all of you, you've done us proud again.

Should we try to organise something to address stuartn's drinking - a party perhaps?
Karyobin
 
Posts: 396
Joined: 18 June 2005

Killer? Whazzat?

Postby magrurry » Sat Oct 08, 2005 5:13 pm

What the hell is a KILLER Sudoku anyway? Does it cut you when you try and sovle it? What if you're on the bus, does it attack the driver? I thought i hated doing Sudoku's when i first saw one. Then i tried it and failed. Then i tried it and worked it out. Real proud of myself till i got here. You guys are Mathmaticians for sure. Well i majored in Englich-I mean English, and it took me two days to do an LA times one. Then i became hooked. Thinking i could solve any puzzle. Now? Im scared again. Thanks. Thanks a lot.
magrurry
 
Posts: 2
Joined: 08 October 2005

Postby Karyobin » Sat Oct 08, 2005 5:43 pm

Wrong thread Magrurry. You got it right second time.:)
Karyobin
 
Posts: 396
Joined: 18 June 2005

Postby 9X9 » Sat Oct 08, 2005 7:26 pm

angusj wrote:Well I think a comment like that does Pappocom a disservice. If it wasn't for his passion for Sudoku, we wouldn't be discussing it here today. That Sudoku solving strategies have evolved is because of the interest generated by his programme, not in spite of it.


I'm certainly indebted to him.
9X9
 
Posts: 100
Joined: 26 September 2005

Postby tso » Sat Oct 08, 2005 9:10 pm

Plenty of newspapers and magazines routinely publish crosswords, cryptics and acrostics that are far beyond the capabilities of all but the most advanced solvers -- puzzles that very few could complete on even the longest commute and certainly not without a pencil and eraser -- and maybe a dictionary. Yes, the majority of the puzzles are easier, but there's something for everybody -- no one is left out.

The fact that someone popularizes something does not forgive them getting it wrong. It would take *nothing* away from his software sales or his status to change "arguably unfair" and especially "invalid" to a more appropriate word. What would we say about a Crossword solving program that would judge puzzles printed in the Telegraph as "Invalid"?

As I've said before, I've solved 100's of different types of logic puzzles and I've NEVER seen one presented with the silly disclaimer -- "these puzzles can be solved with logic only, no guessing required" -- a disclaimer that originated with Pappocom and has been taken up by hundreds of other Sudoku producers, publishers, websites, etc, as if it carries any meaning.

There has been study of advanced Number Place solving tactics in Japan that predates the current fad. There was also some discussion about the mathematics of Number place in rec.puzzles, sci.math etc in the late 90's.

Number Place Metapuzzle discussion in Usenet

And here -- containing an intriguing comment that suggests that 17 is the minimum number of clues possible
tso
 
Posts: 798
Joined: 22 June 2005

Postby Lummox JR » Sat Oct 08, 2005 9:13 pm

Regarding what 9x9 posted about simes.clara.co.uk and their definition of T&E, I think it's safe to say that the description there is poor.

T&E does not place a candidate and look for the possibility of a solution. That's just a mere guess.

As I mentioned earlier, T&E can only be used in cases where it can firmly cause a contradiction, or where all of the valid choices for a constraint (digit choice in a cell, or position choice for a digit in a house) will cause a candidate in some other cell to be true or false. You can take T&E out as far as you want to look for those contradictions, but in the end if you find a completely solved puzzle, you cannot assume the placement you tried is valid; it may be that the puzzle was invalid and had multiple solutions.

In other words, there are only two conclusions you can draw:

"This choice invalidates itself because _____"
"All valid choices for ____, one of which must be true, prove _____"

To choose a placement and stand by it is only a guess, nothing more. If it completes the puzzle, you have learned nothing about the puzzle itself and may have inadvertently considered an invalid multi-solution sudoku to be valid. If the true forms of T&E can take you no further, the puzzle either has multiple solutions or was never soluble to begin with.

That same set of pages has some other muddy definitions. Coloring is inadequately described, for example. In several instances blue and green are shown as conjugates, but in a later example they're each used to describe both halves of a conjugate pair (i.e., blue-black and blue-red, green-black and green-red). It shows that you can join two "weakly linked" colors if the weak links match up, but mentions nothing about how implications and exclusions can be computed transitively to find other potential eliminations. Coloring is not truly complete without that insight; indeed that's a central facet of supercoloring.
Lummox JR
 
Posts: 125
Joined: 22 September 2005

Postby PaulIQ164 » Sat Oct 08, 2005 9:49 pm

tso wrote:Plenty of newspapers and magazines routinely publish crosswords, cryptics and acrostics that are far beyond the capabilities of all but the most advanced solvers -- puzzles that very few could complete on even the longest commute and certainly not without a pencil and eraser -- and maybe a dictionary. Yes, the majority of the puzzles are easier, but there's something for everybody -- no one is left out.


It's a fair point. I wouldn't have a problem with advanced puzzles as an occasional extra - a "Listener Sudoku", if you will. But I'm not sure there'd be much point. Once a sudoku is so complicated that it's easier to do it by T&E than to use the advanced techniques - which I guess an awful lot of people wouldn't come up with on their own; I'm sure I wouldn't - it loses a lot of it's point as a puzzle. I don't do these advanced puzzles, but isn't it more the investigation into and invention of new techniques that holds the fun, rather than the puzzles themselves as discrete entities?

I entirely agree that 'invalid' is a pretty daft way to classify a sudoku that has a unique solution.
PaulIQ164
 
Posts: 533
Joined: 16 July 2005

Postby lunababy_moonchild » Sun Oct 09, 2005 1:24 pm

tso wrote:Plenty of newspapers and magazines routinely publish crosswords, cryptics and acrostics that are far beyond the capabilities of all but the most advanced solvers -- puzzles that very few could complete on even the longest commute and certainly not without a pencil and eraser -- and maybe a dictionary. Yes, the majority of the puzzles are easier, but there's something for everybody -- no one is left out.


Yes they do. However, I think that it can be taken for granted that the above mentioned crosswords, cryptics and acrostics etc have been around for ages - I certainly remember my mother driving the whole family mental with certain crosswords that 'she' liked to do, when I was a child (and that was a very long time ago!) - and Sudoku has only been available in this country since November and only widely available after that. Perhaps it will develop to accomodate the advanced solvers as it grows and there becomes a mass market to accomodate.

tso wrote:The fact that someone popularizes something does not forgive them getting it wrong. It would take *nothing* away from his software sales or his status to change "arguably unfair" and especially "invalid" to a more appropriate word. What would we say about a Crossword solving program that would judge puzzles printed in the Telegraph as "Invalid"?

Imho, and it is only imho, what Wayne calls his own puzzles is his decision (and how can he be wrong about that?). He does provide explanations for both of those terms. Anyway, the new verson of the program is due to come out, who knows what it will contain? Again, crosswords have been established for a very long time.

Luna
lunababy_moonchild
 
Posts: 659
Joined: 23 March 2005

Postby tso » Sun Oct 09, 2005 2:29 pm

lunababy_moonchild wrote:Imho, and it is only imho, what Wayne calls his own puzzles is his decision (and how can he be wrong about that?). He does provide explanations for both of those terms. Anyway, the new verson of the program is due to come out, who knows what it will contain?


He can call his own puzzles marzipan kangaroos if he wants and I won't complain. However, he publicly calls other pubication's puzzles INVALID. He uses language like "sudoku-lookalikes" implying they are not actually Sudokus. This is all about marketing. This has caused great confusion. There are many threads in this (and other) forum in which one person had trouble with a puzzle from another source, posted it here for help, and was told that the puzzle was INVALID by someone who had tried to dub it into Pappocom's software. Though he explains what he means by INVALID and ARGUABLY UNFAIR, most people don't see those explanations and/or don't understand what he means. The user must make a big effort to find these definitions. I didn't see them myself when I first got the software -- I assumed it was a glitch.

If you were to download a chess program that explained that castling was an invalid move, could you defend this? If the program wouldn't allow you to examine games from that included castling or allow you to make that move in the game -- well, they can do what they want with their own software, right? If this seems far fetched ...

Currently, the most popular board game in Japan is Go, followed by Shogi. Shogi is a chess-type game that is far superior to chess but still relatively unknown outside of Japan and the abstract strategy game playing world. A big difference between the FIDE chess you are familiar with and Shogi is that a captured piece is not eliminated, but instead, becomes part of the capturer's army, who can later "drop" a piece back onto the board instead of making a move. Because of this, draws are very rare, less than 1% of championship level games. If Wayne travels back to Japan, "discovers" Shogi, successfully popularizes it in the UK and elsewhere with his software called "Shogi" -- software that calls "drops" INVALID and does not allow them, what are we to do? The word "Shogi" is in the public domain, just as "Chess" is. He can do what he wants with his own software. If he doesn't like drops, why should he have to put up with them?

Because he should. And if he wanted to change the rules to Sudoku, he should have changed the name and made it very clear which of his specifications are NOT part of the traditional puzzle. I don't get it -- virtually all other Sudoku software will allow the user to import or dub in puzzles that are more difficult than the software will generate and/or solve without needing to explain this. (Simple Sudoku, SadMan, etc.)

(And yes, at least one person made a "Shogi" program some time ago that didn't include or even mention the possiblities of "drops". I don't know if he didn't understand the game or just didn't like the drop rule. Fortunately, his software was not wildly successful and had little impact.)
tso
 
Posts: 798
Joined: 22 June 2005

Postby PaulIQ164 » Sun Oct 09, 2005 3:06 pm

But there's a difference between altering the rules of a game, and not considering puzzles that require too-complex techniques as valid. Now I agree that unqualifiedly labelling them as 'invalid' isn't the ideal solution, but I don't think Pappocom is entirely to blame. As I understand it, Nikoli puzzles use essentially the same standards when constructing its puzzles. Now they were surely the biggest authority in sudoku before Pappocom (and arguably still are). So isn't there an implicit understanding about what makes a 'good' sudoku for normal solving purposes? Pappocom was just continuing that understanding. I don't see anything wrong with describing the Daily Telegraph ones as 'sudoku-lookalikes' when they were launched.

And I still argue that there's a qualitative difference between Pappocom-style puzzles and advanced ones. The problem with advanced sudoku is that (as I understand it - correct me if I'm wrong) they're generated with the only constraint being that there is a unique solution. That's how they're used to find new logic techniques, isn't it? Certainly this is how the first DT puzzles must have been produced. Pappocom puzzles are built to be solveable in particular way. This is the similarity with even the trickiest corsswords - the compiler of the crossword could still show you how to solve them.
PaulIQ164
 
Posts: 533
Joined: 16 July 2005

Postby Lummox JR » Sun Oct 09, 2005 9:48 pm

The difference between "invalid" and "unsuitable to my standards" is a wide gulf, and to use the terms interchangeably isn't something that can simply be charitably overlooked. To call a puzzle invalid just because it's more complex than the software would like is, bluntly, ridiculous. To suggest a valid sudoku is merely a sudoku lookalike is equally ridiculous.

I grant that there's a difference between the styles of puzzles, but it's not one that makes language like "invalid" excusable. It's one thing to reject a class of puzzles for publication on the basis that their solution paths are too complex. It's another thing to outright consider them void. An aficionado of simpler puzzles can hardly be upset about the publisher being selective, but the fact of that selection doesn't make harder puzzles invalid; it just makes their inclusion in such a set an editorial error.

[edit]
It does occur to me that because sudoku is supposed to be logically solvable without resorting to guessing, this may be a case of the author simply chalking up all advanced techniques to guessing. It's more than a bit unfair. Even trial and error doesn't count as guessing if it's done right, though it's awfully close. If brute force T&E at some point fails to place or eliminate a candidate, however, then the puzzle is truly invalid because it must have multiple solutions.
Lummox JR
 
Posts: 125
Joined: 22 September 2005

PreviousNext

Return to Advanced solving techniques

cron