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