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.
You 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.
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.