Sudoku Definitions, Terminology and Glossary

This page is nothing but a reference page for the sudoku blog. If

  • The definition you seek is not here
  • The definition you find is not clear
  • Kindly comment below
  • To allow me to know
This page, like the interstate highway system, is always under construction. Help me pave a precision sudoku blog.




General definitions

Almost Locked Set
A set in a common large container with 1 degree of freedom
Boolean variable
Any statement limited to two values. Usually, {TRUE, FALSE}.
candidate
A potential number in a cell
container
A defined partition of the Sudoku puzzle. A cell, box, row, or column.
degrees of freedom
Consider a set of cells in a common large container:
  • Almost Naked set with (n-m) degrees of freedom
    • A set of n cells limited to m candidates
  • Almost Hidden set with (n-m) degrees of freedom
    • A set of n candidates limited to m cells
depth
Number of native strong sets used to justify an elimination(s) (Sudoku only)
elimination
The exclusion of a candidate from a location
forbidding matrix
An n x n table that transparently illustrates an elimination(s)
house
container
large container
Box, Column, or Row.
native
adjective - Appearing within the current possibility matrix.
native strong set
Given the current possibility matrix, one of the following strong sets:
  1. One candidate in one large container
  2. One cell
native weak set
(given only a blank puzzle grid) One of the following weak sets:
  1. One candidate in one large container
  2. One cell
continuous nice loop
A wrap around forbidding chain
ntuple
A set with zero degrees of freedom. (Thus a hidden or naked pair, triple, etc.)
possibility matrix
The puzzle grid decorated with the remaining possible candidates for each cell
sees
Forbids by sharing a container with
strength in cell - also called naked strength
A reflection of the unwritten sudoku rule:
  • A solved sudoku cannot contain a cell empty of all candidates
strength in location - also called hidden strength
A reflection of the written sudoku rule:
  • A solved sudoku cannot contain a large house empty of any candidate
strong set
noun - A set of Boolean variables such that at least one is true
strong link
The logical operator OR (union). The endpoints of a strong link form a strong set
weak set
noun - A set of Boolean variables such that at most one is true
weak link
The endpoints of a weak link form a weak set
wrap around forbidding chain
A forbidding chain is called wrap around when the endpoints of the chain form a set that is both strong and weak.
Unique Possibility
A candidate that is a singleton in a container
UP
short for Unique Possibility or Unique Possibilities



Symbols

==
Binary strong link. (A == B) means (A OR B). Used in forbidding chains.
--
Binary weak link. (A -- B) means ((notA) OR (notB)). Used in forbidding chains.
%
because it is a singleton in (container x). Used to describe a Unique Possibility.
<>
does not equal
=>
implies
~
not
ab1
shorthand for a1,b1
{}
Used in forbidding chains to contain a Boolean variable that partitions more than one native strong set
Subscripts
Used within forbidding chains to help clarify the partioning of a native strong set (strong inference set) that has more than one possible distinct partition. Possible examples:
  • A cell with 3 or more possible canidates
  • A candidate with 3 or more possible locations within a house.



Technique definitions

Unique Possibilities
Finds singular strengths in any container
Locked Candidates
Looks at strength in location of one type of candidate in one large container to deduce strength of that candidate in location
Naked Pairs, Triples, Quads,...
Looks at strength of N candidates in N cells to deduce strength of those N candidates in N locations within a large container(s)
Hidden Pairs, Triples, Quads,...
Looks at strength of N candidates in N locations within a large container(s) to deduce strength of those N candidates in N cells
Xwings, Swordfish, Jellyfish, Squirmbags
Looks at strength of one type of candidate in N rows(location) to deduce strength of that candidate in N columns(location) OR vice versa
Unique Rectangles
Looks at potential symmetrical overlapping strength of candidates in location to deduce strength of any type
Coloring
Looks at strength of one type of candidate in location to deduce strength of that candidate in location
Y wings
Looks at strength of 3 cells containing exactly 2 candidates each. Considers 3 types of candidates. Deduces strength of one of those candidates in location
Y wing style
Looks at 3 native strengths of any type to deduce strength(s) of any type
Forbidding Chains
Looks at any number of strengths of any type to deduce strength(s) of any type
Advanced Forbidding Chains
A forbidding chain that uses a technique as a Boolean variable
Almost Locked Sets
In most locations, considers two sets with 1 degree of freedom each. Uses a weak link between them (relative location) to deduce strength. More generally, a forbidding chain that uses one or more ntuples as a Boolean variable.
Alternating Inference Chain
A Forbidding Chain



Notes

  • Native weak links are independent of the possibility matrix.
  • Native strong links are dependent upon the possibility matrix.
  • The operators, == and --, are not dependent on order. Thus, (A==B) is equivalent to (B==A)
  • (A forbids B) is equivalent to (A -- B), and therefor also (B forbids A)
  • (A -- B == C) => (A => C)
  • Strong and weak are not mutually exclusive properties
  • A set that is both strong and weak contains exactly one truth
  • In most forbidding matrices, each row is a strong set
  • Other sudoku sites may needlessly restrict the definition of
    • strong
    • weak
    • coloring
    • forbidding chains
    • depth
    Please endure the definitions herein
  • Puzzle coordinate system used here can be found at the blog introduction page.



Links to recommended sites

12 Comments
Indicate which comments you would like to be able to see

Steve  From Ohio    Supporting Member
Check out my page


Please feel free to suggest the addition of anything that you think I should include on this page. If you are here and have a question you thought this page would answer, but it does not - please let me know.

kateblu  From Madison WI    Supporting Member
Check out my page
Steve, when I first saw the term 'Boolean variables', my eyes did indeed glaze over in memory of all the symbolic logic that I never learned. I'll print off these definitions and then go back to your piece on FCs. My gut says that when you have two or more possibilities, some of your techniques - especially coloring - give one a chance at an educated guess. For example, a puzzle may have only two possible configurations of a all occurences of a given number throughout the entire possibility matrix (a tautology?). It is relatively easy to try one or the other and this will often lead to unraveling the entire puzzle. I like to try the possibility that eliminates the possibilities of an obvious unique rectangle. I can go back after the fact and determine why one choice is right or wrong but often I can't see that before I make an initial try. Coloring really helps but it's not always physically possible.
Steve  From Ohio    Supporting Member
Check out my page
Hi Kate!
Mastering these technique certainly does allow one to make better educated guesses.

My goal, however, is to move beyond guessing into the realm of certainty. Nevertheless, if one wants to solve a puzzle most quickly, then guessing may at times be the most time efficient path.

When looking for forbidding chains, the situation that you described - that one particular candidate is limited to perhaps only two possible states on the entire puzzle grid - is often a great place to focus the search.

Forbidding chain search parameters are perhaps the trickiest topic that will be discussed in this blog.
Sharkie  From Chicago IL
Steve,

I'm struggling with the definition of a strong link: 'A OR B', or expressed in words as 'at least one is true'.

At least one implies: at least one or possibly both. From what I understand about strong links both can never be true. It's either one or the other, so the definition should be: 'A XOR B' (exclusive or) - correct?

I don't have problem with weak link definition 'at most one'. At most implies either one of them is true or none. This can happen for any situation where you have 3 (or more) possibilities in a group. For any 2 possibilities you can say 'at most one', if both are false, then the 3rd can still be true.

But for strong links, I just don't see the 'at least' part where both could be true.

Please explain, it's quite possible I'm misunderstanding something since I'm still relatively new to sudoku proofs.
Steve  From Ohio    Supporting Member
Check out my page
HI Sharkie!
Absolutely positively do not, ever, think of a strong link as exactly one is true. This is a common misinterpretation, spread all over the web.

It may be the case that Native Strong Links are always also weak, but.... we are not interested in only native strong links. In order to really advance with forbidding chains, the definition I give here for strong links is the only correct one.

Here is the thought process: If you are looking at the puzzle, saying 'at least one is true' is more general than 'exactly one is true'. Even though native strong links are never both true, the proven links could be. For this reason, if you are to generalize the idea, it makes no sense to restrict strong links to exactly one.

On the Y wing styles page, there is an example under the heading 'very common Y wing style example' involving two cells 67, and a strong set of 6's. In that example, the forbidding chain proves that at least one of the two 7's must be true in those cells. In fact, both are true.
Steve  From Ohio    Supporting Member
Check out my page
Hi Sharkie again!

In the expression:

A == B -- C == D,

If A is true, even if B is false, C could still be false, and D be true. So, if we restrict A == B to meaning exactly one is true, we cannot conclude A == D.

On the other hand, if we do not restrict the definition in this manner,
If A is true, Then A == D is valid.
If A is false, then B must be true, then C must be false, then D must be true, so A == D is still valid.

The example I pointed you to is just one of many, many such situation whereas one can prove at least one is true, but in fact both conditions are true.

Hopefully this makes sense. If not, do not hesitate to ask for futher clarifications.
Jyrki  From Finland
About the formula you use to calculate the difficulty of a sudoku. Are the details secret?
Is it difficult to describe?
01/May/07 6:34 AM
Steve  From Ohio    Supporting Member
Check out my page
Hi Jyrki!

Neither.

I assign a difficulty rating to each step. The proof rating is then the sum of each step difficulty.

Any step that requires a deduction to make an elimination is counted.

Each step is evaluated on exactly one parameter: The number of strong inference sets considered.

Let D be depth = number of strong inferences considered.

.01 * ((-1)+2^D))

Thanks for asking!
01/May/07 8:39 AM
Jyrki  From Finland
Steve, Thanks for the explanation. I will scan your blog for examples to make this clearer to me,
but a quick question checking my understanding.
Given that in a forbidding chain every other linkage is strong, does this mean that in such a step D = one half of the number of links in the fc?

As your wording indicates this is a function of a proof/solution rather than of the puzzle itself.
That's ok as anything else probably has prohibitive computational complexity.

I also get the feeling that this rating function is designed primarily to be used only on 'tough levels'. IOW all the easy, medium and may be also hard puzzles here then get rating zero? Yet there difficulty varies because from the point of view of a human solver also the number of various ways to make progress plays a crucial role. Somehow it doesn't feel right that if the only way to make progress is to spot a couple of locked canidates and hidden groups to get a UP, my efforts are rewarded by a round zero rating :-)

I do understand that this formula has the significant merit of objectivity. Do you happen to know, whether this formula is in universal (or near universal) use? The reason I'm asking is that it made small news here a couple of months ago, when a Finnish applied mathematician claimed to have designed 'the toughest sudoku puzzle in the world'. The newspaper article didn't explain the formula he used for deciding whose puzzle is the toughest (no surprise). In the article he was quoted for having said that the solution required resorting to a combination of 8 links twice. I once had the opportunity to leaf thru his book and the formula may have been closely related to yours. The newspaper article did include the sudoku, and I admit that I couldn't make any progress with it (apart from a single initial UP),
so it is a tough one, no doubt about that!

I was just left wondering if there is a universally accepted method for quantifying whose puzzle is the toughest. Otherwise such claims are just boasts/marketing hype/whatever. I do admit that any numerical difficulty rating (for the type of puzzles I can solve myself) would most likely be very subjective and have features easily rebutted by more knowledgeable people.
01/May/07 4:39 PM
Steve  From Ohio    Supporting Member
Check out my page
Hi Jyrki!

Sorry it took so long to reply!
First: my rating system is not employed by any other being that I know of.
Secondly: You are quite correct that it utterly fails to differentiate between puzzles that are solved merely by UPS. This is a fault, no doubt.
Finally: The rating system is nothing but an approximation of difficulty the way that I see things, but it does not even accurately reflect how difficult a particular puzzle feels to me. However, when I have attempted to concoct a different rating system, it seems to be too complex. Since any rating system will be arbitrary, I have not found that improving the rating system would be a likely fruitful enterprise.

13/Jun/07 3:58 PM
jim chang  From florida, USA
I am learning. Your blog does a very job in explaining difficult/confusing ideas.
31/Jul/07 2:07 AM
Bud  From Florida
Check out my page
Hi Steve,
I am familiar with Kraken fish patterns, but when I see terms like Kraken Loop, Kraken Column, and Kraken Cell I am totally lost. What I need is a precise definition of these terms. My attempts to google these terms simply lead me to examples. I can analyze examples of Kraken loops but I still have no idea why a particular loop is called a Kraken loop. Surely if a term is used, it can be precisely defined. Other wise it should not be used.
14/Jul/10 11:08 PM
Please Log in to post a comment.

Not a member? Joining is quick and free. As a member you get heaps of benefits.

Join Now Login