From Sudopedia, the free Sudoku reference guide

From Sudopedia

A BR Net, or Binary Relationship Network, is an abstract mathematical description of the relationships between pairs of Boolean (binary) variables. It is not specific to Sudoku, but rather is a framework into which certain Sudoku techniques such as simple (non-grouped) AIC can be cast. Despite the immense complexity of Sudoku chain/net-type structures that can be captured in BR Nets, they are mainly interesting for what they cannot represent - including such simple patterns as Naked Triples.

Illustrative Examples

Good example: naked pair

Consider the Naked Pair 5,6@r1c7 and 5,6@r3c7, and suppose that there is a candidate 5@r6c7. (At the time of writing, this is the scenario depicted in the Naked Pair article.) We can represent this as a BR Net as follows:

Variables

A₅ = 5@r1c7; A₆ = 6@r1c7

B₅ = 5@r3c7; B₆ = 6@r3c7

X = 5@r6c7

(e.g. X is True if 5@r6c7 is the correct value, but False otherwise)

Binary Relationships

A₅ XOR A₆ - i.e. conjugate link / bivalue cell

B₅ XOR B₆ - i.e. conjugate link / bivalue cell

A₅ NAND B₅ - i.e. weak link

A₆ NAND B₆ - i.e. weak link

A₅ NAND X - i.e. weak link

B₅ NAND X - i.e. weak link

These BR Net equations have only two solutions ...

(A₅,A₆,B₅,B₆,X) = (0,1,1,0,0)

(A₅,A₆,B₅,B₆,X) = (1,0,0,1,0)

... from which we deduce that X=0, i.e. that 5@r6c7 can be eliminated.

The process of taking a set of BR Net equations and deducing eliminations or assignments is called BR Net resolution.

Bad example: naked triple

Consider the Naked Triple (678)@r1c3, (678)@r2c3 and (67)@r5c3, and suppose that there is a candidate 6@r3c3. (At the time of writing, this is the scenario depicted in the Naked Triple article.) We can represent this as a BR Net as follows:

Variables

A₆ = 6@r1c3; A₇ = 7@r1c3; A₈ = 8@r1c3

B₆ = 6@r2c3; B₇ = 7@r2c3; B₈ = 8@r2c3

C₆ = 6@r5c3; C₇ = 7@r5c3

X = 6@r3c3

Binary Relationships

A₆ NAND A₇ - i.e. weak link

A₆ NAND A₈ - i.e. weak link

A₇ NAND A₈ - i.e. weak link

(remainder omitted for brevity)

Note that because we are restricted to binary relationships (between pairs of variables), we have no way of capturing the fact that at least one of A_6,7,8 must be True (similarly for B_6,7,8). Therefore the BR Net specification admits several wrong solutions, such as ...

(A₆,A₇,A₈; B₆,B₇,B₈; C₆,C₇; X) = (0,0,1; 0,0,0; 0,1; 0)

(A₆,A₇,A₈; B₆,B₇,B₈; C₆,C₇; X) = (0,0,0; 0,0,0; 0,1; 1)

(A₆,A₇,A₈; B₆,B₇,B₈; C₆,C₇; X) = (0,0,0; 0,0,0; 1,0; 0)

... and so BR Nets fail to force the elimination of 6@r3c3 (X=0).

Formal Description

Formally, a BR Net is a set of n>1 Boolean variables and the n(n-1)/2 pairwise Good Relationships Lists (GRLs) between them.

The GRL between a pair of variables X and Y describes which of the four combinations, (X,Y) = (0,0) or (0,1) or (1,0) or (1,1), is allowed. For example, the logical formula X NAND Y corresponds to the GRL {(0,0),(0,1),(1,0)}, and the formula X IMPLIES Y corresponds to {(0,0),(0,1),(1,1)}.

It is easily seen that there are 16 different types of GRL. However, if we assume that a BR Net is specified only from variables whose values are unknown, none of which are pairwise inconsistent, then only 7 of the 16 GRLs will be used in a BR Net specification:

{(0,0),(0,1),(1,0),(1,1)}	:	X XOR Y
{(0,0),(0,1),(1,0),(1,1)}	:	X OR Y
{(0,0),(0,1),(1,0),(1,1)}	:	X EQUALS Y
{(0,0),(0,1),(1,0),(1,1)}	:	X IMPLIED BY Y
{(0,0),(0,1),(1,0),(1,1)}	:	X IMPLIES Y
{(0,0),(0,1),(1,0),(1,1)}	:	X NAND Y
{(0,0),(0,1),(1,0),(1,1)}	:	unrestricted

A BR Net specification will typically include "good" relationships that are, in fact, unattainable due to restrictions on other variables. For example, the three GRLs (A OR B), (A NAND X) and (B NAND X) together force X=0: so the "good" relationship A=0,X=1 (from A NAND X) is unattainable. A GRL is said to be refined if it consists only of attainable relationships; otherwise it is unrefined.

A BR Net is said to be resolved if all of its GRLs are refined; otherwise it is unresolved.

If the GRLs in a BR Net specification force the value of any variable then, when the BR Net is resolved, that value will be revealed in the refined GRLs. To illustrate: the refined GRL for (A,X) in the previous example will be {(0,0),(1,0)} indicating that A's value is undecided but X's value must be zero. Similarly, if the GRLs in a BR Net specification are inconsistent (i.e. have no solution) then, following BR Net resolution, this will be revealed by the presence of refined GRLs that are empty.

Resolving a BR Net

This section describes two approaches to resolving a BR Net in time polynomial in n, the number of variables. Note, however, that use of the term "BR Net" does not imply any particular resolution algorithm: BR Nets themselves are merely specification frameworks, not resolution methods.

Triangle resolution

Define a triangle to be three variables and the three GRLs between them. A BR Net with n variables contains n(n-1)(n-2)/6 triangles and each of these is a miniature BR Net in its own right. Thus, we can talk about triangles being resolved.

It should be clear that if a BR Net is resolved then so are all of its triangles. Perhaps surprisingly, the converse is also true (proof here), leading to the simple triangle resolution algorithm given below:

loop {
  find an unresolved triangle
  if none, stop
  else, resolve that triangle
}

2-SAT algorithms

BR Net specifications are 2-CNF formulae, and vice-versa; therefore 2-SAT algorithms can be brought to bear on the problem.

Specifically, a BR Net on n variables can be written as a 2-CNF formulae with <4n clauses. The truth or otherwise of any variable pair assignment can be tested in linear time (e.g. with the strongly-connected components algorithm of Aspvall et al - here), resulting in full BR Net resolution in time O(n³).

In most applications we are not interested the True/False status of variable pairs, but rather of single variables. As above, 2-SAT methods can achieve this in time O(n²). Even allowing for the intricacies of strongly-connected component calculations, this is likely to be substantially quicker than triangle resolution on all but the smallest problems.

Relevance to Sudoku

The natural correspondence of Sudoku puzzles to BR Nets is to take the pencilmarked puzzle and treat each candidate as a variable and each weak, strong, conjugate or implication link between candidates to be a GRL (weak=NAND, strong=OR, conjugate=XOR). This construction and its subsequent resolution, though tedious and time-consuming, still "only" takes time polynomial in the size of the Sudoku grid. Thus, since Sudoku is NP-hard (for grids of arbitrary size), this type of BR Net cannot possibly solve all Sudokus.

More generally, no polynomial-time BR Net construction can yield a network of GRLs that solves any Sudoku puzzle (of arbitrary size). For example, it is a polynomial time exercise to generate implication streams for each candidate in the whole grid which, when captured in a BR Net, can then be resolved simultaneously (again, in polynomial time). Whilst this massively-parallel depth-1 trial-and-error exercise seems like it should be very powerful, the mere fact that BR Net resolution can derive all the implications "quickly" means that it cannot possibly be a universal Sudoku solving technique.

The main reason that BR Nets are insufficient to solve all Sudoku puzzles would seem to be that they cannot deal with grouped nodes: for a start, deriving all possible grouped nodes is an exponential-time problem; and secondly, BR Nets have no way of capturing the fact that if a grouped node is True then at least one of its members must also be True. This goes some way to explaining why the more complicated AIC, Nice Loop, XY-Chain, Forcing Net etc solutions invariably make use of cleverly-chosen grouped nodes.

Reference

• Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert E. (1979). "A linear-time algorithm for testing the truth of certain quantified boolean formulas". Information Processing Letters 8 (3): 121–123.