The main result of this paper is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints and all constraints are even Δ-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec.
Furthermore, we extend the tractability result to a larger class of Δ-matroids that we call stabilizable. Our method works by calling the algorithm for even Δ-matroids polynomially many times. We then show that stabilizable Δ-matroids cover classes that were known to be tractable before, namely co-independent, compact, local and binary.