```#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Exact set cover by the dancing links algorithm

jill-jenn vie et christoph durr - 2014-2018
"""

# snip{ liens-dansants-cell
# pylint: disable=missing-docstring
class Cell:
def __init__(self, horiz, verti, S, C):
self.S = S
self.C = C
if horiz:
self.L = horiz.L
self.R = horiz
self.L.R = self
self.R.L = self
else:
self.L = self
self.R = self
if verti:
self.U = verti.U
self.D = verti
self.U.D = self
self.D.U = self
else:
self.U = self
self.D = self

def hide_verti(self):
self.U.D = self.D
self.D.U = self.U

def unhide_verti(self):
self.D.U = self
self.U.D = self

def hide_horiz(self):
self.L.R = self.R
self.R.L = self.L

def unhide_horiz(self):
self.R.L = self
self.L.R = self
# snip}

# snip{ liens-dansants-cover
def cover(c):            # c = heading cell of the column to cover
assert c.C is None   # must be a heading cell
c.hide_horiz()
i = c.D
while i != c:
j = i.R
while j != i:
j.hide_verti()
j.C.S -= 1   # one fewer entry in this column
j = j.R
i = i.D

def uncover(c):
assert c.C is None
i = c.U
while i != c:
j = i.L
while j != i:
j.C.S += 1   # one more entry in this column
j.unhide_verti()
j = j.L
i = i.U
c.unhide_horiz()
# snip}

# snip{ liens-dansants-exploration

[docs]
"""Exact set cover by the dancing links algorithm

:param size_universe: universe = {0, 1, ..., size_universe - 1}
:param sets: list of sets
:returns: list of set indices partitioning the universe, or None
:complexity: huge
"""
header = Cell(None, None, 0, None)  # building the cell structure
col = []
for j in range(size_universe):
for i, _ in enumerate(sets):
row = None
for j in sets[i]:
col[j].S += 1               # one more entry in this column
row = Cell(row, col[j], i, col[j])
sol = []
return sol
return None

# pylint: disable=missing-docstring
if header.R == header:     # the instance is empty => solution found
return True
c = None                   # find the least covered column
if c is None or j.S < c.S:
c = j
j = j.R
cover(c)                   # cover this column
r = c.D                    # try every row
while r != c:
sol.append(r.S)
j = r.R                # cover elements in set r
while j != r:
cover(j.C)
j = j.R
return True
j = r.L                # uncover
while j != r:
uncover(j.C)
j = j.L
sol.pop()
r = r.D
uncover(c)
return False
# snip}
```