# Path: tryalgo/dancing_links.py
# def dancing_links(size_universe, sets):
#     """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):
#         col.append(Cell(header, None, 0, None))
#     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 = []
#     if solve(header, sol):
#         return sol
#     return None


from tryalgo.dancing_links import dancing_links

def rv(a): return row(a) * N2 + val(a) + N4


def cv(a): return col(a) * N2 + val(a) + 2 * N4


def bv(a): return blk(a) * N2 + val(a) + 3 * N4


def sudoku(G):
    """Solving Sudoku

    :param G: integer matrix with 0 at empty cells
    :returns bool: True if grid could be solved
    :modifies: G will contain the solution
    :complexity: huge, but linear for usual published 9x9 grids
    """
    global N, N2, N4
    if len(G) == 16:              # for a 16 x 16 sudoku grid
        N, N2, N4 = 4, 16, 256
    e = N * N4
    universe = e + 1
    S = [[rc(a), rv(a), cv(a), bv(a)] for a in range(N4 * N2)]
    A = [e]
    for r in range(N2):
        for c in range(N2):
            if G[r][c] != 0:
                a = assignment(r, c, G[r][c] - 1)
                A += S[a]

# Path: tryalgo/dancing_links.py
# def dancing_links(size_universe, sets):
#     """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):
#         col.append(Cell(header, None, 0, None))
#     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 = []
#     if solve(header, sol):
#         return sol
#     return None


# Path: tryalgo/sudoku.py
from tryalgo.dancing_links import dancing_links


def rv(a): return row(a) * N2 + val(a) + N4


def cv(a): return col(a) * N2 + val(a) + 2 * N4


def bv(a): return blk(a) * N2 + val(a) + 3 * N4


def sudoku(G):
    """Solving Sudoku

    :param G: integer matrix with 0 at empty cells
    :returns bool: True if grid could be solved
    :modifies: G will contain the solution
    :complexity: huge, but linear for usual published 9x9 grids
    """
    global N, N2, N4
    if len(G) == 16:              # for a 16 x 16 sudoku grid
        N, N2, N4 = 4, 16, 256
    e = N * N4
    universe = e + 1
    S = [[rc(a), rv(a), cv(a), bv(a)] for a in range(N4 * N2)]
    A = [e]
    for r in range(N2):
        for c in range(N2):
            if G[r][c] != 0:
                a = assignment(r, c, G[r][c] - 1)
                A += S[a]

    sol = dancing_links(universe, S + [A])