I have been trying to write a code to solve sudoku. This method basically involves finding the empty elements in the list of input, then filling the empty elements with the possible values that can be used in that box by deleting the values present in row, column or a box. Then I have tried using the method of backtracking to solve using each and every value present in the list. Moreover I believe that the remove function is not working as it should have because if it had worked correctly then the value 8 should not have been there in the list in a[1][2].
def print_grid(arr):
for i in range(9):
for j in range(9):
print arr[i][j],
print ('\n')
def emptyLoc(a):
l=[0,0]
for i in range(9):
for j in range(9):
if(a[i][j]==0):
a[i][j] = [1,2,3,4,5,6,7,8,9]
l[0] = i
l[1] = j
return l
def remove(a):
for i in range(9):
for j in range(9):
if type(a[i][j]) == list :
x = a[i][j]
for k in x:
for l in range(9):
if(k == a[i][l]):
x.remove(k)
for i in range(9):
for j in range(9):
if type(a[i][j]) == list:
x = a[i][j]
for k in x:
for l in range(9):
if(k == a[l][j]):
x.remove(k)
for i in range(9):
for j in range(9):
if type(a[i][j]) == list:
x = a[i][j]
for k in x:
for l in range(3):
for m in range(3):
if(k == a[l+i-(i%3)][m+j-(j%3)]):
x.remove(k)
return a
def solver(arr):
newArr = emptyLoc(arr)
finalArr = remove(arr)
#Changing One element lists to that single element
for i in range(9):
for j in range(9):
if type(arr[i][j]) == list and len(arr[i][j]) == 1:
arr[i][j] = arr[i][j][0]
for i in range(9):
for j in range(9):
if not(type(arr[i][j]) == list):
return True
else :
for num in arr[i][j]:
store = arr[i][j]
arr[i][j] = num
if (solver(arr) == True):
return True
else :
arr[i][j] = store
return False
if __name__ == "__main__":
grid=[[3,0,6,5,0,8,4,0,0],
[5,2,0,0,0,0,0,0,0],
[0,8,7,0,0,0,0,3,1],
[0,0,3,0,1,0,0,8,0],
[9,0,0,8,6,3,0,0,5],
[0,5,0,0,9,0,6,0,0],
[1,3,0,0,0,0,2,5,0],
[0,0,0,0,0,0,0,7,4],
[0,0,5,2,0,6,3,0,0]]
if(solver(grid)):
print_grid(grid)
else:
print "No solution exists"
I dont understand where I am basically going wrong with the code as I recieve an un-backtracked answer. This is the expected output
3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9
but I am getting this as an output
3 [1, 4, 7, 9] 6 5 [2, 4, 7] 8 4 [2, 6, 9] [2, 6, 7, 9]
5 2 [1, 4, 8, 9] [1, 3, 4, 6, 7, 9] [3, 4, 7] [1, 4, 7, 9] [4, 7, 8, 9] [4, 6, 8, 9] [6, 7, 8, 9]
[4, 8] 8 7 [4, 6, 9] [2, 4, 8] [2, 4, 8, 9] [5, 8, 9] 3 1
[2, 4, 6, 7] [4, 6, 7] 3 [4, 7] 1 [2, 4, 5, 7] [4, 7, 9] 8 [2, 6, 7, 9]
9 [1, 4, 6, 7] [1, 2, 4, 7] 8 6 3 [1, 4, 7, 9] [1, 2, 4, 9] 5
[2, 4, 6, 7, 8] 5 [1, 2, 4, 7, 8] [3, 4, 7] 9 [2, 4, 7] 6 [1, 2, 4, 8] [2, 3, 7]
1 3 [2, 4, 7, 8, 9] [4, 7, 9] [4, 7, 8] [4, 7, 9] 2 5 [6, 8, 9]
[2, 6, 8] [3, 6, 9] [2, 8, 9] [1, 3, 9] [3, 5, 8] [1, 5, 8, 9] [1, 5, 8, 9] 7 4
[4, 6, 7, 8] [4, 6, 7, 9] 5 2 [3, 4, 7, 8] 6 3 [1, 6, 8, 9] [6, 8, 9]
Somebody please help me with this. Thank You !!!
0 Answer(s)