SudoCue - Eureka Notation

This page explains the use of Eureka Notation for Double Implication Chains. It was last updated at September 26, 2006. Eureka Notation is used in several advanced solving techniques explained in the solving guide.

Introduction

Many advanced solving techniques rely on chains of candidates, linked together to propagate implications from the first node to the last node in the chain. The purpose of such a chain is to prove that a contradiction exists for the first candidate in the chain. A Double Implication Chain (DIC) works in 2 directions. By many Sudoku players, it is considered more elegant than a chain that operates in a single direction. To be a DIC, the complete chain must be reversable to deliver the same proof. Eureka Notation is a simple set of rules to write these DICs in a compact sequence.

True or False

Logic can only be used when we can write predicates which are either True or False, so we need to find a way to express the status of candidates in these terms.

P = True

Candidate P belongs to the solution. A common way to write such a predicate is the format: Cell=Digit.

P = False

Candidate P does not belong to the solution. A false predicate is also written in the format: Cell<>Digit.

Links

When two candidate belong to the same constraint, they interact with each other. Each cell is a constraint, because only one of its candidates can be True. Each house has 9 Unit Constraints, one for each digit, because only one of the cells in that house can contain that digit. Any pair of candidates that share a constraint are linked. There are 2 types of links: Strong Links and Weak Links. A strong link exists when the pair of candidates are the last 2 remaining candidates in the constraint. A cell with only 2 candidates is called a Bivalue Cell. A unit constraint with only 2 candidates is called a Bilocation Unit. The strong link tells us that one of the candidates must be true, and the other one must be false.

When there are more than 2 candidates left in a constraint, any pair of candidates in that constraint are weakly linked. They cannot both be true, because that would violate the constraint. However, they could both be false, because there are other candidates left to satisfy the constraint. A weak link is less powerful than a strong link, but they can be very useful in chains.

Inference

In Sudoku, we use the term inference to describe the logical deductions we can make from the interaction between linked candidates. There is strong and weak inference. A strong link can cause both types, but a weak link can only cause weak inference. Inference always has the same effect in both directions, so we speak of inference between candidates, and not from one candidate to another.

Weak Inference

(P=true => Q=false) & (Q=true => P=false)
¬(P ∧ Q)
P-Q

The first line shows the definition in plain logic. The second line is a formal mathematical notation. Because chains are often written in plain text, these mathematical operators are not always available, and many people do not understand them. In Eureka Notation, the dash ‘-’ character is used as a symbol for weak inference. The third line tells you exactly the same as the previous, but it is more compact and easy to use in a chain.

Strong Inference

(P=false => Q=true) & (Q=false => P=true)
(P ∨ Q)
P=Q

Strong inference is represented by an equal sign ‘=’. This may be a little confusing at first, because a strong link causes P and Q not to be equal. Just look at it as 2 lines connecting the candidates. Only strong links can cause strong inference. Please notice that this is pure logic. We are not making statements about P or Q individually, but only about their interaction. When you have no recent math experience, you may have some difficulty understanding this abstraction.

Alternating Inference

Double Implication Chains can be constructed when we use strong and weak inference in an alternating sequence. Take this example:

P-Q=R-S

Because the inference alternates, the implications can travel all the way from the first node to the last node in the chain. The main purpose of the chain is to establish a link between the first and the last node. These are the only 2 we use for further deductions. In many chains, the first and the last node are the same candidate. We call these chains Loops.

P-Q=R-S=T-U=V-P

This is a short loop, representing an XY-Wing. When P=true, Q=false, R=true, S=false, T=true, U=false, V=true, P=false. There is only one possible conclusion: P must be false, because it eliminates itself at a distance.

Candidate Notation

We cannot use P and Q to represent specific candidates. Therefore we must use a notation that allows us to locate the candidate in the grid. Each candidate belongs to a cell and represents a digit. Cells are usually named by their coordinates in the grid. r3c6 is the cell at row 3, column 6. For the candidate, we place the digit in parentheses before the cell name. (5)r3c6 is the candidate for digit 5 in cell r3c6. Here is an example of an XY-Wing:

(4)r4c2-(4)r5c1=(6)r5c1-(6)r1c1=(3)r1c1-(3)r2c2=(4)r2c2-(4)r4c2

Even with the short inference symbols, the chain is pretty long. To overcome this problem, we use contraction to shorten the chain. When multiple candidates of the same cell are subsequent nodes in the chain, then we may place the digits for those candidates between a single set of parentheses. The inference symbol is then placed between those digits.

(4)r5c1=(6)r5c1

is contracted to

(4=6)r5c1

Now the XY-Wing can be written in a more compact format:

(4)r4c2-(4=6)r5c1-(6=3)r1c1-(3=4)r2c2-(4)r4c2

Multiple Candidates

Chains can often be used to provide similar proof for multiple candidates. These only appear at the beginning and end of the chain. We can add these extra candidates to the chain when we separate them with a pipe ‘|’ symbol. Here is an example:

(4)r4c2|(4)r6c2-(4=6)r5c1-(6=3)r1c1-(3=4)r2c2-(4)r4c2|(4)r6c2

When alternatives are followed by a inference symbol, any of the alternative candidates will propagate the effects. When a inference symbol precedes the alternatives, all alternative candidates are affected in the inference. In the example, when either r4c2 or r6c2 contains digit 4, the chain tells us that both r4c2 and r6c2 cannot contain digit 4.

It is possible to contract multiple candidates, but only when they represent the same digit and share a row or column. The alternatives can be contracted in the following way:

(4)r4c2|(4)r6c2

is contracted to

(4)r46c2

The pipe symbol is dropped when we apply this type of contraction. It no longer has any purpose.

Conclusion

A chain is of no use if we cannot draw any conclusions from it. After all, we want to use them to solve our Sudokus. The chain itself is used as the proof for our conclusion. A double arrow separates the chain and the conclusion, which must be written as a true or false predicate. Here is our XY-Wing example again, with its conclusion:

(4)r4c2-(4=6)r5c1-(6=3)r1c1-(3=4)r2c2-(4)r4c2 => r4c2<>4

This provides us with enough information to remove candidate 4 from r4c2.