Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/generators/sudoku.py: 16%

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 

50@nx._dispatch(graphs=None) 

51def sudoku_graph(n=3): 

52 """Returns the n-Sudoku graph. The default value of n is 3. 

53 

54 The n-Sudoku graph is a graph with n^4 vertices, corresponding to the 

55 cells of an n^2 by n^2 grid. Two distinct vertices are adjacent if and 

56 only if they belong to the same row, column, or n-by-n box. 

57 

58 Parameters 

59 ---------- 

60 n: integer 

61 The order of the Sudoku graph, equal to the square root of the 

62 number of rows. The default is 3. 

63 

64 Returns 

65 ------- 

66 NetworkX graph 

67 The n-Sudoku graph Sud(n). 

68 

69 Examples 

70 -------- 

71 >>> G = nx.sudoku_graph() 

72 >>> G.number_of_nodes() 

73 81 

74 >>> G.number_of_edges() 

75 810 

76 >>> sorted(G.neighbors(42)) 

77 [6, 15, 24, 33, 34, 35, 36, 37, 38, 39, 40, 41, 43, 44, 51, 52, 53, 60, 69, 78] 

78 >>> G = nx.sudoku_graph(2) 

79 >>> G.number_of_nodes() 

80 16 

81 >>> G.number_of_edges() 

82 56 

83 

84 References 

85 ---------- 

86 .. [1] Herzberg, A. M., & Murty, M. R. (2007). Sudoku squares and chromatic 

87 polynomials. Notices of the AMS, 54(6), 708-717. 

88 .. [2] Sander, Torsten (2009), "Sudoku graphs are integral", 

89 Electronic Journal of Combinatorics, 16 (1): Note 25, 7pp, MR 2529816 

90 .. [3] Wikipedia contributors. "Glossary of Sudoku." Wikipedia, The Free 

91 Encyclopedia, 3 Dec. 2019. Web. 22 Dec. 2019. 

92 """ 

93 

94 if n < 0: 

95 raise NetworkXError("The order must be greater than or equal to zero.") 

96 

97 n2 = n * n 

98 n3 = n2 * n 

99 n4 = n3 * n 

100 

101 # Construct an empty graph with n^4 nodes 

102 G = nx.empty_graph(n4) 

103 

104 # A Sudoku graph of order 0 or 1 has no edges 

105 if n < 2: 

106 return G 

107 

108 # Add edges for cells in the same row 

109 for row_no in range(n2): 

110 row_start = row_no * n2 

111 for j in range(1, n2): 

112 for i in range(j): 

113 G.add_edge(row_start + i, row_start + j) 

114 

115 # Add edges for cells in the same column 

116 for col_no in range(n2): 

117 for j in range(col_no, n4, n2): 

118 for i in range(col_no, j, n2): 

119 G.add_edge(i, j) 

120 

121 # Add edges for cells in the same box 

122 for band_no in range(n): 

123 for stack_no in range(n): 

124 box_start = n3 * band_no + n * stack_no 

125 for j in range(1, n2): 

126 for i in range(j): 

127 u = box_start + (i % n) + n2 * (i // n) 

128 v = box_start + (j % n) + n2 * (j // n) 

129 G.add_edge(u, v) 

130 

131 return G