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