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.
