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
4import numpy as np
5import torch
6from scipy import sparse
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))
25 puzzle[i, j] = choice
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
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
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
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
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