-
Notifications
You must be signed in to change notification settings - Fork 45
/
sudoku_MRV.py
executable file
·88 lines (80 loc) · 1.76 KB
/
sudoku_MRV.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
import sys
def read_file(textfile):
f=open(textfile,'r')
next(f)
i=0
j=0
matrix=[[0 for x in range(9)] for y in range(9)]
while True:
j=0
char=f.readline()
for c in char:
matrix[i][j]=int(c)
j=j+1
if j==9:
i=i+1
break
if i==9:
break
return matrix
def check_soduku(row,column,number,matrix_board):
check=0
for i in range(0,9):
if matrix_board[row][i]==number:
check=1
for i in range(0,9):
if matrix_board[i][column]==number:
check=1
row=row-row%3
column=column-column%3
for i in range(0,3):
for j in range(0,3):
if matrix_board[row+i][column+j]==number:
check=1
if check==1:
return False
else:
return True
class calls:
number_of_calls=0
c=calls()
def sudoku_solver(matrix):
c.number_of_calls=c.number_of_calls+1
break_condition=0
checking_range=[]
for i in range(0,9):
for j in range(0,9):
if matrix[i][j]==0:
break_condition=1
temp=[]
temp.append([i,j])
temp_2=[]
for num in range(0,10):
if check_soduku(i,j,num,matrix):
temp_2.append(num)
temp.append(len(temp_2))
checking_range.append(temp)
if break_condition==0:
print("Smart Backtracking Algorithm MRV Solution: ")
for i in matrix:
print(i)
print("Amount of Recursions: ")
print(c.number_of_calls)
exit(0)
minimum_range_selection=checking_range[0][0]
low=checking_range[0][1]
for i in range(0,len(checking_range)):
if checking_range[i][1]<low:
low=checking_range[i][1]
minimum_range_selection=checking_range[i][0]
row=minimum_range_selection[0]
column=minimum_range_selection[1]
for i in range(0,10):
if check_soduku(row,column,i,matrix):
matrix[row][column]=i
if sudoku_solver(matrix):
return True
matrix[row][column]=0
return False
matrix=read_file(sys.argv[1])
sudoku_solver(matrix)