Thanks to rep'nA, Red Ed, and Obi-Wahn for (lost) comments that plugged holes in the exposition.

Here is the original note, edited, but without subsequent posts from the corrupt thread.

This post will be edited to keep it up to date.

---

A Ternary Monoid for Sudoku Coloring

Introduction

A traditional 9x9 sudoku puzzle can be modeled as a multigraph with 81 vertices, one for each cell, where the edges

represent the row, column and box cell value constraints between cells. The 9 cell values are represented as the edge

colors 1 through 9. A sudoku solution corresponds to a vertex coloring of the multigraph.

Edge Types

In this model there are four undirected edge types for each of the 9 colors:

- 0-edge: No relationship.
- 1-edge: If one vertex is color c then the other vertex is not color c.
- 2-edge: If one vertex is not color c then the other vertex is color c.
- 3-edge: One vertex is color c if and only if the other vertex is not. A 3-edge is both a 1-edge and a 2-edge

(conveniently 3=1+2).

Color Induced Subgraphs

Each color induces a subgraph (a graph, not a multigraph) on the original multigraph that can be examined

independently. In particular, some edge configurations can be shown to admit or preclude the induced color on

constituent vertices. The remainder of this note assumes edges in the color induced subgraphs.

Relationship to Sudoku Terminology

A multigraph models a pencilmark grid. A color induced subgraph models a pencilmark grid restriced to one

cell value (like those for finned fish analysis.)

Edge Relationships

Two edges that share at least one vertex are adjacent. Adjacent edges can be joined to form a path. A

cycle is a path where every edge is adjacent to two other edges. The cycle size is the number of edges in the

cycle. The smallest cycle size is 3. A segment is a subset of edges that form a path. Segments of size three

(three edges) can be combined to form a new edge according to the following ternary "multiplication" table on

the four edge types:

- Code: Select all
`000 0 100 0 200 0 300 0`

010 0 110 0 210 0 310 0

020 0 120 0 220 0 320 0

030 0 130 0 230 0 330 0

001 0 101 0 201 0 301 0

011 0 111 0 211 0 311 0

021 0 121 1 221 0 321 1

031 0 131 1 231 0 331 1

002 0 102 0 202 0 302 0

012 0 112 0 212 2 312 2

022 0 122 0 222 0 322 0

032 0 132 0 232 2 332 2

003 0 103 0 203 0 303 0

013 0 113 0 213 2 313 2

023 0 123 1 223 0 323 1

033 0 133 1 233 2 333 3

For example, a segment { 1-edge 3-edge 1-edge } (denoted 131) is equivalent to a single 1-edge. 0 is the

multiplicative zero: a 0-edge in combination with any other two edges is equivalent to a 0-edge. From a coloring

viewpoint 0-edges provide zero information. The multiplicative identity element is an adjacent pair of 3-edges:

adjacent 3-edges in combination with any other edge type is equivalent to that edge type.

Ternary Monoid

A monoid is a set with an associative operation on the set elements that also contains an identity

element. Edge multiplication operates on three edges, hence ternary. The ternary operator is closed, a

monoid requirement. This particular monoid also has a multiplicative zero element.

Relationship to Coloring

Cycles are the key to extracting coloring information. Using ternary edge multiplication any odd cycle can be

collapsed into a tri-cycle (cycle of size three). The next figure shows the seven tri-cycles that provide coloring

information (the active tri-cycles).

- Code: Select all

(0) (0) (0)

/ \ / \ / \

1 1 1 1 3 3

/ \ / \ / \

*---2---* *---3---* (1)--2--(1)

112 113 233

(1) (1) (1) (1)

/ \ / \ / \ / \

2 2 2 2 3 3 2 3

/ \ / \ / \ / \

*---1---* *---3---* (0)--1--(0) *---1--(0)

122 223 133 123

(0) means that the vertex cannot be the induced subgraph color (an elimination), and (1) means that the vertex

must be the induced subgraph color (a placement). The tri-cycles 111 and 222, and any tri-cycles containing

0-edges do not provide any placement/elimination information. The 333 tri-cycle is self-contradictory and

therefore impossible in a valid sudoku. This accounts for the 10 tri-cycle forms: seven are active (provide

placement/elimination information), two are inconclusive, and one is contradictory.

The disposition of a vertex in a tri-cycle is determined by the multiplication table entry for the three adjacent edges:

- 0 => inconclusive (*)
- 1 => the vertex cannot be the induced subgraph color (0)
- 2 => the vertex must be the induced subgraph color (1)
- 3 => contradiction

and replace (0) with (1) and vice versa, and the result is a valid complementary tri-cycle. The complements

appear above/below each tri-cycle in the diagram above.

Cycle Coloring Algorithm

The cycle coloring algorithm is simple:

- Induce a subgraph for each color.
- Determine the type 1,2,3 edges.
- Combine edges into paths until odd cycles are formed.
- Collapse each odd cycle into a tri-cycle using the ternary multiplication operator. If the tri-cycle matches

one of the seven forms above then apply the color placement or elimination.

X and Y cycles

X cycles contain 1-edges and 3-edges. Y cycles contain all edge types. Even though all edge types correspond to one

color in the induced subgraph, 2-edges are typically formed by bi-value vertices in the original multigraph, and then mapped

into the subgraph. A bi-value vertex can admit only one of two colors. A single 2-edge consists of one or more edges

between bi-value vertices in the multigraph, where both endpoints contain the induced subgraph color.

2-edge construction can lead to contradictions in the multigraph (and not by cycles in the induced subgraph). These

contradictions are called y-knots.

Extension using directed 2-edges

A normal (undirected) 2-edge exhibits the 2-edge property at both vertices. For a 2-edge with vertices A and B, both

of these statements hold:

(1) if vertex A is not the induced color then vertex B is and

(2) if vertex B is not the induced color then vertex A is.

A directed 2-edge exibits the 2-edge property only in one direction (only one of (1) or (2) holds). Directed 2-edges

may be used in the coloring algorithm as long as they are not operands to the ternary collapse operator. They may,

however, be part of a tri-cycle after the last collapse. This insight was 2 years in the making and allows more puzzles

to be solved without resorting to y-knots.

The Algorithm in Action

Download my solver and run it with the -v2 option on some puzzles known to require/contain coloring, turbot

fish, kites, and or skyscrapers. The X and Y cycles are labeled, and the collapse from full cycles to tri-cycles is

denoted by "=>".

For example, this puzzle

- Code: Select all
`......5.9..7..462.....2..7......6.134.6...8.587.1......2..7.....358..2..1.8......`

contains a few y-cycles and y-knots:

- Code: Select all
`y-cycle 13 6 6a [14]-[15]>[71]-[79][89]- => [14]-[15]>[71]-`

y-cycle 16 9 5a [31]-[71][92][97]=[33]- => [31]-[97]=[33]-

denotes a Y cycle number 13 on color 6 of size 6 (6 vertices, 6 edges), and a Y cycle number 16 on color 9 of size 6.

Cycle numbers may be passed to the -Kc option to display cycles in postscript. In the cycle output, 1-edges are denoted

by "-" ([14]-[15]), 2-edges are denoted by "=" ([97]=[33]), directed 2-edges are denoted by ">" ([15]>[71]), and 3-edges are

denoted by adjacent vertex labels ([71][92]). The size for x-cycles and y-cycles includes sizes for segments hidden by

2-edges and box hinges (described below). e.g., [97]=[33] contains some bivalue edges not displayed in the

-v2 trace. -v3 lists the y-edge sizes. y-edge details are not listed by the current y-edge algorithm, mostly

for performance reasons. Cycle 16 collapses to a 112 tri-cycle: two 1-edges ([31]-[97] and [33]-[31]) and one 2-edge

([97]=[33]). From the 112 tri-cycle figure above, vertex (cell) [31] cannot be the color 9.

The y-cycle trace has a deficiency. The algorithm collapses edge segments as it progresses and must

emit hints for cycle reconstruction. In some cases the reconstruction may trace artifacts of the algorithm rather than

the actual segments from the original cycle. -v5 displays the original edge triplets (four vertices) that are

used by the reconstruction. Although the display may seem incorrect, the underlying logic is sound.

A y-knot is a contradiction uncovered by the y-edge construction algorithm.

- Code: Select all
`y-knot 1 4 6 [41]#[45]`

is y-knot number 1 on color 4 and contains 6 vertices/edges. The y-knot premise is that the first cell is not the color ([41]!=4). In

this case it leads to a contradiction at [45]. y-knots are essentially y-edges gone bad.

Pseudo Edges

The beauty of the ternary edge collapse algorithm is that only edge types matter, not how edges are derived.

2-edges show that edges need not follow intuitive paths through a sudoku puzzle grid. There are other 1-edge

derivations besides cell [rc] sees cell [r'c']. One such derivation is the box hinge illustrated by this puzzle:

- Code: Select all
`6..8352.9.89.......5219..8.92..8.7.383.9..4..41..23896.983.........7893...3.591.8`

6 47 147 | 8 3 5 | 2 147 9

137 8 9 | 2467 46 2467 | 356 14567 1457

37 5 2 | 1 9 467 | 36 8 47

------------------+------------------+------------------

9 2 56 | 456 8 146 | 7 15 3

8 3 567 | 9 16 167 | 4 125 125

4 1 57 | 57 2 3 | 8 9 6

------------------+------------------+------------------

1257 9 8 | 3 146 1246 | 56 24567 2457

125 46 1456 | 246 7 8 | 9 3 245

27 467 3 | 246 5 9 | 1 2467 8

If [79]=4 (cell r7c9 is color 4) then [78][76][75]^4 (cells r7c568 are not color 4) and one of [84] or [94] must be 4,

which implies [44]^4 and [24]^4. Hinges are traced by -v4:

- Code: Select all
`x-hinge 4 8 [79][44]`

which denotes and x-hinge on color 4 in box 8 with cells [79][44]. x-hinges are treated as normal 1-edges by the

ternary collapse algorithm. Here is the x-cycle that incorporates the hinge:

- Code: Select all
`x-cycle 1 4 6a [79]-[39][36]-[46][44]- => [79]-[46][44]-`

The cycle size 6 includes 1 for the hinge. Tri-cycle type 113 means that cell r7c9 cannot be color 4, denoted this way

in the trace:

- Code: Select all
`X1 [79]^4`

which reads: 1 X cycle elimination; r7c9 cannot be color 4.

Conclusion

The literature has few concrete (i.e., useful) examples of ternary monoids or other algebras. My original notes on this

are dated 2005-10-21 -- talk about writer's block.