1"""Generator for Sudoku graphs
2
3This module gives a generator for n-Sudoku graphs. It can be used to develop
4algorithms for solving or generating Sudoku puzzles.
5
6A completed Sudoku grid is a 9x9 array of integers between 1 and 9, with no
7number appearing twice in the same row, column, or 3x3 box.
8
9+---------+---------+---------+
10| | 8 6 4 | | 3 7 1 | | 2 5 9 |
11| | 3 2 5 | | 8 4 9 | | 7 6 1 |
12| | 9 7 1 | | 2 6 5 | | 8 4 3 |
13+---------+---------+---------+
14| | 4 3 6 | | 1 9 2 | | 5 8 7 |
15| | 1 9 8 | | 6 5 7 | | 4 3 2 |
16| | 2 5 7 | | 4 8 3 | | 9 1 6 |
17+---------+---------+---------+
18| | 6 8 9 | | 7 3 4 | | 1 2 5 |
19| | 7 1 3 | | 5 2 8 | | 6 9 4 |
20| | 5 4 2 | | 9 1 6 | | 3 7 8 |
21+---------+---------+---------+
22
23
24The Sudoku graph is an undirected graph with 81 vertices, corresponding to
25the cells of a Sudoku grid. It is a regular graph of degree 20. Two distinct
26vertices are adjacent if and only if the corresponding cells belong to the
27same row, column, or box. A completed Sudoku grid corresponds to a vertex
28coloring of the Sudoku graph with nine colors.
29
30More generally, the n-Sudoku graph is a graph with n^4 vertices, corresponding
31to the cells of an n^2 by n^2 grid. Two distinct vertices are adjacent if and
32only if they belong to the same row, column, or n by n box.
33
34References
35----------
36.. [1] Herzberg, A. M., & Murty, M. R. (2007). Sudoku squares and chromatic
37    polynomials. Notices of the AMS, 54(6), 708-717.
38.. [2] Sander, Torsten (2009), "Sudoku graphs are integral",
39    Electronic Journal of Combinatorics, 16 (1): Note 25, 7pp, MR 2529816
40.. [3] Wikipedia contributors. "Glossary of Sudoku." Wikipedia, The Free
41    Encyclopedia, 3 Dec. 2019. Web. 22 Dec. 2019.
42"""
43
44import networkx as nx
45from networkx.exception import NetworkXError
46
47__all__ = ["sudoku_graph"]
48
49
50def sudoku_graph(n=3):
51    """Returns the n-Sudoku graph. The default value of n is 3.
52
53    The n-Sudoku graph is a graph with n^4 vertices, corresponding to the
54    cells of an n^2 by n^2 grid. Two distinct vertices are adjacent if and
55    only if they belong to the same row, column, or n-by-n box.
56
57    Parameters
58    ----------
59    n: integer
60       The order of the Sudoku graph, equal to the square root of the
61       number of rows. The default is 3.
62
63    Returns
64    -------
65    NetworkX graph
66        The n-Sudoku graph Sud(n).
67
68    Examples
69    --------
70    >>> G = nx.sudoku_graph()
71    >>> G.number_of_nodes()
72    81
73    >>> G.number_of_edges()
74    810
75    >>> sorted(G.neighbors(42))
76    [6, 15, 24, 33, 34, 35, 36, 37, 38, 39, 40, 41, 43, 44, 51, 52, 53, 60, 69, 78]
77    >>> G = nx.sudoku_graph(2)
78    >>> G.number_of_nodes()
79    16
80    >>> G.number_of_edges()
81    56
82
83    References
84    ----------
85    .. [1] Herzberg, A. M., & Murty, M. R. (2007). Sudoku squares and chromatic
86       polynomials. Notices of the AMS, 54(6), 708-717.
87    .. [2] Sander, Torsten (2009), "Sudoku graphs are integral",
88       Electronic Journal of Combinatorics, 16 (1): Note 25, 7pp, MR 2529816
89    .. [3] Wikipedia contributors. "Glossary of Sudoku." Wikipedia, The Free
90       Encyclopedia, 3 Dec. 2019. Web. 22 Dec. 2019.
91    """
92
93    if n < 0:
94        raise NetworkXError("The order must be greater than or equal to zero.")
95
96    n2 = n * n
97    n3 = n2 * n
98    n4 = n3 * n
99
100    # Construct an empty graph with n^4 nodes
101    G = nx.empty_graph(n4)
102
103    # A Sudoku graph of order 0 or 1 has no edges
104    if n < 2:
105        return G
106
107    # Add edges for cells in the same row
108    for row_no in range(0, n2):
109        row_start = row_no * n2
110        for j in range(1, n2):
111            for i in range(j):
112                G.add_edge(row_start + i, row_start + j)
113
114    # Add edges for cells in the same column
115    for col_no in range(0, n2):
116        for j in range(col_no, n4, n2):
117            for i in range(col_no, j, n2):
118                G.add_edge(i, j)
119
120    # Add edges for cells in the same box
121    for band_no in range(n):
122        for stack_no in range(n):
123            box_start = n3 * band_no + n * stack_no
124            for j in range(1, n2):
125                for i in range(j):
126                    u = box_start + (i % n) + n2 * (i // n)
127                    v = box_start + (j % n) + n2 * (j // n)
128                    G.add_edge(u, v)
129
130    return G
131