-
Notifications
You must be signed in to change notification settings - Fork 0
/
generate_sudoku.py
167 lines (155 loc) · 5.85 KB
/
generate_sudoku.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#Sudoku Generator Algorithm - www.101computing.net/sudoku-generator-algorithm/
from random import randint, shuffle
import os
#initialise empty 9 by 9 grid
grid = []
grid.append([0, 0, 0, 0, 0, 0, 0, 0, 0])
grid.append([0, 0, 0, 0, 0, 0, 0, 0, 0])
grid.append([0, 0, 0, 0, 0, 0, 0, 0, 0])
grid.append([0, 0, 0, 0, 0, 0, 0, 0, 0])
grid.append([0, 0, 0, 0, 0, 0, 0, 0, 0])
grid.append([0, 0, 0, 0, 0, 0, 0, 0, 0])
grid.append([0, 0, 0, 0, 0, 0, 0, 0, 0])
grid.append([0, 0, 0, 0, 0, 0, 0, 0, 0])
grid.append([0, 0, 0, 0, 0, 0, 0, 0, 0])
#A function to check if the grid is full
def checkGrid(grid):
for row in range(0,9):
for col in range(0,9):
if grid[row][col]==0:
return False
#We have a complete grid!
return True
#A backtracking/recursive function to check all possible combinations of numbers until a solution is found
def solveGrid(grid):
global counter
#Find next empty cell
for i in range(0,81):
row=i//9
col=i%9
if grid[row][col]==0:
for value in range (1,10):
#Check that this value has not already be used on this row
if not(value in grid[row]):
#Check that this value has not already be used on this column
if not value in (grid[0][col],grid[1][col],grid[2][col],grid[3][col],grid[4][col],grid[5][col],grid[6][col],grid[7][col],grid[8][col]):
#Identify which of the 9 squares we are working on
square=[]
if row<3:
if col<3:
square=[grid[i][0:3] for i in range(0,3)]
elif col<6:
square=[grid[i][3:6] for i in range(0,3)]
else:
square=[grid[i][6:9] for i in range(0,3)]
elif row<6:
if col<3:
square=[grid[i][0:3] for i in range(3,6)]
elif col<6:
square=[grid[i][3:6] for i in range(3,6)]
else:
square=[grid[i][6:9] for i in range(3,6)]
else:
if col<3:
square=[grid[i][0:3] for i in range(6,9)]
elif col<6:
square=[grid[i][3:6] for i in range(6,9)]
else:
square=[grid[i][6:9] for i in range(6,9)]
#Check that this value has not already be used on this 3x3 square
if not value in (square[0] + square[1] + square[2]):
grid[row][col]=value
if checkGrid(grid):
counter+=1
break
else:
if solveGrid(grid):
return True
break
grid[row][col]=0
numberList=[1,2,3,4,5,6,7,8,9]
#shuffle(numberList)
#A backtracking/recursive function to check all possible combinations of numbers until a solution is found
def fillGrid(grid):
global counter
#Find next empty cell
for i in range(0,81):
row=i//9
col=i%9
if grid[row][col]==0:
shuffle(numberList)
for value in numberList:
#Check that this value has not already be used on this row
if not(value in grid[row]):
#Check that this value has not already be used on this column
if not value in (grid[0][col],grid[1][col],grid[2][col],grid[3][col],grid[4][col],grid[5][col],grid[6][col],grid[7][col],grid[8][col]):
#Identify which of the 9 squares we are working on
square=[]
if row<3:
if col<3:
square=[grid[i][0:3] for i in range(0,3)]
elif col<6:
square=[grid[i][3:6] for i in range(0,3)]
else:
square=[grid[i][6:9] for i in range(0,3)]
elif row<6:
if col<3:
square=[grid[i][0:3] for i in range(3,6)]
elif col<6:
square=[grid[i][3:6] for i in range(3,6)]
else:
square=[grid[i][6:9] for i in range(3,6)]
else:
if col<3:
square=[grid[i][0:3] for i in range(6,9)]
elif col<6:
square=[grid[i][3:6] for i in range(6,9)]
else:
square=[grid[i][6:9] for i in range(6,9)]
#Check that this value has not already be used on this 3x3 square
if not value in (square[0] + square[1] + square[2]):
grid[row][col]=value
if checkGrid(grid):
return True
else:
if fillGrid(grid):
return True
break
grid[row][col]=0
#Generate a Fully Solved Grid
fillGrid(grid)
#Start Removing Numbers one by one
#A higher number of attempts will end up removing more numbers from the grid
#Potentially resulting in more difficiult grids to solve!
attempts = 5
counter=1
while attempts>0:
#Select a random cell that is not already empty
row = randint(0,8)
col = randint(0,8)
while grid[row][col]==0:
row = randint(0,8)
col = randint(0,8)
#Remember its cell value in case we need to put it back
backup = grid[row][col]
grid[row][col]=0
#Take a full copy of the grid
copyGrid = []
for r in range(0,9):
copyGrid.append([])
for c in range(0,9):
copyGrid[r].append(grid[r][c])
#Count the number of solutions that this grid has (using a backtracking approach implemented in the solveGrid() function)
counter=0
solveGrid(copyGrid)
#If the number of solution is different from 1 then we need to cancel the change by putting the value we took away back in the grid
if counter!=1:
grid[row][col]=backup
#We could stop here, but we can also have another attempt with a different cell just to try to remove more numbers
attempts -= 1
# flatten the grid into one long list of digits and print to file
flat_grid = [item for sublist in grid for item in sublist]
flat_grid = ''.join(map(str,flat_grid))
with open("sudoku.txt", 'w') as file:
file.write(flat_grid)
print("Sudoku printed to sudoku.txt")