Solve sudokus automatically — and naturally

def whatcanitbe(row, col):
if sudoku[row][col]==0:
rowvals = set(sudoku[row])
colvals = {row[col] for row in sudoku}
boxrow = int(row/3)*3
boxcol = int(col/3)*3
boxvals = [row[boxcol:boxcol+3]
for row in sudoku[boxrow:boxrow+3]]
boxvals = set(boxvals[0] + boxvals[1] + boxvals[2])
return list({1,2,3,4,5,6,7,8,9}
- rowvals - colvals - boxvals)
else:
return [sudoku[row][col]]
def preparesudoku():
global sudoku
sudoku = [[whatcanitbe(row, col)
for col in range(9) ]
for row in range(9)]
def maxdigits():
return max([max([len(col) for col in row]) for row in sudoku])
def printsudoku():
collength='{{:{}}}'.format(maxdigits())
string = '\n'.join(
[' '.join(
[collength.format(''.join(
['{}'.format(s) for s in col]))
for col in row])
for row in sudoku])
print(string + '\n')
def getgroup(rowcolbox, num):
temp = [[(sudoku[i][j], i, j)
for j in range(9) ]
for i in range(9)]
if rowcolbox=='row':
return temp[num]
elif rowcolbox=='col':
return [row[num] for row in temp]
elif rowcolbox == 'box':
startrow = int(num/3)*3
startcol = (num%3)*3
group = [row[startcol:startcol+3]
for row in temp[startrow:startrow+3]]
return group[0] + group[1] + group[2]
else:
raise Exception
def cleanarray(rowcolbox, num, size, audit=1):
global sudoku
array = getgroup(rowcolbox, num)
combs = list(itertools.combinations(array, size))
combs2 = [set.union(*[set(c[0])
for c in comb])
for comb in combs]
combs3 = [len(comb) for comb in combs2]
assert min(combs3)>=size
combs3 = [(comb==size) for comb in combs3]
for i in range(len(combs)):
if combs3[i]==1:
vals = list(combs2[i])
inlocs = [(comb[1], comb[2]) for comb in combs[i]]
for item in array:
if (item[1],item[2]) not in inlocs:
for val in vals:
if val in item[0]:
if audit>=1:
print('{} cannot be in cell {},{} '
'because it is in group {} in '
'that {} '.format(val,
item[1]+1,
item[2]+1,
combs2[i],
rowcolbox))
sudoku[item[1]][item[2]].remove(val)
if audit>=2:
printsudoku()
def cleanarrays(maxsize, audit=1):
for size in range(1, maxsize+1):
for iteration in range(10):
if maxdigits()==1:
break
else:
for num in range(9):
cleanarray('row', num, size, audit)
cleanarray('col', num, size, audit)
cleanarray('box', num, size, audit)
def cleanboxes(audit=1):
global sudoku
rowcolbox = 'col'
temp = [
[sudoku[0][col] + sudoku[1][col] + sudoku[2][col],
sudoku[3][col] + sudoku[4][col] + sudoku[5][col],
sudoku[6][col] + sudoku[7][col] + sudoku[8][col]]
for col in range(9)]
for num in range(1,9):
tempfornum = [[int(num in col) for col in row] for row in temp]
for i in range(3):
t = tempfornum[3*i:3*i+3]
for row in range(3):
for col in range(3):
if (t[0][col] + t[1][col] + t[2][col] - t[row][col] == 0):
for col2 in range(3):
if col2 != col:
if t[row][col2] == 1:
for i2 in range(3):
if num in sudoku[col2*3 + i2][3*i + row]:
if audit >= 1:
print('{} cannot be in {},{} as it is needed in another block in this {}'.format(num, col2*3 + i2 + 1, 3*i + row + 1, rowcolbox ))
sudoku[col2*3 + i2][3*i + row].remove(num)
if audit >= 2:
printsudoku()
rowcolbox = 'row'
temp = [[row[0] + row[1] + row[2], row[3] + row[4] + row[5], row[6] + row[7] + row[8] ] for row in sudoku]
for num in range(1,9):
tempfornum = [[int(num in col) for col in row] for row in temp]
for i in range(3):
t = tempfornum[3*i:3*i+3]
for row in range(3):
for col in range(3):
if (t[0][col] + t[1][col] + t[2][col] - t[row][col] == 0):
for col2 in range(3):
if col2 != col:
if t[row][col2] == 1:
for i2 in range(3):
if num in sudoku[row][3*col2 + i2]:
if audit>=1:
print('remove {} from {},{} as it is needed in another block in this {}'.format(num, row, 3*col2 + i2, rowcolbox ))
sudoku[row][3*col2 + i2].remove(num)
if audit>=2:
printsudoku()
preparesudoku()
printsudoku()
for j in range(4):
cleanarrays(maxsize=5)
printsudoku()
if maxdigits()==1:
break
cleanboxes()
printsudoku()
if maxdigits()==1:
break
2      9456   946    1      7      895    456    3      845   
1457 3 1497 24589 8924 6 12457 24578 12458
14567 14567 8 3 24 25 9 24567 1245
9 4567 467 24578 8234 23578 23456 1 23458
3 145 14 24589 6 8925 245 8245 7
145678 2 1467 8457 8134 8357 3456 8456 9
167 1796 5 927 923 4 8 27 123
147 147 12347 6 823 8237 123457 9 12345
47 8 23479 927 5 1 2347 247 6
1 cannot be in cell 7,1 because it is in group {1, 4, 7} in that box
7 cannot be in cell 7,1 because it is in group {1, 4, 7} in that box
1 cannot be in cell 7,2 because it is in group {1, 4, 7} in that box
7 cannot be in cell 7,2 because it is in group {1, 4, 7} in that box
1 cannot be in cell 8,3 because it is in group {1, 4, 7} in that box
4 cannot be in cell 8,3 because it is in group {1, 4, 7} in that box
7 cannot be in cell 8,3 because it is in group {1, 4, 7} in that box
4 cannot be in cell 9,3 because it is in group {1, 4, 7} in that box
7 cannot be in cell 9,3 because it is in group {1, 4, 7} in that box
6 cannot be in cell 3,1 because it is in group {9, 2, 6} in that col
6 cannot be in cell 6,1 because it is in group {9, 2, 6} in that col
9 cannot be in cell 7,4 because it is in group {9, 5, 6} in that row
9 cannot be in cell 7,5 because it is in group {9, 5, 6} in that row
6 cannot be in cell 7,2 because it is in group {4, 5, 6} in that row
9 cannot be in cell 9,3 because it is in group {9, 5, 6} in that box
9 cannot be in cell 1,2 because it is in group {9, 2, 3} in that col
2 cannot be in cell 7,5 because it is in group {2, 6, 7} in that row
2 cannot be in cell 7,9 because it is in group {2, 6, 7} in that row
3 cannot be in cell 7,9 because it is in group {2, 3, 7} in that row
3 cannot be in cell 8,5 because it is in group {3, 4, 6} in that box
3 cannot be in cell 8,6 because it is in group {3, 4, 6} in that box
1 cannot be in cell 2,9 because it is in group {9, 1, 7} in that col
1 cannot be in cell 3,9 because it is in group {9, 1, 7} in that col
1 cannot be in cell 8,9 because it is in group {9, 1, 7} in that col
1 cannot be in cell 8,7 because it is in group {8, 1, 9} in that box
4 cannot be in cell 3,1 because it is in group {2, 4, 5} in that row
5 cannot be in cell 3,1 because it is in group {2, 4, 5} in that row
4 cannot be in cell 3,2 because it is in group {2, 4, 5} in that row
5 cannot be in cell 3,2 because it is in group {2, 4, 5} in that row
2 cannot be in cell 3,8 because it is in group {2, 4, 5} in that row
4 cannot be in cell 3,8 because it is in group {2, 4, 5} in that row
5 cannot be in cell 3,8 because it is in group {2, 4, 5} in that row
3 cannot be in cell 4,5 because it is in group {3, 6, 7} in that col
3 cannot be in cell 6,5 because it is in group {3, 6, 7} in that col
2 cannot be in cell 9,4 because it is in group {2, 7, 8} in that box
7 cannot be in cell 9,4 because it is in group {2, 7, 8} in that box
1 cannot be in cell 2,1 because it is in group {1, 4, 7} in that col
4 cannot be in cell 2,1 because it is in group {1, 4, 7} in that col
7 cannot be in cell 2,1 because it is in group {1, 4, 7} in that col
1 cannot be in cell 6,1 because it is in group {1, 4, 7} in that col
4 cannot be in cell 6,1 because it is in group {1, 4, 7} in that col
7 cannot be in cell 6,1 because it is in group {1, 4, 7} in that col
5 cannot be in cell 1,2 because it is in group {2, 3, 5} in that box
5 cannot be in cell 2,4 because it is in group {3, 5, 6} in that row
5 cannot be in cell 2,7 because it is in group {3, 5, 6} in that row
5 cannot be in cell 2,8 because it is in group {3, 5, 6} in that row
5 cannot be in cell 2,9 because it is in group {3, 5, 6} in that row
9 cannot be in cell 2,4 because it is in group {1, 3, 9} in that col
9 cannot be in cell 5,4 because it is in group {1, 3, 9} in that col
2 cannot be in cell 2,5 because it is in group {2, 4, 8} in that col
4 cannot be in cell 2,5 because it is in group {2, 4, 8} in that col
8 cannot be in cell 2,5 because it is in group {2, 4, 8} in that col
4 cannot be in cell 6,5 because it is in group {2, 4, 8} in that col
8 cannot be in cell 6,5 because it is in group {2, 4, 8} in that col
1 cannot be in cell 6,3 because it is in group {1, 2, 9} in that row
5 cannot be in cell 6,1 because it is in group {9, 2, 5} in that col
9 cannot be in cell 2,3 because it is in group {9, 3, 5} in that row
9 cannot be in cell 1,6 because it is in group {1, 9, 7} in that box
8 cannot be in cell 6,4 because it is in group {8, 1, 2} in that row
8 cannot be in cell 6,6 because it is in group {8, 1, 2} in that row
8 cannot be in cell 6,8 because it is in group {8, 1, 2} in that row
4 cannot be in cell 1,3 because it is in group {4, 5, 6, 8} in that row
6 cannot be in cell 1,3 because it is in group {4, 5, 6, 8} in that row
2 cannot be in cell 5,6 because it is in group {1, 2, 4, 5, 8} in that row
5 cannot be in cell 5,6 because it is in group {1, 2, 4, 5, 8} in that row
8 cannot be in cell 5,6 because it is in group {1, 2, 4, 5, 8} in that row
2 46 9 1 7 85 456 3 845
5 3 147 248 9 6 1247 2478 248
17 167 8 3 24 25 9 67 245
9 4567 467 24578 824 23578 23456 1 23458
3 145 14 2458 6 9 245 8245 7
8 2 467 457 1 357 3456 456 9
6 9 5 27 3 4 8 27 1
147 147 23 6 82 827 23457 9 2345
47 8 23 9 5 1 2347 247 6
5 cannot be in 4,6 as it is needed in another block in this col
5 cannot be in 6,6 as it is needed in another block in this col
6 cannot be in 4,2 as it is needed in another block in this col
remove 1 from 1,2 as it is needed in another block in this row
2 46 9 1 7 85 456 3 845
5 3 47 248 9 6 1247 2478 248
17 167 8 3 24 25 9 67 245
9 457 467 24578 824 2378 23456 1 23458
3 145 14 2458 6 9 245 8245 7
8 2 467 457 1 37 3456 456 9
6 9 5 27 3 4 8 27 1
147 147 23 6 82 827 23457 9 2345
47 8 23 9 5 1 2347 247 6
4 cannot be in cell 5,3 because it is in group {4, 6, 7} in that col
1 cannot be in cell 5,2 because it is in group {9, 3, 1} in that box
2 cannot be in cell 2,7 because it is in group {2, 4, 7, 8} in that row
4 cannot be in cell 2,7 because it is in group {2, 4, 7, 8} in that row
7 cannot be in cell 2,7 because it is in group {2, 4, 7, 8} in that row
2 46 9 1 7 85 456 3 845
5 3 47 248 9 6 1 2478 248
17 167 8 3 24 25 9 67 245
9 457 467 24578 824 2378 23456 1 23458
3 45 1 2458 6 9 245 8245 7
8 2 467 457 1 37 3456 456 9
6 9 5 27 3 4 8 27 1
147 147 23 6 82 827 23457 9 2345
47 8 23 9 5 1 2347 247 6
7 cannot be in 7,8 as it is needed in another block in this col
7 cannot be in 9,8 as it is needed in another block in this col
2 46 9 1 7 85 456 3 845
5 3 47 248 9 6 1 2478 248
17 167 8 3 24 25 9 67 245
9 457 467 24578 824 2378 23456 1 23458
3 45 1 2458 6 9 245 8245 7
8 2 467 457 1 37 3456 456 9
6 9 5 27 3 4 8 2 1
147 147 23 6 82 827 23457 9 2345
47 8 23 9 5 1 2347 24 6
2 cannot be in cell 7,4 because it is in group {2} in that row
2 cannot be in cell 2,8 because it is in group {2} in that col
2 cannot be in cell 5,8 because it is in group {2} in that col
2 cannot be in cell 9,8 because it is in group {2} in that col
7 cannot be in cell 8,6 because it is in group {7} in that box
4 cannot be in cell 9,1 because it is in group {4} in that row
4 cannot be in cell 9,7 because it is in group {4} in that row
2 cannot be in cell 8,7 because it is in group {2} in that box
2 cannot be in cell 8,9 because it is in group {2} in that box
2 cannot be in cell 9,7 because it is in group {2} in that box
4 cannot be in cell 8,7 because it is in group {4} in that box
4 cannot be in cell 8,9 because it is in group {4} in that box
7 cannot be in cell 3,1 because it is in group {7} in that col
7 cannot be in cell 8,1 because it is in group {7} in that col
1 cannot be in cell 3,2 because it is in group {1} in that box
7 cannot be in cell 4,4 because it is in group {7} in that col
7 cannot be in cell 6,4 because it is in group {7} in that col
7 cannot be in cell 8,2 because it is in group {7} in that box
4 cannot be in cell 2,8 because it is in group {4} in that col
4 cannot be in cell 5,8 because it is in group {4} in that col
4 cannot be in cell 6,8 because it is in group {4} in that col
7 cannot be in cell 9,7 because it is in group {7} in that row
3 cannot be in cell 8,7 because it is in group {3} in that box
3 cannot be in cell 8,9 because it is in group {3} in that box
1 cannot be in cell 8,1 because it is in group {1} in that col
3 cannot be in cell 4,7 because it is in group {3} in that col
3 cannot be in cell 6,7 because it is in group {3} in that col
4 cannot be in cell 8,2 because it is in group {4} in that box
5 cannot be in cell 8,7 because it is in group {5} in that row
3 cannot be in cell 9,3 because it is in group {3} in that row
5 cannot be in cell 1,9 because it is in group {5} in that col
5 cannot be in cell 3,9 because it is in group {5} in that col
5 cannot be in cell 4,9 because it is in group {5} in that col
2 cannot be in cell 8,3 because it is in group {2} in that col
2 cannot be in cell 3,6 because it is in group {2, 4} in that row
8 cannot be in cell 4,6 because it is in group {8, 5} in that col
8 cannot be in cell 8,6 because it is in group {8, 5} in that col
5 cannot be in cell 1,6 because it is in group {5, 6} in that col
2 cannot be in cell 8,5 because it is in group {2, 4} in that row
8 cannot be in cell 1,9 because it is in group {8, 2} in that row
4 cannot be in cell 1,2 because it is in group {8, 4} in that row
4 cannot be in cell 1,7 because it is in group {8, 4} in that row
6 cannot be in cell 3,2 because it is in group {2, 6} in that box
7 cannot be in cell 2,3 because it is in group {6, 7} in that box
4 cannot be in cell 2,4 because it is in group {4, 5} in that row
4 cannot be in cell 2,9 because it is in group {4, 5} in that row
7 cannot be in cell 4,2 because it is in group {6, 7} in that col
8 cannot be in cell 2,4 because it is in group {8, 1} in that box
2 cannot be in cell 3,5 because it is in group {8, 2} in that box
7 cannot be in cell 3,8 because it is in group {1, 7} in that row
4 cannot be in cell 3,9 because it is in group {1, 4} in that row
4 cannot be in cell 4,3 because it is in group {9, 4} in that col
4 cannot be in cell 6,3 because it is in group {9, 4} in that col
6 cannot be in cell 1,7 because it is in group {3, 6} in that box
2 cannot be in cell 2,9 because it is in group {2, 3} in that box
8 cannot be in cell 2,8 because it is in group {8, 2} in that box
2 cannot be in cell 4,4 because it is in group {1, 2} in that col
2 cannot be in cell 5,4 because it is in group {1, 2} in that col
4 cannot be in cell 4,5 because it is in group {4, 7} in that col
8 cannot be in cell 4,5 because it is in group {8, 7} in that col
2 cannot be in cell 4,6 because it is in group {2, 6} in that box
5 cannot be in cell 4,7 because it is in group {1, 5} in that col
5 cannot be in cell 5,7 because it is in group {1, 5} in that col
5 cannot be in cell 6,7 because it is in group {1, 5} in that col
6 cannot be in cell 6,8 because it is in group {3, 6} in that col
5 cannot be in cell 5,8 because it is in group {5, 6} in that col
8 cannot be in cell 4,9 because it is in group {8, 4} in that col
4 cannot be in cell 4,9 because it is in group {8, 4} in that col
2 cannot be in cell 4,9 because it is in group {2, 4} in that col
2 cannot be in cell 4,7 because it is in group {9, 2} in that row
3 cannot be in cell 4,6 because it is in group {9, 3} in that row
7 cannot be in cell 4,3 because it is in group {3, 7} in that row
6 cannot be in cell 6,3 because it is in group {9, 6} in that box
8 cannot be in cell 5,4 because it is in group {8, 3} in that row
7 cannot be in cell 6,6 because it is in group {2, 7} in that box
4 cannot be in cell 4,4 because it is in group {4, 5} in that box
5 cannot be in cell 4,4 because it is in group {4, 5} in that box
5 cannot be in cell 6,4 because it is in group {8, 5} in that row
4 cannot be in cell 6,7 because it is in group {4, 5} in that row
4 cannot be in cell 5,7 because it is in group {4, 6} in that box
6 cannot be in cell 4,7 because it is in group {1, 6} in that box
4 cannot be in cell 4,2 because it is in group {9, 4} in that row
4 cannot be in cell 5,4 because it is in group {1, 4} in that col
5 cannot be in cell 5,2 because it is in group {9, 5} in that box
2 6 9 1 7 8 5 3 4
5 3 4 2 9 6 1 7 8
1 7 8 3 4 5 9 6 2
9 5 6 8 2 7 4 1 3
3 4 1 5 6 9 2 8 7
8 2 7 4 1 3 6 5 9
6 9 5 7 3 4 8 2 1
4 1 3 6 8 2 7 9 5
7 8 2 9 5 1 3 4 6

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store