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