Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

1import random 

2from typing import Tuple 

3 

4import numpy as np 

5import torch 

6from scipy import sparse 

7 

8 

9def construct_solved_sudoku(): 

10 """Return a solved sudoku puzzle.""" 

11 while True: 

12 try: 

13 puzzle = np.zeros((9, 9), dtype=np.int64) 

14 rows = [set(range(1, 10)) for i in range(9)] 

15 columns = [set(range(1, 10)) for i in range(9)] 

16 squares = [set(range(1, 10)) for i in range(9)] 

17 for i in range(9): 

18 for j in range(9): 

19 # Pick a number for cell (i,j) from the set of remaining available numbers 

20 choices = rows[i] & columns[j] & squares[(i // 3) * 3 + j // 3] 

21 if not choices: 

22 raise ValueError 

23 choice = random.choice(list(choices)) 

24 

25 puzzle[i, j] = choice 

26 

27 rows[i].discard(choice) 

28 columns[j].discard(choice) 

29 squares[(i // 3) * 3 + j // 3].discard(choice) 

30 return puzzle 

31 except ValueError: 

32 pass 

33 

34 

35def gen_sudoku_graph_dense() -> np.ndarray: 

36 """Generate Sudoku constraint graph (dense).""" 

37 # Create connectivity matrix for each pixel in graph 

38 lst = [] 

39 for i in range(9): 

40 for j in range(9): 

41 a = np.zeros((9, 9), dtype=np.int) 

42 i_div = i // 3 

43 j_div = j // 3 

44 a[i_div * 3 : (i_div + 1) * 3, j_div * 3 : (j_div + 1) * 3] = 1 

45 a[i, :] = 1 

46 a[:, j] = 1 

47 lst.append(a) 

48 # Combine into a single connectivity matrix 

49 adj_dense = np.empty((81, 81), dtype=np.int) 

50 for i, a in enumerate(lst): 

51 adj_dense[i, :] = a.reshape(-1) 

52 return adj_dense 

53 

54 

55def gen_sudoku_graph_featured() -> np.ndarray: 

56 """Generate Sudoku constraint graph (dense).""" 

57 # Create connectivity matrix for each pixel in graph 

58 lst = [] 

59 for i in range(9): 

60 for j in range(9): 

61 a = np.zeros((9, 9, 3), dtype=np.float32) 

62 i_div = i // 3 

63 j_div = j // 3 

64 a[i_div * 3 : (i_div + 1) * 3, j_div * 3 : (j_div + 1) * 3, 0] = 1 

65 a[i, :, 1] = 1 

66 a[:, j, 2] = 1 

67 lst.append(a) 

68 # Combine into a single connectivity matrix 

69 adj_dense = np.empty((81, 81, 3), dtype=np.float32) 

70 for i, a in enumerate(lst): 

71 adj_dense[i, :, :] = a.reshape(81, 3) 

72 return adj_dense 

73 

74 

75def gen_sudoku_graph() -> Tuple[torch.tensor, torch.tensor]: 

76 """Generate Sudoku constraint graph (sparse).""" 

77 adj_dense = gen_sudoku_graph_dense() 

78 adj_coo = sparse.coo_matrix(adj_dense) 

79 indices = torch.stack([torch.from_numpy(adj_coo.row), torch.from_numpy(adj_coo.col)]).to( 

80 torch.long 

81 ) 

82 values = torch.from_numpy(adj_coo.data) 

83 return indices, values 

84 

85 

86def sudoku_is_solved(values) -> bool: 

87 ref = np.arange(1, 10) 

88 mat = values.reshape(9, 9) 

89 for i in range(3): 

90 for j in range(3): 

91 v = np.sort(mat[i * 3 : (i + 1) * 3, j * 3 : (j + 1) * 3], axis=None) 

92 if not (v == ref).all(): 

93 return False 

94 for i in range(9): 

95 v = np.sort(mat[i, :]) 

96 if not (v == ref).all(): 

97 return False 

98 for j in range(9): 

99 v = np.sort(mat[:, j]) 

100 if not (v == ref).all(): 

101 return False 

102 return True