-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathrandom_fn.py
177 lines (162 loc) · 6.08 KB
/
random_fn.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
168
169
170
171
172
173
174
175
176
177
#random_fn_merv
import turtle
from random import randint, shuffle
from time import sleep
#import suduko_main
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])
def array_to_string(array):
result = ""
for row in array:
result += " ".join(str(num) for num in row)
result += "\n"
return result
#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
def random_inp():
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
global counter
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
print("Sudoku Grid Ready")
print(array_to_string(grid))
return grid
# def solve_random(grid):
# suduko_main.main(array_to_string(grid))