Flagged Revisions installed. Unapproved pages display a Red unchecked notice under the title. Trolls attack here by creating and archiving pages with offensive content. To verify an archived page, check the original URL. Questions about administration? Contact User talk:Abd. Limited privacy on this site, see CFC:Limited privacy

Sudoku/Bifurcation methods/Beran 2005

From CFC
Jump to: navigation, search

Max Beran » Thu Aug 25, 2005 Hard puzzle in Eppstein's paper:

In the "Exercise on xyz-wing and xy-chain" topic Scott H draws attention to David Eppstein’s paper “ Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku “.

Review by Abd (talk) 22:03, 24 July 2019 (UTC)

In Figure 11 the author shows "one of the more difficult" puzzles. Nothing daunted, I thought I’d give it a go and succeeded only in reaching the following point:

SW Solver link for raw Sudoku as shown by Beran (link includes 81-digit code] The raw sudoku was loaded into Hodoku. The Hudoku solver was run until it required uniqueness, which was not accepted. The same puzzle was run in SW Solver until an X-cycle was found, not accepted, then it reported uniqueness strategy. This is how Hodoku looked at this point.

Eppstein.png
after which there is quite a lot of tidying up possible through couples, locked rows and columns such that the cell with the highest number of candidates is r2c1 with 1, 2, 4, 7 and 9. But finally I reached an impasse. I’ve filtered for x-wings, swordfishes and xy chains, searched for hidden triples and quads but nothing.
According to the paper it is solvable using the techniques given there (but in very mathematical terms so not for ornery mortals). However it does imply that trial and error is not one of their techniques.
So is there anyone out there who can see how to solve this puzzle? Presumably Eppstein's so-called repetitive and non-repetitve cyles might play a part but their operation seems horrendous - are they part of the serious player's toolbag?

I am not sure what techniques are described in the paper (see the page supra for a link to it), because I do know a technique which is both advanced and almost scary-simple. I keep in mind that the above was written almost twenty years ago and there was massive confusion on certain issues, often among experts. If a technique is very simple as to each step, is it "horrendous", given that one may mark the puzzle to keep it simple? Is a method which identifies two mutually exclusive possibilities, and then generates proposed resolutions from *both*, "trial and error?." These terms are used and seem to be assume for, for example, Nishio, and Nishio himself seems to be caught in the same trap.

There is a solving technique which I think every serious sudoku solver should at least understand in theory. It is how the computer solvers work. It is not "guessing." It is called Sudoku/Ariadne's Thread, and is a standard logical technique. Because Ariadne's Thread can be run in any order and from any starting point, it will, on average, take a lot of computing, but present-day computers are so fast that way'crazy complicated analysis can be done in a fraction of a second. No guessing is involved, just a complete list of exclusive possibilities. Humans can run Ariadne's thread, we demonstrated it with Sudoku/Inkala's Maze. The trick is *not* to just run mindlessly through a list of all possibilities, but to choose ones more likely to be productive.

And that offends some sudoku aficionados, because they think of it as "guessing." Yet we "guess" constantly when solving sudoku. We have an armamentarium of many, many techniques and many places to look, and we gain skill with experience as to what and how to look at patterns. Any strategy that involves looking at a complete set of two exclusive possibilities and observing interactions is a simple bivalued Nishio. It's often very easy to see. What if it gets complicated?

But the proof is in the pudding. What can I do here? I don't know until I actually run the technique. Now, I've been, for some years, doing bifurcation in ink on paper. The way I do it is far simpler than the very complex annotations that some use. I mark candidates with dots, and I would never start bifurcation until I have a complete candidate list. I may then mark the candidates into two sets, by circling one chain and "triangling" the alternative. But I can do this on Hodoku with coloring. And, very neat, I can find results (or few "results" from a choice of one pair. Bifurcation will always reduce the sodoku into two puzzles, and it's possible to use advanced techniques within each. But I don't normally, and the reason is that it takes too long to look for them and seems to be, so far, unnecessary. With this technique I went through Longo's Black Belt Sudoku and did every puzzle (there are a few where I made mistakes, and in ink, I just went on, but for fun I plan to eventually solve all of them. I know know better why I make "stupid silly" mistakes, that's been fun to discover. It's surprising. It's not what I thought.

Eppstein1.png

This puzzle has very abundant pairs, both individual cell pairs and many row and column pairs. I look at it and expect it to be easy. If I were working in ink, I'd be very careful about my pair choice. With Hodoku, I'll simply choose one were I see some consequences in both legs. So I color the 2 in r5c1 green and the 7 red and the cell light orange so I know where I started. That's important, because this technique follows all consequential resolutions, not merely strong links. The author may have been aware of 3D Medusa, which only uses strong links, and if one comes to a contradiction with one color, one may eliminate all candidates of that color. In this method, only the original candidate can be eliminated. Then any strong links will follow, but weakly linked candidates will simply be decolored.

With the green candidate, the puzzle almost cracked. Almost cracked is not cracked, it was a contradiction. I can easily check, but avoid it. I ran the green chain again! The image here is the second run. It's easy and is faster the second time, always. Even if I can't consciously remember what I did.

This time the green didn't go quite so "well," so maybe I made a mistake [and in hindsight, I must have]. I took red a lot further, and eventually hit pay dirt. The first mutual confirmation is colored in light purple (not yet implemented), and cells with eliminations are colored light blue. I see I lost the starting cell color, no matter, I know what it was.

Eppstein2.png

With the resolutions shown, and continuing coloring, the rest of greens filled out all cells, so green is a valid choice, proven. but I'm not done yet. I have proven a valid solution but not that it is unique. So I need to continue eliminations and intersections until I find that red is in contradiction -- or can be completed. As the eliminations proceed, the board looks more and more like a BUG, which is common. And I did find a contradiction, not quite to the BUG state. To really nail this, I'd want to run it again, very, very carefully. but it's not worth the effort. Multiple solutions sudoku are rare as hen's teeth, and it's enough for me to allow the possibility of discovering that, miracle of miracles, all these people looked at this puzzle and failed to notice that there was more than one solution. Sure, some people ran solvers on it and allowed Unique Rectangles, which can conceal multiple solutions, but the Solution Count on SW Solver was 1. That is an Ariadne's Thread program and makes no assumption about uniqueness.

This was not a difficult sudoku. Was I just lucky? Well, this happens again and again. I did not know which of the two candidates was the valid choice, and I looked at both. The "guess," if anything was which pair to test, and I did not just pick a fully-random pair, I checked to see that there were multiple resolutions both ways, and as with trying any strategy, one might not find anything. Except that with a little care, and with ordinary published sudoku, including way-crazy diabolical, etc, Black Belt Sudoku, etc.. the technique works.

Sudoku/Inkala's Maze, another story entirely. First thing one will see about Inkala's Maze that there is only one pair visible immediately, {39}, and it does, like, nothing. Row 6 has a pair of 7s that are slightly more productive and we used that to solve Inkala's maze with a manual Ariadne's Thread approach, I'll be expanding documentation of that. It is much less difficult than many have imagined, if choices are binary only. If a sudoku is constructed with no binary choices, then a trinary choice is possible. It would take, on average, half again as long.

Now that we actually know something here, some more comments from Max Beran. What he wrote was very common thinking at that time, so don't take this as an attack on him, please.

. . . the chains I've met and used up to now have all involved pairs whereas Eppstein's non-repetitive cycles can include cells with more than 2 candidates - the sole criterion is that there must be no more than 2 of the digit in a domain (like x-wings). I've had a look for them armed with the bilocation graph which starts looking like Spaghetti but slowly entire chunks are removed as they are dead ends or else adjacent edges have the same label.

The method has been described in ways that make it very complicated. What I did here was very simple. What he had seen sounds like 3D Medusa, which is restricted to strong links. We don't need the restriction, any logical resolution is allowed. With strong links, the chains are bidirectional, but with weak links, that link only works in one direction. (But if one does find a contradiction in one branch, the original choice will be confirmed as the opposite, and this will handle all strong links, doing the work of 3D Medusa without the restriction, so it does more. And in some examples, one goes very deep into resolutions in both branches. That, in fact, indicates a good pair choice! Sooner or later, if there is only one solution, interactions will be seen, and the longer the chains are, the better!

The discussion went on with assumptions that one needed very complicated approaches to use bifurcation. All that is needed is distincting candidate marks. I used pen from the beginning, I just liked the feel of it. So when I wanted to go into bifurcation, I needed marks that could be built up, never needing erasing, and that, it turns out, is very easy. It's easy to see and understand. I do not need to mark these complicated paths that some mark. I don't need the path, in fact, just the starting point and the results. A completed sudoku proves the path was likely to be correct (it is not a proof! Some mistakes are 50% likely to actually crack a puzzle!) But a solution is self-evident. I confirm that the alternate path is invalid by a number of logical methods, plus the argument of authority from Hodoku that tells me a candidate or resolution is wrong. Sometimes the contradiction is very easy to show.

Sometimes I find that contradiction and the other side is primitive (only a few proposed resolutions. Okay, I have one cell resolved! The rest of the markings are useless. With ink, I have ways of dealing with this, at least with one level of it. With Hodoku, I can simply choose another pair to run coloring on. It's fast and easy. Gradually -- or surprisingly often, rapidly -- the puzzle is reduced toward a BUG. Only pairs left -- until one side breaks down or it confirms the other side.

Actually the bilocation diagram was not as totally horrendous as Scott H and Tso are making out. As I suggested in my email, I did do it (greatly assisted by Angus filtering), and certainly it began like a snakes and ladders board gone crazy. But whole chunks quickly dropped out due to dead ends and identically labelled edges to the same vertex.
While the relaxation from bivalue to bilocation increases the initial number of edges, the requirement for a closed cycle more than compensates. So the problem really boils down to a sensible approach to drawing in candidate edges in such a way as you can erase them and colour them up if they look halfway hopeful. I made liberal use of highlight pens.

He simply had not figured out how to mark. He didn't have the discipline of working in ink. There was so much of an idea that one must handle candidates with pencil, which is hard to read. Because I mark candidates with dots (using the standard phone keypad position), I can add to the mark while keeping it entirely enclosed in its one-ninth of the cell space. I only need to add ink, because I cancel a candidate by drawing an X over it. And that cancels any extra marks as well for that candidate. I very quickly learned to ignore X's. I prefer to avoid them, sure. I use Snyder notation (which for me was 'double dotting') for that reason, then add in triples, then the whole set. A couple of hours ago, I identified a triple while prepping the candidate list. Keeping the candidates simple as long as possible helps with this.

A certain "Jacko" shows up and solves the puzzle with what is obviously bifurcation, and he understands the issues. He's a noob and doesn't know the language. He writes a bit about reductio ad absurdem as a logical technique. That discussion never did settle on a clear understanding of how to use bifurcation. They were suffering, my opinion, from excessive sophistication. What the hell is an "edge"? (I'll learn and it probably means something, but I know that I don't need to mark anything more than what is effectively candidate coloring. The rest can be seen directly. I carry an ink pen with me. I dislike eraser crumbs. I can work on a paper copy. Yes, if I make a mistake, it creates a mess, so the rule is, "Don't make mistakes." Like it? I do.

No guessing answers, but choosing a promising pair is not exactly a guess, though it isn't certain knowledge either. A good choice leads reliably to a solution, a poor choice may create difficulty, that's all.

It does not appear to be necessary to choose the "best pair" to work from. Any decent pair, that can be seen to generate a decent number of proposed resolutions in both directions, will generally work.

And I break rules, and I learn from it.

See also[edit]