Source code for tryalgo.sudoku

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Solving Sudoku (nanpure)
jill-jenn vie et christoph durr - 2014-2019
"""
# pylint: disable=missing-docstring, multiple-statements, global-statement

from tryalgo.dancing_links import dancing_links


__all__ = ["sudoku"]

# snip{
N = 3        # global constants
N2 = N * N
N4 = N2 * N2


# sets
def assignment(r, c, v): return r * N4 + c * N2 + v


def row(a): return a // N4


def col(a): return (a // N2) % N2


def val(a): return a % N2


def blk(a): return (row(a) // N) * N + col(a) // N


# elements to cover
def rc(a): return row(a) * N2 + col(a)


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


[docs]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]) if sol: for a in sol: if a < len(S): G[row(a)][col(a)] = val(a) + 1 return True return False
# snip}