A flower?

foxglove · Posted: Wed Mar 08, 2006 11:23 pm Post subject: A flower?

Paths, trees and flowers was the title of a breakthrough paper by Edmonds (1965) where some particular sub graphs he named blossoms were used in solving the “Maximum Cardinality Matching Problem” in general graphs.
It just happens that blossoms can be used as a very general structure that includes a great part of the known techiques for solving sudoku puzzles, from naked/hidden pairs to finned X-wings to super coloring and I think in general they are called XY cycles. (Corrections appreciated)
Excluded are: Swordfishes with more than 2-2-2 candidates. Bifurcations. Uniqueness tests.
The study and classification of these blossoms will certainly lead to the naming of more simple patterns and techniques. Or simplify some of the current confusion. (I guess)
Make a graph of candidates and join them with an edge if they are in some relation (same row, column, block or cell)
A <b>matching</b> is a graph where no vertex has more then one edge.
Here we restrict matching edges to "strong links" : where the two vertexes of the matching edge are the only two left candidates in a relation. Or edges in the "bivalue/bilocation plot"
Even with this restriction, (in most cases) in a sudoku without any singles there will be several possible matchings where some of the strong edges belong to one or another different matching. The non matching edges can be any edges.
An alternating path or cycle is a path/cycle where only the even (or odd) edges belong to M.
A blossom with respect to one of those matchings, <b>M</b> is an odd alternating cycle on
say 2k + 1 vertices containing k edges of M. The unique vertex of the cycle
with no edge of M in the cycle incident to it is called the base of the blossom.
Now comes the funny part:

foxglove

An example of classification based on flowers:

Length of the cycle containing the flower (L) = 3: a locked pair.

Is there an edge between the two vertexes connected to the base? Then the cycle is continuous.
L = 5, same digit, continuous : X-Wing
L = 5, same digit , discontinuos: Turbot
Here I can already hear people screaming. But this is what I mean maybe flowers can help simplify classifications.
Is it an X-wing with a fin or a turbot?

L = 5, different digits, matching edges in the same cell (between different digits)
XY Wing

L > 5
All the edges not belonging to the matching are strong?
same digit : Coloring.
different digits : super coloring