Pulling Rank


This post turns attention to Sudoku  techniques based on the concept of rank.  I’ve seen references to this concept in many places, but nowhere else as clearly described as on the website www.SudokuOne.com, under the title of general logic. I don’t subscribe to that title, so I’ll just call it rank theory .  Similarly, until l’m told the identity of the author of “A General Logic of Sudoku”, I’ll refer to him or her as SudokuOne.  Here I’m providing more careful definitions of rank theory than I get from SudokuOne or anyone else.  Maybe you can help me out there.

Rank theory defines candidate elimination rules based what SudokuOne calls truths.  A truth is a set of candidates that see each other, and are known to contain exactly one true candidate.  Hence the set of candidates of one number within a unit, i.e. a box or a line, is a truth. The set of all candidates in a cell is also a truth.  The common “truth” feature allows cells, lines and boxes to be treated equally in rank theory.  A slink is a two-candidate truth. The two candidates of a strong link see each other, and one of them is true, but not both.

sudokuOne ex 1You may have seen this way to visualize Sudoku constraints in solver forum posts. Unit and cell truths are seen in 3-D by representing cell content in a third dimension above the box and line grid.  SudokuOne’s use of this drawing mechanism suggests that he or she invented it.  It reminds me of a 3-D diagram of a building’s plumbing system, so for short I’ll call it plumbing.  This plumbing shows  a rank 2 elimination of a 5-candidate in r2c2. I’ll spend the rest of this post and the next just explaining that.

Let’s start by interpreting the plumbing. The colored bars are truths, mostly slinks, with maroons in rows, and greys in columns.  The blue bars represent cell truths.  Levels of the third dimension map represent cell numbers, with connecting blocks representing candidates. Elbows without blocks are box winks. Elbow between blocks would represent box slinks.  The grey color is shadow from illumination from below and to the viewers right, but also serves as the color of column truths.

Closed sets of candidates, like naked or hidden pairs, triples, quads and quints, are not truths.  They are closed with respect to the unit containing them, and but they contain more than one true candidate.  But the set of candidates of a single number in a closed set is a truth.

The toxic sets defined by XYZ-wings, inference chains, and ALS are not truths, for two reasons: candidates of a toxic set do not see each other, and a toxic set may contain more than one true candidate.

The concept of rank is based on two sets of candidate sets.  One set, the base set, or base,  is a set of truths with no intersection, i.e. with each candidate of the base in only one truth.  The base does not have to include all candidates, or all candidates of a number.  An associated collection of candidate sets,   the cover, contains all of the base candidates, and may have base candidates in their intersections.   All candidates of a cover set see each other, but a cover set does not necessarily contain a true candidate.

Returning to the plumbing above, the white bars represent cover sets.  SudokuOne refers to cover sets as links.  I’ll stick with cover sets or cover,  reserving links for the fundamental notion of slinks and winks.

The rank of a (base, cover) pair is defined as the difference between the number of cover sets and the  number of base sets

rank = #cover sets – #base sets

A startling fact about a rank of zero is that candidates in the cover, but not in the base, can be removed! Call it the rank = 0 rule.

Regular Sysudoku readers may recall that a I covered an application of the rank = 0 rule in the  case of mutant fish in the  post of April 4, 2012, Unraveling the Mutant Fish.  In that little adventure into rank theory,  I was after the mystery of how boxes and lines could be treated interchangeably, and how the rank = 0 rule, widely quoted but never proved in my sources, could be justified.  After verifying that the rank = 0 rule applies directly to regular fish, and applying the fishing logic to boxes as well, I began looking for mutant fish.

On justifying  the rank = 0 rule, I discovered many cases of the rule, as applied to boxes and lines, could be verified by a grouped X-chain ANL. But then I found a case where this could not be done.  So it became an interesting, but blind, alley.  Under blog posting duress, I proved the rank = 0 rule for myself.  My proof and SudokuOne’s proof are nearly identical and are quite simple:

1. Each base set, atruth,  contains one true candidate.

2. Every base candidate is contained in a cover set,  so every true base candidate is contained in one.

3. Since all cover set candidates see each other, a cover set can contain no more than one true candidate.   It may contain none.

4. At rank = 0,  every cover set must contain one of the base’s true candidates.

5. Any candidate in the cover, but not in the base, sees a true candidate, by 4, but cannot be one.  Remove it.

The only difference between this proof and SudokuOne’s is that SudokuOne never actually defines a cover set (or link).  But his proof implies the mutual seeing property and requires nothing more.

A base has many possible covers.  As we discovered with mutant fish, the trick is to find a permissive base and a competent and useful cover.  Since the mutant fish post,  I haven’t found any.  I drew up a template with a single X-panel, with right sized box and line shapes on the side, for identifying mutant fish.  I tried hard, with the extreme puzzles I had then, without success.  The problem is I had no systematic way of filtering the search down to human proportion.  This may be a problem with the general rank = 0 rule as well.

SudokuOne applies rank theory for every removal, and describes the rank theory equivalent to many  advanced methods of this blog.  We can hope to understand how to recognize and apply rank theory by relating it to the advanced methods we know.

First, let’s convert a rank 0 removal example from SudokuOne into sysudoku graphics.  The example below shows  how bases and covers are commonly rendered in 2-D.  We have overlapped that diagram from www.sudokuone.com with a sysudoku grid of the same logic.

sudokuOne 3

The SudokuOne example shows  three base sets and three cover sets, two units and a cell on each side. The base truths are the West box 5 slink, the row 4 3-slink, and cell r6c8 bv. The cover sets are row 6 5-candidates, the column 8 3-candidates and cell r4c1. Why were these selected?  The base units contain single slinks or single bv.  This is why they are guaranteed to contain a true candidate 3 or 5.  The cover sets are a box and two lines covering the 3 and 5 candidates.  In sysudoku speak,  we have a nice loop with toxic adjacent members and victims that see too much.

The sysudokie human solver can expect to find this nice loop after drawing AIC hinges, and noticing the 35-chain.  The five removals would be obvious, and so would the 3 removals, once the nice loop is constructed and slinks and winks are examined, one at a time.

A similar pattern recognition strategy might apply to finding base and cover sets, but I would say that no advantage is demonstrated for rank =0 theory by SudokuOne’s example.

I have mentioned the possibility of extending XY-chains with slinks and X-chains, but I’m sure that I have missed many.  The X-panels and bv map offer little help for this task.  Later in the order of battle comes  the constructing of AIC on the grid, a process that offers many more possibilities. Base and cover construction seems to involve just as many possibilities, but seems to lack an organizing principle such as the AIC.

I do have one further insight into my failure with mutant fish search.  I was confining myself to boxes and lines, and excluding cell base and cover sets.

There’s more in the www.SudokuOne.com general logic page.  Next time I’ll go for rank > 0, and a sysudoku version of the rank = 2 plumbing example above.  For homework, you could demonstrate your understanding of beginning rank theory notation by beating me to it.

Advertisements

About Sudent

My real name is John Welch. I'm a happily married, retired professor (computer engineering), timeshare traveling, marathon running father of 3 wonderful daughters and granddad to 7 fabulous grandchildren. The blog is about Sudoku solving. It covers how to start, basic solving to find candidates efficiently, and advanced solving methods in an efficient order of battle. It is about human solving methods, not computer solving.
This entry was posted in Barker, Expert Reviews, Extreme Solving and tagged , , , . Bookmark the permalink.

5 Responses to Pulling Rank

  1. Big says:

    I believe the author is Alan Barker email = rab@buddybb.com. I received an email from him on dec 13 2012 to confirm this. I had been looking forward to Denis Berthier also addressing his approach and I believe some day he will. I am playing catch-up and am interested on your take on his approach. You have spent a lot of time on your blog and am wondering why you never found the time to be involved in any of the advanced sudoku forums. Denis Berthier does and I think that gives him more credibility with advanced players. You have a lot to offer and I think that would greatly increase your readership. Just a thought – Blessings, Richard G.

    • Sudent says:

      Thanks, Richard, for the info and good advice. I did a few posts on Berthier concepts and sent you references earlier. On the forums, I still consider my audience to be ordinary solver folks. I’m not inclined join the forums. Denis and Alan are really computer solvers and I’m strictly on human solving. As to readership, look for some big news for human solving to end the year. Advanced players are already watching, but many of those who can profit more will be finding the blog soon. I just hope I can get them to read through the basic and advanced posts. Thanks also for the generous endorsement.

      • Big says:

        Denis Berthier would disagree with you, even by what he says in his book, but I am inclined to agree with you. As a minimum you would have to be very stubborn and/or with at least the aptitude of an engineer/geek to work through his book. I am sure you would agree there is a continuuom of what we call rigour. Frankly I think DB is a little too high for even advanced players and does lead to some mutual frustration with him and others on the various forums where he posts. While I disagree with you on some of the ways you name things in general I like your approach. There are a few others I look at, like Prof Robert Hanson at St. Olaf College. Ultimately I seem to always come back to your blog. I am REALLY looking forward to the day – I hope it is coming? – when you publish a “dead tree” book on the subject. As you know there is another engineer out there doing a fairly impressive effort – Phillip McCollum – “Sudoku for Everyone” but I do not see anything new or innovative there – but it is a nice index and links to what is out there in Sudoku Land so probably should be commended for that. I am wondering if he has a link to your blog? If not he should! I bought “Taking Sudoku Seriously” by a couple of mathematicians – Rosenhouse and Taalman – but was basically disappointed. If I remember correctly you were a computer engineering prof. which I think helps you be more ‘down to earth’ (for lack of a better term) Blessings, Richard

  2. GUENTER TODT says:

    Thank you for your detailed explanation. Maybe I can give some light to the 3D-representations of truths and links. You define a truth to be a set of candidates that see each other. Strictly speaking this is not mathematically correct. Of course it is clear what is meant, and it is allowed to say that a candidate is an element of a truth or belongs to a truth. But a consistent definition in set theory must be a little bit more complicated. The easiest way would be to define a truth to be a special set of triples (x,y,n) where x, y, n are natural numbers from 1 to 9. x stands for a row, y for a column and n for a candidate – without saying also given and solution numbers are included. There are 81 row truths, 81 column truths, 81 box truths and 81 cell or square truths for every Sudoku at a certain solution stage. It suffices to give four examples. The row truth R51 is defined to contain all triples (5,y,1) where 1 is a candidate of r5cy. The column truth C51 contains all triples (x,5,1) where 1 is a candidate of rxc5. The box truth B51 contains all triples (x,y,1) where rxcy is a cell of box 5 and 1 is a candidate of rxcy. The square (or cell) truth S51 contains all triples (5,1,n) where n is a candidate of r5c1.

    It is not a mystery to represent triples in a 3D-space, and there are different ways to do so. Allan Barker’s 3D-representations of truths and links are impressive because they look like a plumbing system.

    • Sudent says:

      Thank you, Guenter. Elsewhere I’ve mapped Barker plumbing into 2-D for Sysudoku readers, to illustrate its complexity. I prefer “covers” to “links” because strong and weak links between candidates are central to my extension of “seeing” beyond unit-based vision. It is not rare for a “truth set” to extend beyond a line or box by ER or other forcing chain. I don’t know if that complicates Barker’s higher rank set link theory or not. I reluctantly reject it all anyway as just another computer based solving mechanism of computational complexity beyond practical human solving. A picture of the plumbing after its discovery doesn’t change that.

      My current review of Berthier’s Hidden Logic of Sudoku is reaching a similar conclusion, without the nice visuals. On the other hand, practically enhanced human vision via office software has turned out to be surprisingly powerful.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s