## Guesses?

Advanced methods and approaches for solving Sudoku puzzles
I think part of the problem is that a puzzle (in my opinion) cannot by itself be good or bad. A sudoku that has been generated to simply guarantee a unique solution and nothing more is a bad puzzle and I have no sympathy with them whatever. A good sudoku should be generated with an eye to how it is solved (whether by hand or by computer). This is how Pappocom puzzles are done. The problem is that this is not an inherent property of the puzzle - the two different generation methods could come up with the same solution. So when you dub a puzzle into the program, it can't tell whether it's a old-style-Telegraph type puzzle that I hold know truck with at all, even if it can technically be solved with advanced techniques, or if it's been generated by something like Simple Sudoku, which knows exactly what forcing chains and what swordfishes can solve it. So the problem of classifying advanced sudokus can't be solved, and we should stop worrying about it.
PaulIQ164

Posts: 533
Joined: 16 July 2005

At some point in recent days I believe I recall tso saying something along the lines of any puzzle having a unique solution must be solvable by logical means. Owing to there being a potentially vast array of logical techniques remaining to be discovered, this statement is obviously immensely difficult to prove (something for a PhD in a few years time there Paul?) However, I would like to award the status of Conjecture to this suggestion, as I also believe many of us consider it to be true. It is therefore inappropriate of anyone to classify such a puzzle as 'Invalid', though perhaps 'Arguably Unfair' could be permitted, given an accompanying explation.

However, I also recall someone else (by all means let me know, I'll give credit in the edit) commenting that Wayne's original programme was written long before the advent of the current esoteric approaches available to the 'hardcore' solving community. It therefore casts its judgements based upon approaches that many of us consider elementary, especially in the light of the last few months' evolution.

I believe these two paragraphs illustrate the point clearly. We all know Wayne isn't given to entering into lengthy public debate, and that stance should be respected, whether or not it is agreed with. Whether Wayne will be able to build a more powerful judgement algorithm into the next version of the programme remains to be seen, but any change will surely still be out of date the following day. Should Wayne choose to reassess his language is also a moot point - we will just have to wait and see.

Either way, it really isn't worth wasting so much energy on. There hasn't been a new technique discovered for at least a fortnight.

Has there?
Karyobin

Posts: 396
Joined: 18 June 2005

PaulIQ164 wrote:But there's a difference between altering the rules of a game, and not considering puzzles that require too-complex techniques as valid.

Calling completed chess games that used castling invalid and those that didn't valid does not alter the rules of the game any more or less than calling one set of sudokus invalid for whatever arbitrary reason we choose.

PaulIQ164 wrote:... I don't think Pappocom is entirely to blame. As I understand it, Nikoli puzzles use essentially the same standards when constructing its puzzles.

This is a myth. Nikoli creates their puzzles by hand. Puzzle creation is a similar skill to puzzle solving. The nearly inescapable by-product of this method of this type of creation is puzzles that require the type of tactics you'll seen in a Pappocom HARD or less. (Every Nikoli puzzle I've rated with Pappocom softare comes out HARD or less.)

It's not impossible to create a puzzles by hand that requires forcing chains, colors or something beyond that, just more difficult. I don't believe creating the most difficult possible puzzles was a priority, so little effort was spent in that direction.

Those at Nikoli have talked about poor quality computer generated puzzles flooding the market, but never stated or implied that they were invalid. Personally, I do feel that when solving lower level puzzles, hand made are better -- I can't tell if my judgement is based on prejudice and loyalty or not.

PaulIQ164 wrote: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?

"Invalid" is not.

PaulIQ164 wrote:I don't see anything wrong with describing the Daily Telegraph ones as 'sudoku-lookalikes' when they were launched.

Calling the Telegraph's puzzles "sudoku-lookalikes" is equivalent to saying "The Telegraph's puzzles are NOT Sudokus." It is factually inaccurate. All reasonable people will read that statement and conclude, that if the statment is true, those puzzles are not Sudoku -- which is what I suspect what he is trying to imply. If you manufactured cricket balls and your major competitor publicly claimed that they were merely "lookalikes" ... I guess you couldn't argue -- since your cricket balls certainly do look like cricket balls.

PaulIQ164 wrote: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.

Both SadMan Sudoku and Simple Sudoku generate puzzles that Pappocom label as "invalid". Simple Sudoku generates only puzzles the it can solve by a specific set of human-implementable logical steps, though it will allow you to import puzzles that are beyond its solving capacity. SadMan will create puzzles that it cannot solve without Trial and Error based on user choice. (We're not supposed to talk about puzzle creation here, so I'll stop.)

I'll stipulate that there is a qualitative difference. I've noticed that it's *very hard* to find a puzzle from any other source that Pappocom rates as *very hard* -- they either come out HARD or below, Arguably Unfair or Invalid.

I'll also stipulate that Pappocom's puzzles are good and that the Very Hards are subjectively different from puzzles available from any other source and are alone reason enough to purchase his software.
tso

Posts: 798
Joined: 22 June 2005

Karyobin wrote:At some point in recent days I believe I recall tso saying something along the lines of any puzzle having a unique solution must be solvable by logical means. Owing to there being a potentially vast array of logical techniques remaining to be discovered, this statement is obviously immensely difficult to prove (something for a PhD in a few years time there Paul?) However, I would like to award the status of Conjecture to this suggestion, as I also believe many of us consider it to be true. It is therefore inappropriate of anyone to classify such a puzzle as 'Invalid', though perhaps 'Arguably Unfair' could be permitted, given an accompanying explation.

Actually the fact that a unique solution allows logical means to solve a puzzle is trivial to prove. Brute force trial and error if applied correctly can be considered logical, not a guess, based on whether it's willing to stick with a placement that merely "works" or whether it can prove that placement is valid based on other criteria. The rules involved in this technique will always be able to find either an inconsistency, an impossible placement, or a guaranteed placement from all common solutions. If multiple solutions exist, then and only then will those rules break down. If only one solution exists, making a wrong placement will always end up with an inconsistency.
Either way, it really isn't worth wasting so much energy on. There hasn't been a new technique discovered for at least a fortnight.

On the contrary, I know of at least three. Two more variations on the uniqueness test have been found: one by me, another by PaulIQ164. I've also proposed another format to the test, based on the same logic, that extends it to 7 known configurations. And in the programmers forum, Nick70 has found a method for finding bifurcating implication chains that requires no backtracking.

Also there's the matter of coloring. Until recently I don't think it was common practice to use exclusions to their full potential. In fact if anyone was using the technique I now refer to as complete simple coloring, I'm unaware of it. This method is a superset of both fishy cycles and turbot fish, and finds most Nishio cases as well.
Lummox JR

Posts: 125
Joined: 22 September 2005

I spent ages typing in a post last night when, upon clicking submit, this cursed computer crashed. *gaaaargh*

Anyway, the gist of it was : Wayne spent 6 years developing his program and it was done - as previously mentioned - before the advanced solving techniques were developed. Michael Mepham spent a week developing his (could this be 'good quality' sudoku?) Farewell to Ariadne's thread? He now seems to have changed his mind about guessing. At least Wayne remains consistent about what he considers Invalid and Arguably Unfair - and is about to unleash the new version of the program on which, I believe he is working.

Having conducted a search using Google the only thing I can find on the rules is the "fill in each row.............." and Nikoli says. Wikidpedia Soduku do a lengthy and informative piece on the subject, including guessing and all it's forms. So as to the rules of traditional sudoku (what it is, how it's created, what is regarded as 'good' etc), you have me at an advantage (Shogi, on the other hand, turns up quite a bit of information, including this: Shogi which tells you about the aforementioned drops).

Wayne has already spoken on the subject of calling the puzzles sudoku, so there's no point - imho - in going over that again. And they weren't, as far as I can tell, 'invented' (if that's the correct word) in Japan. Nikoli developed them in Japan and gave them their name. It is from Nikoli that we get the 'they must be symmetrical and have only one solution' bit from - and who is to say that they are right? Well, Nikoli have been successful with their puzzles and have been creating them for a long time. However, solvers do have to rely on Nikoli to generate puzzles (no software to buy and use at home, then, to obtain advice - hints and tips? - from the 'masters' or practice your advanced techniques). There is an email address on their website that you can use for questions, beyond that its "fill in each........". And they are not overly impressed with the software approach to creating puzzles in general (if you want to take what that implies into account).

As I understand it, Wayne's was the first sudoku software to become available and, as previously stated (curse compter crashes), will now be somewhat out of date, especially in the light of current techniques being developed at a frighteningly fast pace. He may, however, choose not to implement any of said techniques. There is the aformentioned software, freely available (as I understand it) to those that require it. More, I feel certain will be released as people decide to create their own for their own purposes based on what they consider the 'rules' to be.

So, in the end, what makes a good soduku? Who decides that? What are the rules of traditional sudoku?

The debate continues.

Luna
lunababy_moonchild

Posts: 659
Joined: 23 March 2005

Is it too banal for me to repeat what I already said in some far-off thread, that it's hard to argue the terms with the person who created the program. Could it be OK for Pappacom to label puzzles as invalid meaning 'invalid for my program'? Not 'existentially invalid' for all you people who want to use fishy cycles and Nishios, just 'invalid for this program that I developed'. I can live with this - I just take the invalid ones to Susser. If Pappacom knows that we all do that, then he might change his program. Or not.
emm

Posts: 987
Joined: 02 July 2005

One of the points I was trying to make, though, is that if essentially everyone who has ever commercially mass-produced sudoku (Nikoli, Pappocom) have made puzzles that require the same tactics, there's surely an implicit understanding that this is a standard for what tactics should be needed for a sudoku. So it's not like disallowing chess puzzles that involve castling, since every chess authority agrees upon castling being a proper move in chess, whereas a lot of people would argue that if you have to plot a bilocation graph or whatever to solve a sudoku, it's not a fair or standard sudoku (although I agree on avoiding the epithet 'invalid').
PaulIQ164

Posts: 533
Joined: 16 July 2005

em wrote:Is it too banal for me to repeat what I already said in some far-off thread, that it's hard to argue the terms with the person who created the program. Could it be OK for Pappacom to label puzzles as invalid meaning 'invalid for my program'? Not 'existentially invalid' for all you people who want to use fishy cycles and Nishios, just 'invalid for this program that I developed'.

I reckon he did that. Inferences, like art, are in the eye of the beholder, imho.

em wrote:I can live with this - I just take the invalid ones to Susser. If Pappacom knows that we all do that, then he might change his program. Or not.

I reckon he knows that.

And I agree with your points.

PaulIQ164 wrote:One of the points I was trying to make, though, is that if essentially everyone who has ever commercially mass-produced sudoku (Nikoli, Pappocom) have made puzzles that require the same tactics, there's surely an implicit understanding that this is a standard for what tactics should be needed for a sudoku. So it's not like disallowing chess puzzles that involve castling, since every chess authority agrees upon castling being a proper move in chess, whereas a lot of people would argue that if you have to plot a bilocation graph or whatever to solve a sudoku, it's not a fair or standard sudoku (although I agree on avoiding the epithet 'invalid').

I agree with this too (except for the brackets). Thing is, who wants to plot a bilocation graph or whatever on the commute to/from work - which is what I think (although I could be wrong) the Pappacom software was created for. As Em pointed out there are other software engines available for everything else.

I don't think that we have an industry standard, as of yet. Perhaps discussion like this could lead to one.

Luna
lunababy_moonchild

Posts: 659
Joined: 23 March 2005

Lummox JR wrote:Brute force trial and error if applied correctly can be considered logical

No they can't. (teehee - pass the spoon)

Seriously though, I can't be bothered to dredge up that old debate again. As I said months ago - for me it's about elegance. Tell you what though Lummox JR, I could be way off, but you're talking like a coder, not a mathematician. No-one could argue that a specific puzzle cannot be solved by trial and error, but that's not what I said.

Lummox JR wrote:Either way, it really isn't worth wasting so much energy on. There hasn't been a new technique discovered for at least a fortnight.

On the contrary, I know of at least three.

Having a bit of trouble spotting a joke, are we?
Karyobin

Posts: 396
Joined: 18 June 2005

PaulIQ164 wrote:One of the points I was trying to make, though, is that if essentially everyone who has ever commercially mass-produced sudoku (Nikoli, Pappocom) have made puzzles that require the same tactics, there's surely an implicit understanding that this is a standard for what tactics should be needed for a sudoku. So it's not like disallowing chess puzzles that involve castling, since every chess authority agrees upon castling being a proper move in chess, whereas a lot of people would argue that if you have to plot a bilocation graph or whatever to solve a sudoku, it's not a fair or standard sudoku (although I agree on avoiding the epithet 'invalid').

A better way of putting it might be that there's an implicit standard for the tactics used in mass market puzzles. A lot of people love crosswords, but some revel in the ultra-hard ones. The latter are not invalid, but merely don't belong in the same publications.
Karyobin wrote:
Lummox JR wrote:Brute force trial and error if applied correctly can be considered logical

No they can't. (teehee - pass the spoon)

Seriously though, I can't be bothered to dredge up that old debate again. As I said months ago - for me it's about elegance. Tell you what though Lummox JR, I could be way off, but you're talking like a coder, not a mathematician. No-one could argue that a specific puzzle cannot be solved by trial and error, but that's not what I said.

At the risk of reopening that can of worms, here's my explanation. Trial and error, if correctly defined, always uses logic to reach its ends. It does not place a number and see if the solution is fully solvable, for that's a mere guess and tells you nothing. T&E can only 1) look for inconsistencies caused by a placement, 2) look for a constraint (digit in cell, placement of digit in a house) whose possible choices all confirm or reject a placement.

I think I see now that what you were saying included the unspoken premise that T&E doesn't count as logical. It does, but indeed it is not elegant. It's not guessing, but it's far too much like guessing to be palatable. Your conjecture then is not about all logical techniques per se, but merely the kind of logical techniques that people consider "fair" to use. That line can be drawn just short of T&E, or it can be drawn much lower, since the set of preferred solving techniques is entirely subjective. Ultimately all techniques are all the same rule distilled into different patterns (or with T&E, no pattern). As em nicely put it, T&E is merely a logical technique without refinements, while all the other tests are refined in some way. Is a pattern/refinement required? What then of Nishio?

You're quite right that I was talking like a coder, not a mathemetician. I do have a math background as well, though, so here's my attempt to rephrase this in mathematical terms. Noting that the set of logical techniques excluding T&E may not be fully known, and is not necessarily finite, you consider as conjecture the statement that this set can solve any puzzle. With that I can agree. If T&E is eliminated as a possible logical test, then the known set of techniques--those that are not a form of T&E anyhow--is not capable of solving all puzzles, but whether it can do so in the future remains an unknown.

And nope, I didn't catch the joke, but then that's what I get for posting at 2 AM.
Lummox JR

Posts: 125
Joined: 22 September 2005

LOL! Nice one. I don't dare admit the state I was in when I wrote all that as well.

I agree with what everyone says with regard to T & E being logical - it is, of course. My only criteria for rejection of a technique is whether or not I know what I wish to achieve before I commence applying it. I agree it's not a very scientific method of judging, but for me aesthetics count too.
Karyobin

Posts: 396
Joined: 18 June 2005

My general rule is if I find myself saying "if that were" at any point then I don't count it as good and proper.
PaulIQ164

Posts: 533
Joined: 16 July 2005

?

Gonna sign off now, so don't be obliged to respond immediately but - isn't that what colouring and chains are all about? I mean, it's quite possible that you have reduced the techniques to some manner of algorithimic construct in your mind, but that's still essentially what's going on isn't it?

Don't forget I'm on your side here, I've just allowed such methods as named above to enter my canon and I'm not sure where you stand. I strongly suspect you use and respect them, I just can't see how that fits with what you just said.

You have sixteen hours to respond...
Karyobin

Posts: 396
Joined: 18 June 2005

PaulIQ164 wrote:My general rule is if I find myself saying "if that were" at any point then I don't count it as good and proper.

My general rule is that I don't count it an interesting puzzle unless at some point I find myself saying "if that were".

----------------------------------------
Nine sets of nine are awaiting exposure,
naked & hiding, deranged in composure.
r.e.s.

Posts: 337
Joined: 31 August 2005

While it's easiest (though not necessary) to state chains in the "if there were" way, coloring is more of a straightforward pattern technique.
Lummox JR

Posts: 125
Joined: 22 September 2005

PreviousNext